| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| magistraleinformatica:ad:ad_18:start [10/04/2019 alle 12:21 (6 anni fa)] – [Topics] Roberto Grossi | magistraleinformatica:ad:ad_18:start [24/04/2020 alle 07:13 (4 anni fa)] (versione attuale) – Roberto Grossi |
|---|
| |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| Case study on data streams (I): probabilistic counting. | {{ :magistraleinformatica:ad:ad_18:data-stream-stats.pdf |slides}} {{ :magistraleinformatica:ad:ad_18:cms.zip | code}} | | |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| 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}} | | |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 == |
