Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
magistraleinformatica:ad:ad_17:start [27/12/2017 alle 15:07 (7 anni fa)] – [Topics] Roberto Grossi | magistraleinformatica:ad:ad_17:start [03/09/2018 alle 22:02 (7 anni fa)] (versione attuale) – [Schedule] Roberto Grossi |
---|
==== Schedule ==== | ==== Schedule ==== |
| |
| * Regarding your exam planning: I'll be on leave during 19.09.18-15.10.18 and 01.11.2018-28.02.19. |
* Timetable: [[https://www.di.unipi.it/en/education/mcs/timetable-wif/myschedule-wif?courses%5B%5D=58926_u&cds=WIF-LM&dip=Informatica&test=10&sem=1&anno=2017#|weekly timetable]] with changes: (Oct.5 -> Oct.4, 14-16, I-Lab); (Oct.9 -> Oct.2, 14-16, room A1); (Oct.10 -> Oct.23, 14-16, room A1). | * Timetable: [[https://www.di.unipi.it/en/education/mcs/timetable-wif/myschedule-wif?courses%5B%5D=58926_u&cds=WIF-LM&dip=Informatica&test=10&sem=1&anno=2017#|weekly timetable]] with changes: (Oct.5 -> Oct.4, 14-16, I-Lab); (Oct.9 -> Oct.2, 14-16, room A1); (Oct.10 -> Oct.23, 14-16, room A1). |
* Office hours: Thu. 14-17 or by appointment. | * Office hours: Thu. 14-17 or by appointment. |
| |
==== Overview ==== | ==== Overview ==== |
| |
==== Exams ==== | ==== Exams ==== |
| |
Written exam: | //Written exam:// |
- choose one of the topics discussed in class | - choose one of the topics discussed in class |
- write a very short to-do list and ask the instructor for approval | - write a very short to-do list and ask the instructor for approval |
| |
Suggested reading: [[http://www.ittc.ku.edu/~jsv/Papers/Vitwritingnotes.pdf|some useful tips for scientific writing in English]] (first two sections) by J.S. Vitter. | Suggested reading: [[http://www.ittc.ku.edu/~jsv/Papers/Vitwritingnotes.pdf|some useful tips for scientific writing in English]] (first two sections) by J.S. Vitter. |
| |
| Example of interaction: [[.interaction:|student and instructor]] discussing the report's content and structure. |
| |
| |
Oral examination: topics discussed in class, please read the references in the notes. | //Oral exam:// topics discussed in class, please read the references in the notes. |
==== Topics ==== | ==== Topics ==== |
| |
|26.09.2017| 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]]| | |26.09.2017| 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]]| |
|28.09.2017| 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]]| | |28.09.2017| 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]]| |
|02.10.2017| Case study: rsync and file synchronization using hash functions | {{ :magistraleinformatica:ad:ad_17:rsync.pdf |slides}} [[https://en.wikipedia.org/wiki/Rsync|wikipedia]] | | |02.10.2017| Case study on hashing: rsync and file synchronization using hash functions | {{ :magistraleinformatica:ad:ad_17:rsync.pdf |slides}} [[https://en.wikipedia.org/wiki/Rsync|wikipedia]] | |
|02.10.2017| Data Streaming algorithms. Motivations and examples. Count-Min Sketches | {{https://7797b024-a-62cb3a1a-s-sites.googlegroups.com/site/countminsketch/cm-latin.pdf| sects.1-3}} [[https://sites.google.com/site/countminsketch/|Site]] {{:magistraleinformatica:alg2:algo2_12:count-min-sketch.pdf|Notes}} [[https://repl.it/Lvob/3|code]]| | |02.10.2017| Data Streaming algorithms. Motivations and examples. Count-Min Sketches | {{https://7797b024-a-62cb3a1a-s-sites.googlegroups.com/site/countminsketch/cm-latin.pdf| sects.1-3}} [[https://sites.google.com/site/countminsketch/|Site]] {{:magistraleinformatica:alg2:algo2_12:count-min-sketch.pdf|Notes}} [[https://repl.it/Lvob/3|code]]| |
|03.10.2017| Queries with Count-Min Sketches: implementation and analysis. | {{https://7797b024-a-62cb3a1a-s-sites.googlegroups.com/site/countminsketch/cm-latin.pdf| sects.3-4}} {{:magistraleinformatica:ad:ad_17:20171003.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_12:count-min-sketch-median.pdf|Notes (optional)}} | | |03.10.2017| Queries with Count-Min Sketches: implementation and analysis. | {{https://7797b024-a-62cb3a1a-s-sites.googlegroups.com/site/countminsketch/cm-latin.pdf| sects.3-4}} {{:magistraleinformatica:ad:ad_17:20171003.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_12:count-min-sketch-median.pdf|Notes (optional)}} | |
|04.10.2017| 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]]| | |04.10.2017| 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]]| |
|19.10.2017| Case study: document tagging and perfect hashing.| {{ :magistraleinformatica:ad:ad_17:tagger.tgz | code }} | | |19.10.2017| Case study on hashing: document tagging and perfect hashing.| {{ :magistraleinformatica:ad:ad_17:tagger.tgz | code }} | |
|23.10.2017| Networked data and randomized min-cut algorithm for graphs. | {{:magistraleinformatica:alg2:algo2_15:mincut1.pdf| par.1.1}} | | |23.10.2017| Networked data and randomized min-cut algorithm for graphs. | {{:magistraleinformatica:alg2:algo2_15:mincut1.pdf| par.1.1}} | |
|23.10.2017| Proxy caches and dictionaries with errors: Bloom filters. | {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|Survey: except par.2.5-2.6 (optional: par.2.2)}} | | |23.10.2017| Proxy caches and dictionaries with errors: Bloom filters. | {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|Survey: except par.2.5-2.6 (optional: par.2.2)}} | |
|24.10.2017| Randomness in data. Kolmogorov complexity. Generating random sequences and permutations (exercise: subsets). | [[http://www.eecs.berkeley.edu/~luca/cs172/notek.pdf|Notes]] [[http://www.1stworks.com/ref/ruskeycombgen.pdf|Sect. 5.4]] | | |24.10.2017| Randomness in data. Kolmogorov complexity. Generating random sequences and permutations (exercise: subsets). | [[http://www.eecs.berkeley.edu/~luca/cs172/notek.pdf|Notes]] [[http://www.1stworks.com/ref/ruskeycombgen.pdf|Sect. 5.4]] | |
|26.10.2017| Generating random trees. Models for generating random graphs: Erdős-Rényi-Gilbert G(n,p), Barabási–Albert preferential attachment, Watts–Strogatz small world, configuration model. | [[http://www.1stworks.com/ref/ruskeycombgen.pdf|Sect. 5.5]] [[http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf| Sect. 1.1-1.3 (optional 1.5-1.6), 4,1 (till pag.126), 7.1-7.2, 8.1]] | | |26.10.2017| Generating random trees. Models for generating random graphs: Erdős-Rényi-Gilbert G(n,p), Barabási–Albert preferential attachment, Watts–Strogatz small world, configuration model. | [[http://www.1stworks.com/ref/ruskeycombgen.pdf|Sect. 5.5]] [[http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf| Sect. 1.1-1.3 (optional 1.5-1.6), 4,1 (till pag.126), 7.1-7.2, 8.1]] | |
|06.11.2017| Case study: data stream analytics (part 1). | {{ :magistraleinformatica:ad:ad_17:data-stream-stats.pdf |notes}} | | |06.11.2017| Case study on data stream: statistics and analytics (part 1). | {{ :magistraleinformatica:ad:ad_17:data-stream-stats.pdf |notes}} | |
|07.11.2017| Distributed server and load balancing through hashing: revisited | [[https://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesF15/hashing.pdf|Sect.7 and 8.1]] | | |07.11.2017| Distributed server and load balancing through hashing: revisited | [[https://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesF15/hashing.pdf|Sect.7 and 8.1]] | |
|09.11.2017| The power of two random choices: Cuckoo hashing.| {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_16:cuckoohashinsertion.pdf|Notes}} [[https://repl.it/NzGN/3|code]]| | |09.11.2017| The power of two random choices: Cuckoo hashing.| {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_16:cuckoohashinsertion.pdf|Notes}} [[https://repl.it/NzGN/3|code]]| |
|13.11.2017| Case study: data stream analytics (part 2). | {{ :magistraleinformatica:ad:ad_17:data-stream-stats2.pdf |notes}} [[https://repl.it/@geraci/Min-Hash-estimate|code]]| | |13.11.2017| Case study on data stream: statistics and analytics (part 2). | {{ :magistraleinformatica:ad:ad_17:data-stream-stats2.pdf |notes}} [[https://repl.it/@geraci/Min-Hash-estimate|code]]| |
| |
=== Enumeration, hardness and approximation of some combinatorial problems === | === Enumeration, hardness and approximation of some combinatorial problems === |
|14.11.2017| 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]] | | |14.11.2017| 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]] | |
|16.11.2017| NP-hard problems: branch and bound algorithms; fully polynomial-time approximation schemes (FPTASs). Case study: knapsack problem. | {{ :magistraleinformatica:ad:ad_17:vazirani_knapsack.pdf |ch.8}} {{ :magistraleinformatica:ad:ad_17:NotesKnapsack1.pdf | notes}} [[https://repl.it/@grossiroberto/approxKnapsack|code]] | | |16.11.2017| NP-hard problems: branch and bound algorithms; fully polynomial-time approximation schemes (FPTASs). Case study: knapsack problem. | {{ :magistraleinformatica:ad:ad_17:vazirani_knapsack.pdf |ch.8}} {{ :magistraleinformatica:ad:ad_17:NotesKnapsack1.pdf | notes}} [[https://repl.it/@grossiroberto/approxKnapsack|code]] | |
|20.11.2017| TBD | TBA| | |20.11.2017| Case study on bottom-k sketches: approximate similarity searching of large collections of images | [[http://image.diku.dk/igel/paper/NNCUBkS.pdf|paper]]| |
|21.11.2017| NP-hard problems: counting version (#P) based on dynamic programming, uniform random sampling of the feasible solutions; fully polynomial-time randomized approximation schemes (FPRASs). Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] | | |21.11.2017| NP-hard problems: counting version (#P) based on dynamic programming, uniform random sampling of the feasible solutions; fully polynomial-time randomized approximation schemes (FPRASs). Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] | |
|23.11.2017| General inapproximability results. Case study: travel salesman problem (TSP). 2-approximation algorithm . | [CLRS 35.2] | | |23.11.2017| General inapproximability results. Case study: travel salesman problem (TSP). 2-approximation algorithm . | [CLRS 35.2] | |
|27.11.2017| Case study on approximation for metric k-center: Clustering and video summarization. | [[https://www.dropbox.com/s/mvomtclqs97vx26/27-11.pdf?dl=0|slides]] [[https://www.dropbox.com/s/aeowxkt6p8iximx/chapter2.pdf?dl=0|notes]] | | |27.11.2017| Case study on approximation for metric k-center: Clustering and video summarization. | [[https://www.dropbox.com/s/mvomtclqs97vx26/27-11.pdf?dl=0|slides]] [[https://www.dropbox.com/s/aeowxkt6p8iximx/chapter2.pdf?dl=0|notes]] | |
|28.11.2017| Non-existence of PTAS. Local search. Greedy. Case study: max-cut for graphs. | TBD | | |28.11.2017| Non-existence of PTAS. Local search. Greedy. Case study: max cut for graphs. | {{:magistraleinformatica:alg2:algo2_14:lec02.pdf|Notes}} | |
|30.11.2017| Randomized approximation. Derandomization: universal hash functions; conditional expectations. Case study: max-cut for graphs. | TBD | | |30.11.2017| Randomized approximation. 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]] | |
|04.12.2017| Case study on approximation for graphs (max cut): single individual haplotypes reconstruction problem (hapcut) |[[https://tinyurl.com/yak7p2w7|paper]] | | |04.12.2017| Case study on approximation for graphs (max cut): single individual haplotypes reconstruction problem (hapcut) |[[https://tinyurl.com/yak7p2w7|paper]] | |
|05.12.2017| Parameterization in algorithms. Kernelization. Bounded search tree. Case study: min-vertex cover in graphs. | TBD | | |05.12.2017| 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]] | |
|07.12.2017| Fixed-parameter tractable (FPT) algorithms. Randomized FPT algorithms: color coding and randomized separation. Case study: longest path in graphs and subgraph isomorphism. | TBD | | |07.12.2017| 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.12.2017| Fine-grained algorithms. SETH conjecture and conditional lower bounds. Guaranteed heuristics. Case study: diameter in undirected unweighted graphs. | TBD | | |11.12.2017| Class canceled for weather alert. | - | |
|14.12.2017| Approximation in fine-grained algorithms and limitations. Case study: diameter in undirected unweighted graphs. Communities detection in large graphs.| {{ :magistraleinformatica:ad:ad_17:diameterapprox.pdf | notes }} [[https://www.nature.com/articles/nature03607.pdf|paper]] [[https://images.nature.com/original/nature-assets/nature/journal/v435/n7043/extref/nature03607-s1.pdf|supplement]] | | |12.12.2017| 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]]| |
| |14.12.2017| Approximation in fine-grained algorithms and limitations. Case study: diameter in undirected unweighted graphs. Case study: communities detection in large graphs.| {{ :magistraleinformatica:ad:ad_17:diameterapprox.pdf | notes }} [[https://www.nature.com/articles/nature03607.pdf|paper]] [[https://images.nature.com/original/nature-assets/nature/journal/v435/n7043/extref/nature03607-s1.pdf|supplement]] | |
| |
== Activity in class == | == Activity in class == |