DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Year 2021-2022 ======

[[http://pages.di.unipi.it/grossi/|Prof. Roberto Grossi]]
[[http://webhost.services.iit.cnr.it/staff/filippo.geraci/|Dr. Filippo Geracii]]


==== Announcements ====

Lectures will be given both in **presence** and in **streaming** on [[https://teams.microsoft.com/l/team/19%3a83FB0Inw4v9ftWjuzhY6FCZ70amqdEm-Xe4O4jcOR501%40thread.tacv2/conversations?groupId=6c1c2610-7521-4349-8316-7fc06f7a1209&tenantId=c7456b31-a220-47f5-be52-473828670aa1|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:// [[https://esami.unipi.it/programma.php?c=50478&aa=2021&cid=69&did=13|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 [[https://esami.unipi.it/esami/|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. |