Code: | CC2001 | Acronym: | CC2001 | Level: | 200 |
Keywords | |
---|---|
Classification | Keyword |
OFICIAL | Computer Science |
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 |
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 | 101 | study plan from 2021/22 | 2 | - | 6 | 48 | 162 |
L:F | 4 | Official Study Plan | 3 | - | 6 | 48 | 162 |
L:G | 2 | study plan from 2017/18 | 2 | - | 6 | 48 | 162 |
3 | |||||||
L:IACD | 93 | study plan from 2021/22 | 2 | - | 6 | 48 | 162 |
L:M | 5 | 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 |
Teacher | Responsibility |
---|---|
Ana Paula Nunes Gomes Tomás |
Theoretical classes: | 1,85 |
Laboratory Practice: | 1,85 |
Type | Teacher | Classes | Hour |
---|---|---|---|
Theoretical classes | Totals | 1 | 1,846 |
Ana Paula Nunes Gomes Tomás | 1,846 | ||
Laboratory Practice | Totals | 6 | 11,076 |
Pedro Manuel Pinto Ribeiro | 3,692 | ||
Ana Paula Nunes Gomes Tomás | 3,692 |
To learn techniques for designing and analyzing algorithms.
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.
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.
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.
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.
designation | Weight (%) |
---|---|
Exame | 80,00 |
Teste | 20,00 |
Total: | 100,00 |
designation | Time (hours) |
---|---|
Estudo autónomo | 72,00 |
Frequência das aulas | 48,00 |
Trabalho laboratorial | 42,00 |
Total: | 162,00 |
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.
max(TE*0.4+Ex*0.6, Ex)*0.8 + NP >= 9.5
max(TE*0.4+Ex*0.6, Ex)*0.8 + NP >= 9.5
There will be one or two programming tests (weighted at 20% in total). They consist in the submission, using the Mooshak system, of solutions to problems similar to those proposed in the laboratory classes and for homework.The grade for these tests (NP) cannot be improved.
The pratical component is compulsory for every student, regardless of special status of any kind. If the student does not take the practical test, it will score 0 in that component.
Students approved in 2023/2024, who wish to improve their grade, must take the practical tests ((unless they obtained 3 or 4 points out of 4 in 2023/2024 in that component) and the final exam (in the regular ou resit period).
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).