Algorithm Design and Analysis

Code:

CC211

Acronym:

CC211

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2013/2014 - 1S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~apt/aulas/DAA/1314
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Bachelor in Computer Science

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:CC	57	Plano de estudos de 2008 até 2013/14	2	-	7,5	-
MI:ERS	101	Plano de Estudos a partir de 2007	2	-	7,5	-

Teaching language

Portuguese

Objectives

Introduction of techniques of design and analysis of algorithms.

Learning outcomes and competences

Improving background on generic models of common problems and the algorithmic techniques for solving them. Practical experience in applying generic algorithms to specific problems. Competence in the asymptotic analysis of the running time of algorithms. Understanding the main complexity classes and problem reducibility, with knowledge of typical examples.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Students should know simple algorithms and data structures (for counting, searching and sorting) and a programming language (C or JAVA).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Program

Algorithmic complexity: asymptotic analysis, recurrences, amortized analysis, complexity classes P, NP and co-NP. Graph algorithms: graph types, elementary algorithms, minimum spanning trees, shortest paths, maximum flow. Data structures: binary search trees, red-black trees; heaps and priority queues; disjoint sets. Dynamic programming and greedy algorithms.

Mandatory literature

000102107. ISBN: 9780262033848 hbk
S. Dasgupta, C.H.Papadimitriou, U.V.Vazirani; Algorithms, McGraw-Hill, 2006. ISBN: 978-0073523408
J. Kleinberg, E. Tardos; Algorithm Design, Addison-Wesley, 2005. ISBN: 978-0321295354

Complementary Bibliography

000074403. ISBN: 0-387-00163-8

Teaching methods and learning activities

Regular lectures for exposing the program topics and discussing examples. Laboratory classes for                    solving exercise sheets and programming problems, like those found in programming contests, using known algorithms. Additional programming problems for homework (with automatic evaluation by Mooshak).

Software

Linguagens de programação: C, C++, Java ou Python
Programming languages: C, C++, Java or Python
Servidor Mooshak para CC211 (http://mooshak.dcc.fc.up.pt/~daa)

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	85,00
Participação presencial	0,00
Teste	15,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Frequência das aulas
Trabalho laboratorial
Total:	0,00

Eligibility for exams

Students should attend at least 75% of laboratory classes and obtain at least 1.0 at 3.0 in the programming test.

Calculation formula of final grade

NP: programming test automatically graded by the Mooshak system (weight 3/20). Required NP >= 1.

F:  two intermediate written tests (TE1 and TE2)   or  E: Final exam (weight 17/20) 

F = max(0.3 TE1 + 0.7 TE2, TE2) . Required TE1  >= 8.0  and  TE1 >= 8.0  (TE2 covers all topics)

Final grade (1st exam) :  C = max(E,F)*0.85+NP  >= 9.5

Final grade (rebuttal) :  C = E*0.85+NP  >= 9.5

If F >= 9.5, the student does not need to take the final exam.

Examinations or Special Assignments

Along the semester there are two written tests and one programming test. The written tests and exams consist of generic questions plus questions about problems seen in the laboratory classes. The programming test consists in the submission, using the Mooshak system, of solutions to problems seen in the laboratory classes, or slight variants. The programming test is mandatory.

Test dates:

    - First written test: 13 November, 14:30, rooms FC1 219 and FC1 226

   - Second written test: 18 December, 14:30

   - Programming test: 7 January, 14:00

Special assessment (TE, DA, ...)

The pratical test is compulsory for every student, regardless of special status of any kind.

Classification improvement

Students approved in 2012/2013 must take the final exam and the programming test.