Algorithm Design and Analysis

Code:

CC2001

Acronym:

CC2001

Level:

200

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2024/2025 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~apt/aulas/DAA/2425
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:B	0	Official Study Plan	3	-	6	48	162
L:CC	100	study plan from 2021/22	2	-	6	48	162
L:F	3	Official Study Plan	3	-	6	48	162
L:G	1	study plan from 2017/18	2	-	6	48	162
			3
L:IACD	96	study plan from 2021/22	2	-	6	48	162
L:M	6	Official Study Plan	2	-	6	48	162
			3
L:MA	0	Official Study Plan	3	-	6	48	162
L:Q	0	study plan from 2016/17	3	-	6	48	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).

Prerequisites: "Imperative Programming" (CC1003) and  "Data Structures"(CC1007), or some course unit with equivalent content.

 

Program

Asymptotic analysis of algorithms: Big O notation (O, Ω e Θ), estimating execution time, analyzing iterative and recursive programs;

Sorting: sorting as basic element of other algorithms; comparative and non comparative algorithms, binary search and direct and indirect applications;

Algorithm design techniques: exhaustive search, greedy algorithms, divide and conquer, dynamic programming;

Some specialized data structures: priority queues, disjoint sets;

Balanced Binary Search Trees: Red-Black trees;

Graph algorithms: graph representation, depth-first search, breadth-first search, minimum spanning trees, minimum distances, maximum flow.

Computtaionally hard problems. Brief introduction to the complexity classes P, NP, NP-hard, NP-complete for decision problems. Introduction to approximation and parameterized algorithms.

Mandatory literature

Thomas H. Cormen; Introduction to algorithms. ISBN: 978-0-262-36750-9 (T.H.Cormen, C.E. Leiserson, R.L.Rivest, C.Stein. Introduction to Algorithms. The MIT Press, 4th ed, 2022)
Cormen Thomas H. 070; Introduction to algorithms. ISBN: 9780262033848 hbk
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
Skiena Steven S.; The algorithm design manual. ISBN: 978-1-84800-069-8
Michael R. Garey; Computers and intractability. ISBN: 0-7167-1045-5

Teaching methods and learning activities

Regular lectures for exposing the program topics and discussing examples. Laboratory classes for solving exercise sheets and programming problems for implementation, with automatic feedback and evaluation by the Mooshak system.

Software

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

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	65,00
Teste	30,00
Trabalho laboratorial	5,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo	72,00
Frequência das aulas	48,00
Trabalho laboratorial	42,00
Total:	162,00

Eligibility for exams

Students must attend at least 75% of the pratical classes to be admitted to the exams. Students who miss more than three classes cannot attend the exams. 

Calculation formula of final grade

• NP (7 points): Obtained with 3 components: 2 practical tests (3 points each) and continuous evaluation solving exercises during the semester (1 point). Required NP>=2.5 (scale from 0 to 7).


• Ex (13 points): theoretical grade, worth 65% of the final grade.


• Final Grade  (requires NP >= 2.5 in 7 and Ex >= 8.0 in 20.0) and 

               NF = Ex * 0.65 + NP >= 9.5

• Academic integrity violations: the regulations from FCUP/University of Porto will be applied.

Examinations or Special Assignments

Two programming tests will be carried out, each worth 6 points (out of 20) towards the final grade (i.e. 30%). The other continuous assessment exercises, proposed for practical classes (1 point), will also have submission deadlines. The tests and exercises will be automatically evaluated by the Mooshak system. The problems to be solved in the tests will be related to those proposed in the practical classes and for extracurricular work.The score for these practical tests cannot be improved.

Special assessment (TE, DA, ...)

The pratical component is compulsory for every student, regardless of special status of any kind. If the student does not achieve the score 2.5 in that component, the final grade will be RFC (failure).

Classification improvement

Students approved in 2023/2024, who wish to improve their grade, must take the practical tests - 6 points - (unless they obtained 3 or 4 points out of 4 in 2023/2024 in that component) - take the final exam (in the regular ou resit period).

Final gradel = 0.7*Ex + TP

where TP is the score in practical tests.

For cases where the practical grade in 2023/2024 was 3 or 4 points, TP will be that grade multiplied by 1.5 (unless the student wants to repeat the tests).

Observations

Prerequisites (not mandatory): "Imperative Programming" (CC1003) and  "Data Structures"(CC1007), or some course unit with equivalent content.

Students without CC1007 may need an extra effort to pass CC2001.


It is strongly recommended that students follow the subjects from the beginning of the semester, through study, active participations in practical and theoretical classes, and by solving the proposed problems (for evaluation by Mooshak).