Year 2021-2022

Prof. Roberto Grossi Dr. Filippo Geracii

Announcements

Lectures will be given both in presence and in streaming on Microsoft Teams.

Schedule

Class hours: Tue 09:00‑10:45, Wed 09:00‑10:45, Fri 11:00‑12:45
Office hours: remotely by appointment.

Overview

The advanced nature of this course focuses on developing algorithmic design skills, exposing the students to complex problems that cannot be directly handled by standard libraries (being aware that several basic algorithms and data structures are already covered by the libraries of modern programming languages), thus requiring a significant effort in problem solving. These problems involve all basic data types, such as integers, strings, (geometric) points, trees and graphs as a starting point. The syllabus is structured to highlight the applicative situations in which the corresponding algorithms can be successfully employed, making references to software applications and libraries. The level of detail in each argument can change year-by-year, and will be decided according to requests coming from other courses in the curriculum and/or specific issues arising in, possibly novel, applicative scenarios.

Exams

Written exam: weekly hands-on in classroom.

Oral exam: topics discussed in class, please read the references in the notes.

Syllabus: programma d'esame

Topics

Please see the topics listed below. Handouts are are available in the MS Teams channel.

Activity in class

The screen snapshots shown during the classes are available in the MS Teams channel.

Official forms for the course

Access to the course evaluation form (questionario studenti).

Registro delle lezioni

Data	Giorno	Tipo	Inizio	Fine	Ore accademiche	Argomento della lezione
02/15/2022	Martedi	lezione	9.00	11.00	2	Introduction to the class. Load balancing.
02/16/2022	Mercoledi	lezione	9.00	11.00	2	Universal hashing.
02/18/2022	Venerdi	lezione	11.00	13.00	2	Concentration bounds: Markov's inequality (MI), Chebyshev's inequality (CI), Chernoff's bounds (CB).
02/22/2022	Martedi	esercitazione	9.00	11.00	2	Hands-on activity
02/23/2022	Mercoledi	lezione	9.00	11.00	2	Cuckoo hashing.
02/25/2022	Venerdi	lezione	11.00	13.00	2	Power of using 2 hash functions (load balancing). Randomized Quicksort.
03/01/2022	Martedi	esercitazione	9.00	11.00	2	Hands-on activity
03/02/2022	Mercoledi	lezione	9.00	11.00	2	Randomized fingerprints.Randomized algorithms: Montecarlo vs Las Vegas. Karp-Rabin pattern matching.
03/04/2022	Venerdi	lezione	11.00	13.00	2	Playing with probability: Birthday Paradox, the Hiring Problem, Random Permuting. Randomness and Kolmogorov complexity.
03/08/2022	Martedi	esercitazione	9.00	11.00	2	Hands-on activity
03/09/2022	Mercoledi	lezione	9.00	11.00	2	The data stream model. Cardinality estimation. Linear counting. LogLog counters. (Filippo Geraci)
03/11/2022	Venerdi	lezione	11.00	13.00	2	Bloom filters (probabilistic deletion and counting). Count min sketch. Heavy hitters. The space saving algorithm. (Filippo Geraci)
03/15/2022	Martedi	esercitazione	9.00	11.00	2	Hands-on activity (Filippo Geraci)
03/16/2022	Mercoledi	lezione	9.00	11.00	2	Bloom filters.
03/18/2022	Venerdi	lezione	11.00	13.00	2	Approximate (Montecarlo) dictionaries.
03/22/2022	Martedi	esercitazione	9.00	11.00	2	Hands-on activity
03/23/2022	Mercoledi	lezione	9.00	11.00	2	Morris' counters. Fully polynomial-time approximation scheme (FPTAS).
03/25/2022	Venerdi	lezione	11.00	13.00	2	Using Chebychev's inequality and variance for FPTAS on counters. Using Chernoff's bounds to boost probability in FPTAS.
03/29/2022	Martedi	esercitazione	9.00	11.00	2	Hands-on activity
03/30/2022	Mercoledi	lezione	9.00	11.00	2	Sketching algorithms: FM-sketches (Flajolet-Martin).
04/01/2022	Venerdi	lezione	11.00	13.00	2	Count-min sketch.
04/05/2022	Martedi	lezione	9.00	11.00	2	Count-min sketch (continued).
04/06/2022	Mercoledi	esercitazione	9.00	11.00	2	Hands-on activity
04/08/2022	Venerdi	lezione	11.00	13.00	2	Min-hash sketch.
04/12/2022	Martedi	esercitazione	9.00	11.00	2	Hands-on activity
04/13/2022	Mercoledi	lezione	9.00	11.00	2	Introduction to game theory.The theory of rational choice. Strategic games. (Filippo Geraci)
04/22/2022	Venerdi	lezione	11.00	13.00	2	Nash equilibrium . Best response. (Filippo Geraci)
04/26/2022	Martedi	esercitazione	9.00	11.00	2	Hands-on activity. (Filippo Geraci)
04/27/2022	Mercoledi	lezione	9.00	11.00	2	Improving and best response. Dominated actions. Vickrey auction (aka second price auction). (Filippo Geraci)
04/29/2022	Venerdi	lezione	11.00	13.00	2	Expected payoffs. Mixed strategy Nash equilibrium. Stable matching. (Filippo Geraci)
05/03/2022	Martedi	esercitazione	9.00	11.00	2	Hands-on activity (Filippo Geraci)
05/04/2022	Mercoledi	lezione	9.00	11.00	2	Fine-grained complexity: upper and conditional lower bounds for the graph diameter.
05/06/2022	Venerdi	lezione	11.00	13.00	2	NP-hardness. Case study: Knapsack. Exact algorithms.
05/10/2022	Martedi	lezione	9.00	11.00	2	Case study: Knapsack. Approximation algorithms. FPTAS.
05/11/2022	Mercoledi	lezione	9.00	11.00	2	Case study: Traveling Salesperson Problem (TSP). Conditional inapproximability. Metric TSP and approximation. Min-vertex cover and approximation.
05/13/2022	Venerdi	lezione	11.00	13.00	2	Parameterized algorithms. Kernelization. Branching technique.
05/17/2022	Martedi	lezione	9.00	11.00	2	Color coding. Randomized separation.