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/best-case analysis
Fundamentals of asymptotic analysis
Average-case and randomized algorithms
Recursive algorithms
Amortized analysis
Data structures - Collections and Dictionaries

Lectures

23 Sep 24: Introduction (1-intro.pdf) and algorithm correctness: specifying problems logically (2-correctness.pdf - pages 1-12)
30 Sep 24: Algorithm correctness: partial and complete correctness (2-correctness.pdf - pages 13-36)
7 Out 24: Motivation for performance analysis; Algorithms complexity: best and worst case analysis; Counting steps (3-countingsteps.pdf - pages 1-43)
14 Out 24: Counting steps; Asymptotic complexity; Starting to analyse recursive algorithms (3-countingsteps.pdf - pages 44-77)
21 Out 24: Solving recursive algorithms with unfolding, substitution, and recurrences (3-countingsteps.pdf - pages 78-98)
21 Out 24: Solving recursive algorithms with unfolding, substitution, and recurrences (3-countingsteps.pdf - pages 78-98)
28 Out 24: Teaching interruption
4 Nov 24: Dynamic programming: motivation, concepts and methodology; optimal substructure and overlapping subproblems; examples and variations: longest increasing subsequence, 0-1 Knapsack and edit distance slides/dp.pdf
11 Nov 24: Recursive algorithms: the master theorem (3-countingsteps.pdf - pages 98-113); introduction to average case analysis (4-average-time.pdf - pages 1-17)
18 Nov 24: Intermediate test (30%) in room FC6.140 @ 14h00-15h00 (specification, correction, worst/best time analysis, and asymptotic analysis); average case analysis (4-average-time.pdf - pages 17-19)
25 Nov 24: Average case analysis: more exercises; analysis of the quick-sort algorithm; Las Vegas vs. Monte Carlo algorithms (4-average-time.pdf - pages 20-42); introduction to amortised analysis (4-average-time.pdf - pages 20-42)
2 Dec 24: Amortised analysis: revisiting the aggregate and accounting method; using the potential method (5-amortised.pdf - pages 18-26)
9 Dec 24: Amortised analysis: revision and exercises (5-amortised.pdf - pages 26-46); Data structures (6-data-structures.pdf - pages 1-7)
16 Dec 24: …

Literature and Material

Slides

Main book

Introduction to algorithms, Cormen Thomas H. et al.; ISBN: 9780262033848

Example Tests

Intermediate test, used on the 10th Nov 2023, covering around 30% of the topics
Final test (or improvement test), used on the 15th Dec 2023, covering the remaining 70% of the topics

Previous years

Content from 2023/24 (very similar to this year) https://cister-labs.github.io/alg2324/
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: 978-1-84800-069-8
Competitive Programming 3: The New Lower Bound of Programming Contests; Steven Halim and Felix Halim; 2023
Rigorous Software Development – An Introduction to Program Verification; José Bacelar Almeida, Maria João Frade, Jorge Sousa Pinto, Simão Melo de Sousa 2011; ISBN: 978-0-85729-017-5
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

Teaching methods and learning activities

Lectures; intermediate test 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 exam.

Calculation formula of final grade

(IT) intermediate mid-term test: 30% (done during a lesson, required >=5.5)
(FT) final test: 70% (done during the normal exam period, required >=5.5)
(ER) final exam: 100% (done during “recurso” period, required >=9.5)

1st (“Normal”) classification: C = IT0.3+ FT0.7 >= 9.5

2nd (“Recurso”) classification: C = ER >= 9.5

Lecturer

- - José Proença
  - - DCC 1.69
    - jose.proenca(at)fc.up.pt
    - meet: thu afternoon (email before)
- - Pedro RIbeiro
  - - DCC 1.47
    - pribeiro(at)fc.up.pt
    - meet: tba

Edit the content of this page here.