| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| magistraleinformatica:ad:ad_18:start [10/04/2019 alle 09:50 (6 anni fa)] – Roberto Grossi | magistraleinformatica:ad:ad_18:start [24/04/2020 alle 07:13 (4 anni fa)] (versione attuale) – Roberto Grossi |
|---|
| ==== Schedule ==== | ==== Schedule ==== |
| |
| * Please note that the class on April 16 will be taken in room X2 as planned, even though other rooms could be closed. Please enter the building from the coffee kiosk side. | * Please note that the class on April 16 will not take place. |
| * Class hours: Tue 16:00‑18:00 (Fib X2), Wed 11:00‑13:00 (Fib X2), Fri 11:00‑13:00 (Fib X2) | * Class hours: Tue 16:00‑18:00 (Fib X2), Wed 11:00‑13:00 (Fib X2), Fri 11:00‑13:00 (Fib X2) |
| * Office hours: Fri 13:00-16:00 or by appointment. | * Office hours: Fri 13:00-16:00 or by appointment. |
| |08.03.2019| Dictionary of keywords. Quick review of classical hashing. Universal hashing. Markov's inequality. Perfect hashing.| [CLRS 11.2, 11.3.3, CLRS 11.5 ] [[https://repl.it/Ljuh/8|code]]| | |08.03.2019| Dictionary of keywords. Quick review of classical hashing. Universal hashing. Markov's inequality. Perfect hashing.| [CLRS 11.2, 11.3.3, CLRS 11.5 ] [[https://repl.it/Ljuh/8|code]]| |
| |12.03.2019| Data Streaming algorithms. Motivations and examples. Count-Min Sketches | {{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]]| | |12.03.2019| Data Streaming algorithms. Motivations and examples. Count-Min Sketches | {{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]]| |
| |13.03.2019| rsync: using hashing and fingerprinting to sync file systems. | {{ :magistraleinformatica:ad:ad_18:rsync.pdf |slides}} | | |13.03.2019| Case study on hashing: rsync and file synchronization using hash functions. | {{ :magistraleinformatica:ad:ad_18:rsync.pdf |slides}} | |
| |15.03.2019| Queries with Count-Min Sketches: implementation and analysis. | {{http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf| sects.3-4}} {{:magistraleinformatica:alg2:algo2_12:count-min-sketch-median.pdf|Notes}} | | |15.03.2019| Queries with Count-Min Sketches: implementation and analysis. | {{http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf| sects.3-4}} {{:magistraleinformatica:alg2:algo2_12:count-min-sketch-median.pdf|Notes}} | |
| |19.03.2019| Building minimal perfect hashing. | {{ :magistraleinformatica:ad:ad_18:perfect_hashing.pdf |paper}} {{ :magistraleinformatica:ad:ad_18:tagger.tgz |code}}| | |19.03.2019| Case study on hashing: document tagging and perfect hashing. | {{ :magistraleinformatica:ad:ad_18:perfect_hashing.pdf |paper}} {{ :magistraleinformatica:ad:ad_18:tagger.tgz |code}}| |
| |20.03.2019| Document resemblance with MinHash, k-sketches and the Jaccard similarity index. Azuma-Hoeffding bound. | [[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]]| | |20.03.2019| Document resemblance with MinHash, k-sketches and the Jaccard similarity index. Azuma-Hoeffding bound. | [[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]]| |
| |22.03.2019| 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.2019| Proxy caches and dictionaries with errors: Bloom filters. | {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|Survey: except par.2.5-2.6 (optional: par.2.2)}} | |
| |26.03.2019| Bloom filters (continued). Cuckoo hashing. | {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_16:cuckoohashinsertion.pdf|Notes}} [[https://repl.it/NzGN/3|code]]|| | |26.03.2019| Bloom filters (continued). Cuckoo hashing. | {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_16:cuckoohashinsertion.pdf|Notes}} [[https://repl.it/NzGN/3|code]]| |
| |27.03.2019| | | | |27.03.2019| Case study on data streams (I): probabilistic counting. | {{ :magistraleinformatica:ad:ad_18:data-stream-stats.pdf |slides}} {{ :magistraleinformatica:ad:ad_18:cms.zip | code}} | |
| |29.03.2019| Cuckoo hashing (continued). Distributed server and load balancing through hashing. | [[https://jeremykun.com/2015/12/28/load-balancing-and-the-power-of-hashing/|blog]] [[https://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesF15/hashing.pdf|Sect.7 and 8.1]] | | |29.03.2019| Cuckoo hashing (continued). Distributed server and load balancing through hashing. | [[https://jeremykun.com/2015/12/28/load-balancing-and-the-power-of-hashing/|blog]] [[https://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesF15/hashing.pdf|Sect.7 and 8.1]] | |
| |09.04.2019| Networked data and randomized min-cut algorithm for graphs. | {{:magistraleinformatica:alg2:algo2_15:mincut1.pdf| par.1.1}} | | |09.04.2019| Networked data and randomized min-cut algorithm for graphs. | {{:magistraleinformatica:alg2:algo2_15:mincut1.pdf| par.1.1}} | |
| |10.04.2019| | | | |10.04.2019| Case study on data streams (II): set membership and heavy hitters. | {{ :magistraleinformatica:ad:ad_18:data-stream-stats.pdf |slides}} {{ :magistraleinformatica:ad:ad_18:cms.zip | code}} | |
| |12.04.2019| | | | |12.04.2019| NP-hard problems: download file manager and the knapsack problem. Reduction from Partition to Knapsack (restriction). Dynamic programming algorithms for Knapsack: Case 1: integer weights, complexity O(nW). Case 2: integer values, complexity O(n<sup>2</sup>vmax). Examples. | {{ :magistraleinformatica:ad:ad_17:partition-knapsack.pdf | PDF}} [[https://repl.it/@grossiroberto/knapsack|code]] | |
| | |17.04.2019| Case study on approximation for graphs (max cut): single individual haplotypes reconstruction problem (HapCUT) | {{ :magistraleinformatica:ad:ad_18:hapcut.pdf |}} {{ :magistraleinformatica:ad:ad_18:bio.pdf |}}| |
| | |30.04.2019| NP-hard problems: heuristics based on dynamic programming; approximation algorithms. Case study: knapsack problem. | [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/book/chapter02.pdf| chapt.2: par. 2.1.1]] [[https://repl.it/@grossiroberto/knapsack|code]] | |
| | |03.05.2019| NP-hard problems: counting version (#P) based on dynamic programming, uniform random sampling of the feasible solutions. Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] | |
| | |06.05.2019| Case study on approximation for metric k-center: Clustering and video summarization. | {{ :magistraleinformatica:ad:ad_18:clustering.pdf |}} {{ :magistraleinformatica:ad:ad_18:chapter2.pdf |}}| |
| | |07.05.2019| NP-hard problems: fully polynomial-time randomized approximation schemes (FPRASs). Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] | |
| | |10.05.2019| General inapproximability results. Case study: travel salesman problem (TSP). 2-approximation algorithms for metric TSP, Local search. Greedy. Case study: max cut for graphs. Non-existence of PTAS. | [CLRS 35.2] {{:magistraleinformatica:alg2:algo2_14:lec02.pdf|Notes}} | |
| | |13.05.2019| Randomized approximation and derandomization: universal hash functions; conditional expectations. Case study: max-cut for graphs. | [[http://pages.cs.wisc.edu/~jyc/02-810notes/lecture19.pdf|sect. 3-4]] [[http://web.cs.iastate.edu/~pavan/633/lec14.pdf|sect. 1.1]] | |
| | |14.05.2019| Case study on bottom-k sketches: approximate similarity searching | {{ :magistraleinformatica:ad:ad_18:06691730.pdf |}} {{ :magistraleinformatica:ad:ad_18:p371-thorup.pdf | only Sect.1}} {{ :magistraleinformatica:ad:ad_18:bio.pdf |}}| |
| | |17.05.2019| 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]] | |
| | |21.05.2019| 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]] | |
| | |22.05.2019| Case study on graphs: community detection is social networks | {{ :magistraleinformatica:ad:ad_18:sna.pdf |}} {{ :magistraleinformatica:ad:ad_18:nature03607.pdf |}} {{ :magistraleinformatica:ad:ad_18:nature03607-s1.pdf |}}| |
| | |24.05.2019| 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]]| |
| | |28.05.2019| Approximation in fine-grained algorithms and limitations. | {{ :magistraleinformatica:ad:ad_17:diameterapprox.pdf | notes }} | |
| | |
| | |
| |
| == Activity in class == | == Activity in class == |
