Algorithm Design and Analysis

Code:

CC2001

Acronym:

CC2001

Level:

200

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2014/2015 - 1S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~pribeiro/aulas/daa1415/
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	60	Plano de estudos a partir de 2014	2	-	6	56	162
MI:ERS	105	Plano Oficial desde ano letivo 2014	2	-	6	56	162

Teaching language

Portuguese

Objectives

To learn techniques for designing and analyzing 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.

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/C++ or JAVA).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Program

Algorithmic complexity: asymptotic analysis, recurrences, some complexity classes. Algorithm design techniques: divide and conquer, greedy algorithms, dynamic programming. Specialized data structure: priority queues, disjoint sets and balances search trees. Graph algorithms: breadth and depth first search, minimum spanning trees, shortest paths, maximum flow.

Mandatory literature

Cormen Thomas H. 070; Introduction to algorithms. ISBN: 9780262033848 hbk
Skiena Steven S.; The algorithm design manual. ISBN: 978-1-84800-069-8
J. Kleinberg, E. Tardos; Algorithm Design, Addison-Wesley, 2005. ISBN: 978-0321295354

Complementary Bibliography

R. Sedgewick and K. Wayne; Algorithms, 4th Edition, Addison-Wesley, 2011. ISBN: 978-0321573513
S. Halim and F. Halim; Competitive Programming, 1st Edition, 2011

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	80,00
Teste	20,00
Total:	100,00

Amount of time allocated to each course unit

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

Eligibility for exams

Students should fill out at least 80% of the weekly quizzes and should have a grade higher than zero in the programming test.

Calculation formula of final grade

NP: programming test automatically graded by the Mooshak system (graded from 0 to 4, global weight 20%). Required NP>0.

F:  two intermediate written tests (TE1 and TE2)   or  E: Final exam (weight 80%) 

F = max(0.5*TE1 + 0.5*TE2). Required TE1  >= 6.0  and  F >= 7.0

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

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

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 theoretical and 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.

Special assessment (TE, DA, ...)

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

Classification improvement

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