Code: | CC211 | Acronym: | CC211 |
Keywords | |
---|---|
Classification | Keyword |
OFICIAL | Computer Science |
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 |
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 | - |
Introduction of techniques of design and analysis of 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. Understanding the main complexity classes and problem reducibility, with knowledge of typical examples.
Students should know simple algorithms and data structures (for counting, searching and sorting) and a programming language (C or JAVA).
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.
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).
designation | Weight (%) |
---|---|
Exame | 85,00 |
Participação presencial | 0,00 |
Teste | 15,00 |
Total: | 100,00 |
designation | Time (hours) |
---|---|
Frequência das aulas | |
Trabalho laboratorial | |
Total: | 0,00 |
Students should attend at least 75% of laboratory classes and obtain at least 1.0 at 3.0 in the programming test.
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.
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
The pratical test is compulsory for every student, regardless of special status of any kind.
Students approved in 2012/2013 must take the final exam and the programming test.