Questa è una vecchia versione del documento!
Year 2021-2022
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 in unimap log of the lectures (registro delle lezioni). 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).
Data
Giorno
Tipo
Inizio (hh.mm)
Fine (hh.mm)
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.