Algorithms and complexity

A.Y. 2021/2022
Overall hours
Learning objectives
his course aims at raising students' awareness on the role of approximation algorithms and on the impact of randomness on designing efficient algorithms
Expected learning outcomes
The student should be able to design and study algorithms using the techniques described during the course
Course syllabus and organization

Single session

Lesson period
First semester
Synchronous video lessons (if needed).
Course syllabus
* Approximation algorithms

- The NPO, APX, PTAS, FPTAS complexity classes
- Greedy techniques
... The load balancing problem [A]
... The center selection problem [A]
... Inapproximability of the center selection problem [C]
... The set cover problem [A]
- Pricing technique
... The vertex cover probem [A]
... The disjoint paths problem [A]
- Rounding techniques
... Vertex cover by rounding [A]
- Other examples
... The Christofides algorithm for metric TSP [B]
... Inapproximability of TSP [D.6]
- Polynomial time and fully polynomial time approximation schemes
... A PTAS (based on the reduced exhaustive solution) of the minimum partition problem [G]
... A FPTAS (based on rounding) of the knapsack problem [C]

- Probabilistic algorithms

- The Karger algorithm for minimum global cut [E]
- The Miller-Rabin for primality (no proof) [H]
- A randomized-rounding algorithm for set cover [D.4]
- A probabilistic algorithm for MaxEkSat and its derandomization [D.3]
- Approximation complexity

- The PCP theorem (no proof) [F.3, Theorem 1]
- PCP and inapproximability of MaxSat and MaxE3Sat [F.3.1]
- PCP and inapproximability of independent set [F.4.4, Claim 13 and Claim 14]

- Succinct, quasi-succinct and compact data structures

- Succinct structures for rank and selection; the "Four-Russians Trick" [D.9, excluding 9.2]
- Succinct structures for binary trees [D.10]
- Quasi-succinct Elias-Fano coding for monotone sequences [D.11, excluding D.11.1 and D.11.2]
- Compact structure for balanced parenthesis [D.12]
- Quasi-succinct functions: the MWHC technique [D.13]
- Minimal perfect hashing [D.13]
Prerequisites for admission
A first course on algorithms and data structures.
Teaching methods
Frontal teaching.
Teaching Resources
[A] Chapter 11 (excluding 11.7) of Jon Kleinberg, Éva Tardos: Algorithm Design, Pearson, 2013
[B] Cornell handouts on the Christofides algorithm
[C] Kevin Wayne's slides
[D] Sebastiano Vigna's handouts
[E] Stanford slides on Karger's algorithm
[F] Luca Trevisan's handouts
[G] Section 3.2 of Ausiello et al.: Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer 1999
[H] Miller-Rabin's Algorithm (Wikipedia page)
Assessment methods and Criteria
Oral examination.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor: Boldi Paolo
Educational website(s)