DidaWiki

Strumenti Utente

Strumenti Sito

Ti trovi qui: DidaWiki » Corso di Laurea Magistrale in Informatica » Algorithm Design » Year 2021-2022
magistraleinformatica:ad:ad_21:start

Differenze

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

Link a questa pagina di confronto

Entrambe le parti precedenti la revisioneRevisione precedente
Prossima revisione		Revisione precedente
magistraleinformatica:ad:ad_21:start [12/09/2022 alle 13:14 (3 anni fa)] – Roberto Grossimagistraleinformatica:ad:ad_21:start [12/09/2022 alle 13:34 (3 anni fa)] (versione attuale) – Roberto Grossi
Linea 32: Linea 32:
 ==== Topics ==== ==== Topics ====
  
-  * Please see the topics listed in [[https://unimap.unipi.it/registri/printregistriNEW.php?re=3323863:::&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 == == Activity in class ==
Linea 40: Linea 40:
 == Official forms for the course == == Official forms for the course ==
  
-  * Access to [[https://unimap.unipi.it/registri/printregistriNEW.php?re=3323863:::&ri=9172|unimap log of the lectures (registro delle lezioni)]]. 
   * Access to the [[https://esami.unipi.it/esami/|course evaluation form (questionario studenti)]].   * Access to the [[https://esami.unipi.it/esami/|course evaluation form (questionario studenti)]].
  
  
 +==== Registro delle lezioni ====
  
  
-**Data** +| **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. | 
-**Giorno** +| 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). | 
-**Tipo** +| 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. | 
-**Inizio (hh.mm)** +| 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 | 
-**Fine (hh.mm)** +| 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. | 
-**Ore accademiche** +| 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) | 
-**Argomento della lezione** +| 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) | 
-02/15/2022 +| 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. | 
-Martedi +| 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). | 
-lezione +| 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 | 
-9.00 +| 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. | 
-11.00 +| 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 | 
-2 +| 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 | 
-Introduction to the class. Load balancing. +| 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) | 
-02/16/2022 +| 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) | 
-Mercoledi +| 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) | 
-lezione +| 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. | 
-9.00 +| 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. | 
-11.00 +| 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. |
-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.1662988486.txt.gz · Ultima modifica: 12/09/2022 alle 13:14 (3 anni fa) da Roberto Grossi
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki