DidaWiki

Strumenti Utente

Strumenti Sito

Ti trovi qui: DidaWiki » Corso di Laurea Magistrale in Informatica » Algorithm Design » Year 2022-2023
magistraleinformatica:ad:ad_22: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_22:start [22/05/2023 alle 17:38 (2 anni fa)] – Roberto Grossimagistraleinformatica:ad:ad_22:start [03/07/2023 alle 12:07 (24 mesi fa)] (versione attuale) – Roberto Grossi
Linea 48: Linea 48:
  
 ^ Date ^ Topics ^ References and notes ^ ^ Date ^ Topics ^ References and notes ^
-|22.02.2023 | Introduction to the class. | |+|22.02.2023 | Introduction to the class. Course organization, schedule, and purpose. | |
 |24.02.2023| Playing with probability. Random indicator variables: secretary problem and random permuting (suggested reading: birthday paradox). Randomized quick sort. | [CLRS 5.1-5.3 (optional 5.4.1), {{:magistraleinformatica:alg2:algo2_13:randqs.pdf|par. 7.3}}] [[https://repl.it/L9KD/1|code]] | |24.02.2023| Playing with probability. Random indicator variables: secretary problem and random permuting (suggested reading: birthday paradox). Randomized quick sort. | [CLRS 5.1-5.3 (optional 5.4.1), {{:magistraleinformatica:alg2:algo2_13:randqs.pdf|par. 7.3}}] [[https://repl.it/L9KD/1|code]] |
 |27.02.2023| Virus scan and stream analysis with Karp-Rabin fingerprints: randomized checking and pattern matching. Montecarlo and Las Vegas algorithms. | [RM {{:magistraleinformatica:alg2:algo2_15:karp-rabin-1.pdf| par.7.4-7.6}}]  [[https://repl.it/LbWC/3|code]]| |27.02.2023| Virus scan and stream analysis with Karp-Rabin fingerprints: randomized checking and pattern matching. Montecarlo and Las Vegas algorithms. | [RM {{:magistraleinformatica:alg2:algo2_15:karp-rabin-1.pdf| par.7.4-7.6}}]  [[https://repl.it/LbWC/3|code]]|
 |01.03.2023| Universal hashing. Markov's inequality. Perfect hashing.| [CLRS 11.2, 11.3.3, CLRS 11.5 ] [[https://repl.it/Ljuh/8|code]]| |01.03.2023| Universal hashing. Markov's inequality. Perfect hashing.| [CLRS 11.2, 11.3.3, CLRS 11.5 ] [[https://repl.it/Ljuh/8|code]]|
 |03.03.2023 | Weekly hands-on. | see Teams drive | |03.03.2023 | Weekly hands-on. | see Teams drive |
-|06.03.2023 | Introduction to game theory. The theory of rational choice. Strategic games. The prisoner dilemma. Pollution game. Bach or Stravinsky. Matching Pennies. Stag hunt.| see Teams drive | +|06.03.2023 | Introduction to game theory. The theory of rational choice. Strategic games. The prisoner dilemma. Pollution game. Bach or Stravinsky. Matching Pennies. Stag hunt. (F. Geraci) | see Teams drive | 
-|08.03.2023 | Nash equilibrium. Review of example strategic games. Nash equilibrium of stag hunt with n players. Best response. Using best response to find the Nash equilibrium. | see Teams drive | +|08.03.2023 | Nash equilibrium. Review of example strategic games. Nash equilibrium of stag hunt with n players. Best response. Using best response to find the Nash equilibrium. (F. Geraci) | see Teams drive | 
-|10.03.2023 | Weekly hands-on. | see Teams drive | +|10.03.2023 | Weekly hands-on. (F. Geraci) | see Teams drive | 
-|13.03.2023 | Game Theory. Improving and best response. Dominated actions. Vickrey auction (aka second price auction). Expected payoffs. | see Teams drive | +|13.03.2023 | Game Theory. Improving and best response. Dominated actions. Vickrey auction (aka second price auction). Expected payoffs. (F. Geraci) | see Teams drive | 
-|15.03.2023 | Mixed strategy Nash equilibrium. Example: matching penny. Example: kicking penalty. Stable matching. | see Teams drive | +|15.03.2023 | Mixed strategy Nash equilibrium. Example: matching penny. Example: kicking penalty. Stable matching. (F. Geraci) | see Teams drive | 
-|17.03.2023 | Weekly hands-on. | see Teams drive |+|17.03.2023 | Weekly hands-on. (F. Geraci) | see Teams drive |
 |20.03.2023| Worst-case constant-time lookup: Cuckoo hashing. | {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_16:cuckoohashinsertion.pdf|Notes}}  [[https://repl.it/NzGN/3|code]]| |20.03.2023| Worst-case constant-time lookup: Cuckoo hashing. | {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_16:cuckoohashinsertion.pdf|Notes}}  [[https://repl.it/NzGN/3|code]]|
 |22.03.2023| Proxy caches and dictionaries with errors: Bloom filters. | {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|Survey: except par.2.5-2.6 (optional: par.2.2)}} | |22.03.2023| Proxy caches and dictionaries with errors: Bloom filters. | {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|Survey: except par.2.5-2.6 (optional: par.2.2)}} |
Linea 67: Linea 67:
 |03.04.2023| Document resemblance with MinHash, k-sketches and the Jaccard similarity index. Azuma-Hoeffding bound. Triangle counting. | [[http://gatekeeper.dec.com/ftp/pub/dec/SRC/publications/broder/positano-final-wpnums.pdf|paper]] [[http://cs.brown.edu/courses/cs253/papers/nearduplicate.pdf|paper]] [[http://homes.cs.washington.edu/~jrl/cs525/scribes08/lec10.pdf|Azuma-Hoeffding]] [[https://repl.it/MDNO/3|code]]| |03.04.2023| Document resemblance with MinHash, k-sketches and the Jaccard similarity index. Azuma-Hoeffding bound. Triangle counting. | [[http://gatekeeper.dec.com/ftp/pub/dec/SRC/publications/broder/positano-final-wpnums.pdf|paper]] [[http://cs.brown.edu/courses/cs253/papers/nearduplicate.pdf|paper]] [[http://homes.cs.washington.edu/~jrl/cs525/scribes08/lec10.pdf|Azuma-Hoeffding]] [[https://repl.it/MDNO/3|code]]|
 |05.04.2023| Count-Min sketches for frequent elements.| {{http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf| sects.1-3, 4.1}} [[https://sites.google.com/site/countminsketch/|Site]] {{:magistraleinformatica:alg2:algo2_12:count-min-sketch.pdf|Notes}} [[https://repl.it/Lvob/3|code]]| |05.04.2023| Count-Min sketches for frequent elements.| {{http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf| sects.1-3, 4.1}} [[https://sites.google.com/site/countminsketch/|Site]] {{:magistraleinformatica:alg2:algo2_12:count-min-sketch.pdf|Notes}} [[https://repl.it/Lvob/3|code]]|
-|08.05.2023| Fixed-parameter tractable (FPT) algorithms. Kernelization. Bounded search tree. Case study: min-vertex cover in graphs.  | [[https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf|sect. 2.2.1, 3.1]] | +|14.04.2023 | Weekly hands-on. | see Teams drive | 
-|10.05.2023| Randomized FPT algorithms: color coding and randomized separation. Case study: longest path in graphs and subgraph isomorphism. | [[https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf|sect. 5.2, 5.3]] |+|17.04.2023 | The data stream model. Cardinality estimation. Linear counting. LogLog counters. (F. Geraci) | see Teams drive | 
 +|19.04.2023 | Bloom filters (probabilistic deletion and counting). Count min sketch. Heavy hitters. The space saving algorithm. (F. Geraci) | see Teams drive | 
 +|21.04.2023 | Weekly hands-on. (F. Geraci) | see Teams drive |
 |24.04.2023| Networked data and randomized min-cut algorithm for graphs. | {{:magistraleinformatica:alg2:algo2_15:mincut1.pdf| par.1.1}} | |24.04.2023| Networked data and randomized min-cut algorithm for graphs. | {{:magistraleinformatica:alg2:algo2_15:mincut1.pdf| par.1.1}} |
 |26.04.2023| Approximation in fine-grained algorithms and limitations. Case study: diameter in undirected unweighted graphs. | {{ :magistraleinformatica:ad:ad_17:diameterapprox.pdf | notes }} | |26.04.2023| Approximation in fine-grained algorithms and limitations. Case study: diameter in undirected unweighted graphs. | {{ :magistraleinformatica:ad:ad_17:diameterapprox.pdf | notes }} |
 |03.05.2023| Fine-grained algorithms. SETH conjecture and conditional lower bounds. Guaranteed heuristics. Case study: diameter in undirected unweighted graphs. | [[https://www.dropbox.com/s/zq0dklabkjyd302/20171212.pdf?dl=0|notes]] [[https://people.csail.mit.edu/virgi/ipec-survey.pdf|sect. 2.3, 2.4, 3, 4]]| |03.05.2023| Fine-grained algorithms. SETH conjecture and conditional lower bounds. Guaranteed heuristics. Case study: diameter in undirected unweighted graphs. | [[https://www.dropbox.com/s/zq0dklabkjyd302/20171212.pdf?dl=0|notes]] [[https://people.csail.mit.edu/virgi/ipec-survey.pdf|sect. 2.3, 2.4, 3, 4]]|
 +|08.05.2023| Fixed-parameter tractable (FPT) algorithms. Kernelization. Bounded search tree. Case study: min-vertex cover in graphs.  | [[https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf|sect. 2.2.1, 3.1]] |
 +|10.05.2023| Randomized FPT algorithms: color coding and randomized separation. Case study: longest path in graphs and subgraph isomorphism. | [[https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf|sect. 5.2, 5.3]] |
 |12.05.2023| Local search, Greedy, Randomized: case study of max cut for graphs. | {{:magistraleinformatica:alg2:algo2_14:lec02.pdf|Notes}} | |12.05.2023| Local search, Greedy, Randomized: case study of max cut for graphs. | {{:magistraleinformatica:alg2:algo2_14:lec02.pdf|Notes}} |
 |15.05.2023| NP-hard problems: download file manager and the knapsack problem. Dynamic programming algorithms for Knapsack: Case 1: integer weights, complexity O(nW). Case 2: integer values, complexity O(n<sup>2</sup>vmax). Examples.  General inapproximability results. Case study: travel salesman problem (TSP).  2-approximation algorithms for metric TSP. | [CLRS 35.2] [[https://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf|notes]] | |15.05.2023| NP-hard problems: download file manager and the knapsack problem. Dynamic programming algorithms for Knapsack: Case 1: integer weights, complexity O(nW). Case 2: integer values, complexity O(n<sup>2</sup>vmax). Examples.  General inapproximability results. Case study: travel salesman problem (TSP).  2-approximation algorithms for metric TSP. | [CLRS 35.2] [[https://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf|notes]] |
 |17.05.2023| NP-hard problems: fully polynomial-time randomized approximation schemes (FPRASs). Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf|notes]] [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] | |17.05.2023| NP-hard problems: fully polynomial-time randomized approximation schemes (FPRASs). Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf|notes]] [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] |
  
magistraleinformatica/ad/ad_22/start.1684777134.txt.gz · Ultima modifica: 22/05/2023 alle 17:38 (2 anni fa) da Roberto Grossi
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki