This course is about designing algorithms for computational problems, and how to think clearly about analyzing correctness and running time. The main goal is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future.
Students should be able to understand the relationship between algorithm design, correctness proof and complexity analysis. Students should learn algorithmic techniques of general applicability and get to know some major algorithms in a few common domains. They will also obtain practical experience in applying generic algorithms to specific problems.
- Algorithm Correctness
- Complexity: worst/best-case analysis
- Fundamentals of asymptotic analysis
- Average-case and randomized algorithms
- Recursive algorithms
- Sorting algorithms
- Amortized analysis
- Graph traversals and Dynamic programming
- Fundamentals of NP-completeness
- 22 Sep 24: Introduction (1-intro.pdf)
- ...
- Introduction to algorithms, Cormen Thomas H. et al.; ISBN: 9780262033848
- The algorithm design manual; Skiena Steven S.; ISBN: 978-1-84800-069-8
- Competitive Programming 3: The New Lower Bound of Programming Contests; Steven Halim and Felix Halim; 2023
- Algorithms; Sedgewick Robert; ISBN: 0-201-06673-4
- Algorithm Design; Jon Kleinberg and Éva Tardos; 2005. ISBN: 978-0321295354
- Tópicos Avançados em Algoritmos; Armando Matos; DCC/FCUP, 2008 (In Portuguese - some lecture notes)
- Desenho e Análise de Algoritmos – Alguns Apontamentos; Ana Paula Tomás; DCC/FCUP, 2013
Lectures; intermediate test (mandatory) and final test or final exam.
The lectures mix the presentation of new material (introducing concepts, main algorithms and some results) with interactive discussion of their application when solving real problems.
The homework focus is on practical application of algorithmic concepts, consolidating the learned material.
The final exam and intermediate tests (closed book), globally evaluates the knowledge acquired by the students.
Distributed evaluation with final exam
| designation | Weight (%) |
|---|---|
| Exam | 80,00 |
| Test | 20,00 |
| designation | Time (hours) |
|---|---|
| Home study | 120,00 |
| Attendance time | 42,00 |
| Total: | 162,00 |
All students will be admitted to the exams.
-
(IT) intermediate mid-term test (mandatory) 20%
-
(FE) final exam: 80% (can be replaced by Tf)
-
(IE) improvement exam: can replace the final exam. Required IE >= 8.
1st Exam ("Normal") classification: C = max(FE,IE)0.8+ IT0.2 >= 9.5
2nd Exam ("Recurso") classification: C = max(FE0.8+IT0.2, FE) >= 9.5
Required FE >=8.
By final exam.
The day and time for appointments is Friday afternoon (José Proença). Please email me the day before if you wish to meet. If you prefer you can also just send an email with your questions to José Proença, or we can try to book an online meeting.