Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- magistraleinformatica:ad:ad_21:start [13/04/2022 alle 14:26 (3 anni fa)] – creata Roberto Grossi
+++ magistraleinformatica:ad:ad_21:start [12/09/2022 alle 13:34 (3 anni fa)] (versione attuale) – Roberto Grossi
@@ Linea 26: / Linea 26: @@
 //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 in [[https://unimap.unipi.it/registri/printregistriNEW.php?re=3319217:::&ri=9172|unimap log of the lectures (registro delle lezioni)]]. Handouts are are available in the MS Teams channel.
+  * Please see the topics listed below. Handouts are are available in the MS Teams channel.
 == Activity in class ==
@@ Linea 37: / Linea 40: @@
 == Official forms for the course ==
-  * Access to [[https://unimap.unipi.it/registri/printregistriNEW.php?re=3319217:::&ri=9172|unimap log of the lectures (registro delle lezioni)]].
   * 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. |