DidaWiki

Strumenti Utente

Strumenti Sito

Ti trovi qui: DidaWiki » Corso di Laurea Magistrale in Informatica » Algorithm Design » Year 2019-2020
magistraleinformatica:ad:ad_19: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 revisione Revisione precedente
Prossima revisione 		Revisione precedente
magistraleinformatica:ad:ad_19:start [27/03/2020 alle 16:56 (4 anni fa)]
Roberto Grossi 		magistraleinformatica:ad:ad_19:start [07/07/2020 alle 07:59 (4 anni fa)] (versione attuale)
Roberto Grossi
Linea 11: Linea 11:
 You student, what can you do next for getting a lecture?  You student, what can you do next for getting a lecture? 
  
-  - Join the class on **Google Classroom** (use Android/iOS or connect to the [[https://classroom.google.com/u/1/c/NjI0NjI4NjExNzRa|Algorithm Design link]]), and use the code below: {{:magistraleinformatica:ad:ad_19:code.jpg?400|}}\\ \\  +  - Join the class on Google Classroom (use Android/iOS or connect to the [[https://classroom.google.com/u/1/c/NjI0NjI4NjExNzRa|Algorithm Design link]]).  
   - Click on the link for streaming on [[https://meet.google.com/rco-fojo-cqn|Google Meet]] for attending the classes. Please note that we //keep our schedule for time//, the only difference is that you have connect to the link instead of physically coming to the room.   - Click on the link for streaming on [[https://meet.google.com/rco-fojo-cqn|Google Meet]] for attending the classes. Please note that we //keep our schedule for time//, the only difference is that you have connect to the link instead of physically coming to the room.
  
Linea 53: Linea 53:
 === Randomization, hashing and data streaming === === Randomization, hashing and data streaming ===
  
-Randomization is a powerful tool to solve large-scale problems. After introducing the concept of randomized algorithms and hashing, we consider some applications, such as data streaming algorithms, a field emerged in the last decade. Here data flow as a stream and one-pass algorithms with limited memory can process it. We focus on the count-min sketch paradigm and its applications. [Note: to refresh the basic notions on counting and probability, please refer to Appendix C in Cormen-Leiserson-Rivest-Stein's book "Introduction to Algorithms", 3rd ed., MIT Press.]+Randomization is a powerful tool to solve large-scale problems. After introducing the concept of randomized algorithms and hashing, we consider some applications, such as data streaming algorithms, a field emerged in the last decade. Here data flow as a stream and one-pass algorithms with limited memory can process it. We focus on the count-min sketch paradigm and its applications. [Note: to refresh the basic notions on counting and probability, please refer to Appendix C in Cormen-Leiserson-Rivest-Stein's book "Introduction to Algorithms", 3rd ed., MIT Press. Concentration bounds are explained in these [[http://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf|class notes]].]
  
 ^ Date ^ Topics ^ References and notes ^ ^ Date ^ Topics ^ References and notes ^
Linea 66: Linea 66:
 |12.03.2020| Distributed server and load balancing through hashing (continued). | [[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]] | |12.03.2020| Distributed server and load balancing through hashing (continued). | [[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]] |
 |13.03.2020| Multiplicative universal hashing.| [[https://arxiv.org/abs/1504.06804|Sect. 2.3]]| |13.03.2020| Multiplicative universal hashing.| [[https://arxiv.org/abs/1504.06804|Sect. 2.3]]|
-|17.03.2020| Sketching algorithms: approximate counters (part 1).| [[https://www.sketchingbigdata.org/fall17/lec/lec1.pdf|Sect. 3-5]]| +|17.03.2020| Data streaming and sketching algorithms: approximate counters (part 1).| [[https://www.sketchingbigdata.org/fall17/lec/lec1.pdf|Sect. 3-5]]| 
-|19.03.2020| Case study on hashing: rsync and file synchronization using hash functions.| {{ :magistraleinformatica:ad:ad_19:20200319.pdf |slides }}|+|19.03.2020| Case study on hashing: rsync and file synchronization using hash functions (seminar by F.Geraci).| classroom drive|
 |20.03.2020| Sketching algorithms: approximate  counters (part 2).| [[https://www.sketchingbigdata.org/fall17/lec/lec1.pdf|Sect. 3-5]]| |20.03.2020| Sketching algorithms: approximate  counters (part 2).| [[https://www.sketchingbigdata.org/fall17/lec/lec1.pdf|Sect. 3-5]]|
 |24.03.2020| Sketching algorithms: approximate  counters (part 3).| [[https://www.sketchingbigdata.org/fall17/lec/lec1.pdf|Sect. 3-5]]| |24.03.2020| Sketching algorithms: approximate  counters (part 3).| [[https://www.sketchingbigdata.org/fall17/lec/lec1.pdf|Sect. 3-5]]|
 |26.03.2020| Flajolet-Martin sketches for counting distinct elements.| [[https://www.cse.cuhk.edu.hk/~taoyf/course/wst501/notes/lec4.pdf|notes]]| |26.03.2020| Flajolet-Martin sketches for counting distinct elements.| [[https://www.cse.cuhk.edu.hk/~taoyf/course/wst501/notes/lec4.pdf|notes]]|
 |27.03.2020| 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]]| |27.03.2020| 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]]|
 +|31.03.2020| Integer counters and range queries with Count-Min Sketches: implementation and analysis. | {{https://7797b024-a-62cb3a1a-s-sites.googlegroups.com/site/countminsketch/cm-latin.pdf| sects.3-4}} |
 +|02.04.2020| Data stream statistics - part 1 (seminar by F.Geraci)| classroom drive|
 +|03.04.2020| 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]]|
 +|07.04.2020|Unifying view of sketches: min-k, bottom-k, threshold-t. Jaccard example. | classroom drive |
 +|09.04.2020|Distance distribution in networks: approximation with random sampling and sketches| classroom drive |
 +|16.04.2020| Data stream statistics - part 2 (seminar by F.Geraci). | classroom drive|
 +|17.04.2020| 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]]|
 +|21.04.2020| Approximation in fine-grained algorithms and limitations. Case study: diameter in undirected unweighted graphs. | {{ :magistraleinformatica:ad:ad_17:diameterapprox.pdf | notes }} |
 +|23.04.2020| Networked data and randomized min-cut algorithm for graphs. | {{:magistraleinformatica:alg2:algo2_15:mincut1.pdf| par.1.1}} |
 +|24.04.2020| 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]] |
 +|28.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]]  |
 +|30.04.2019| Clique-based social network analysis (seminar by F.Geraci) | classroom drive |
 +|05.05.2020| 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]] |
 +|07.05.2020| 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]] |
 +|12.05.2020| 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}} |
 +|14.05.2020| 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]] |
 +|15.05.2020| 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]] |
 +|19.05.2020| 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]] |
 +
  
 == Activity in class == == Activity in class ==
  
   * The screen snapshots shown during the classes are available in the Google Classroom shared drive.   * The screen snapshots shown during the classes are available in the Google Classroom shared drive.
 +
 +== Official documents for the course ==
 +
 +  * Access to [[https://unimap.unipi.it/registri/printregistriNEW.php?re=3297601::::&ri=9172|unimap log (registro delle lezioni)]].
 +  * Access to the [[https://esami.unipi.it/esami/|course evaluation form (questionario studenti)]].
  
  
magistraleinformatica/ad/ad_19/start.1585328181.txt.gz · Ultima modifica: 27/03/2020 alle 16:56 (4 anni fa) da Roberto Grossi

Strumenti Pagina

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki