Introduction and objectives
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.
The official plan of this course is hosted in FCUP here.
Learning outcomes and competences
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.
Syllabus
 Algorithm correctness
 Complexity: worst/bestcase analysis
 Fundamentals of asymptotic analysis
 Averagecase and randomized algorithms
 Recursive algorithms
 Amortized analysis
 Data structures  Collections and Dictionaries
 Fundamentals of NPcompleteness
Lectures
 22 Sep 23: Introduction (1intro.pdf) and algorithm correctness: specifying problems logically (2correctness.pdf  pages 118)
 29 Sep 23: Algorithm correctness: partial and complete correctness (2correctness.pdf  pages 1336); motivation for performance analysis (3countingsteps.pdf  pages 129)
 6 Oct 23: Algorithms complexity: best and worst case analysis. Counting steps and asymptotic notation (3countingsteps.pdf  pages 2363)
 13 Oct 23: Exercises with asymptotic notation (3countingsteps.pdf  pages 6466); Time complexity of recursive algorithms (3countingsteps.pdf  pages 6795)
 20 Oct 23: Exercises on the time complexity of recursive algorithms and the master theorem (3countingsteps.pdf  pages 96112); Average time complexity (4averagetime.pdf  pages 119)
 27 Oct 23: Average time complexity and analysis of the quicksort algorithm (4averagetime.pdf  pages 2032); Randomised algorithms (4averagetime.pdf  pages 3340); Amortised analysis and the aggregate method (5amortised.pdf  pages 111)
 10 Nov 23: Test (30%): 9h3010h30 (Specification, Correction, Worst/Best time analysis, Asymptotic analysis); Rest of the lesson starts at 11h15  Amortised analysis (5amortised.pdf  pages 1126)
 17 Nov 23: Amortised analysis (5amortised.pdf  pages 2744); Data structures: sequences (6datastructures.pdf  pages 18)
 24 Nov 23: Data structures: buffers and dictionaries (6datastructures.pdf  pages 928)
 1 Dec 23: Holiday
 8 Dec 23: Holiday
 15 Dec 23: Improvement test (70%): 9h3011h30 (focused on averagetime, amortised time, and data structures, but all topics can be asked); no lesson after the test
Literature and Material
Slides
 Introduction to the course
 Algorithm correctness
 Counting steps and asymptotic notation
 Averagetime and probabilistic algorithms
 Amortised analysis
 Data structures
Main book
 Introduction to algorithms, Cormen Thomas H. et al.; ISBN: 9780262033848
Previous years
 Slides from Pedro Ribeiro (2018/19): https://www.dcc.fc.up.pt/~pribeiro/aulas/alg1819/material.html#slides
 Content from Ana Paula Tomás (2021/22): https://www.dcc.fc.up.pt/~apt/Aulas/ALGO2223.html
 Slides from similar courses:
 By E. Demaine, C.E. Leiserson, MIT, 2001 (companion of the main book  more on the course)
 By Skiena, Stony Brook University, 2012
 By J. Barros, J.S. Pinto et. al, U. Minho (2022/23) (no content online)
Complementary Bibliography
 The algorithm design manual; Skiena Steven S.; ISBN: 9781848000698
 Competitive Programming 3: The New Lower Bound of Programming Contests; Steven Halim and Felix Halim; 2023
 Algorithms; Sedgewick Robert; ISBN: 0201066734
 Algorithm Design; Jon Kleinberg and Éva Tardos; 2005. ISBN: 9780321295354
 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
Teaching methods and learning activities
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.
Evaluation Type
Distributed evaluation with final exam
Assessment Components
designation  Weight (%) 

Exam  70,00 
Test  30,00 
Amount of time allocated to each course unit
designation  Time (hours) 

Home study  120,00 
Attendance time  42,00 
Total:  162,00 
Eligibility for exams
All students will be admitted to the exams.
Calculation formula of final grade
 (IT) intermediate midterm test (mandatory) 30%
 10 Nov, during the lecture time.

(FE) final exam: 70% (can be replaced by IT2)
 (IT2) improvement test: can replace the final exam. Required IT2 >= 8.
1st Exam (“Normal”) classification: C = max(FE,IT2)0.7+ IT0.3 >= 9.5
2nd Exam (“Recurso”) classification: C = max(FE0.7+IT0.3, FE) >= 9.5
Required FE >=8.
Contact
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.