Strumenti Utente

Strumenti Sito


magistraleinformatica:ad:ad_21:start

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 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

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.
magistraleinformatica/ad/ad_21/start.txt · Ultima modifica: 12/09/2022 alle 13:34 (22 mesi fa) da Roberto Grossi