DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Year 2019-2020 ======

[[http://pages.di.unipi.it/grossi/|Prof. Roberto Grossi]]
[[http://webhost.services.iit.cnr.it/staff/filippo.geraci/|Dr. Filippo Geracii]]


==== Announcements ====

This week the teaching activity is suspended, as requested by our Rector. Hence the classes of March 5 and 6 are canceled. Next class is Tue, March 10, regular time, but lectures will be given in **streaming**. More details follow.

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]]).  
  - 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.


==== Schedule ====

  * Class hours: Tue 14:00‑16:00 (Fib N1), Thu 11:00‑13:00 (Fib L1), Fri 11:00‑13:00 (Fib N1)
  * Office hours: Fri 13:00-16:00 or by appointment.

==== Overview ====

The advanced nature of this course focuses on developing algorithmic design skills, exposing the students to complex problems that cannot be directly handled by standard libraries (being aware that several basic algorithms and data structures are already covered by the libraries of modern programming languages), thus requiring a significant effort in problem solving. These problems involve all basic data types, such as integers, strings, (geometric) points, trees and graphs as a starting point. The syllabus is structured to highlight the applicative situations in which the corresponding algorithms can be successfully employed, making references to software applications and libraries. The level of detail in each argument can change year-by-year, and will be decided according to requests coming from other courses in the curriculum and/or specific issues arising in, possibly novel, applicative scenarios. 


==== Exams ====

//Written exam://
  - choose one of the topics discussed in class
  - write a very short to-do list and ask the instructor for approval
  - if the instructor suggests some mods, modify the to-do list according to the instructor's comments and repeat step 2
  - if the chosen topic and the to-do list are approved, expand the to-do list into a more detailed to-do list and repeat step 3
  - make a written report in English and submit it to the instructor (recall to add at least 20% new content, when compared to what seen in class)
  - meet the instructor to read together the report and get some comments on it
  - make the necessary mods
  - use [[https://jupyterlab.readthedocs.io/en/stable/getting_started/installation.html|Jupyter Lab]] to prepare your report (so as to mix Markdown, LaTeX and Python code). More info inside Google Classroom.

{{:magistraleinformatica:ad:ad_19:python_environment.png?400|Credits XKCD https://xkcd.com/1987/}}


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 exam:// topics discussed in class, please read the references in the notes.
==== Topics ====

Caveat: Several topics are the outcomes of recent advancements in the field, and thus the course material mostly consists in research papers or book chapters. 


=== 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. Concentration bounds are explained in these [[http://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf|class notes]].]

^ Date ^ Topics ^ References and notes ^
|18.02.2020| 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]] |
|20.02.2020| 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]]|
|21.02.2020| Universal hashing. Markov's inequality. Perfect hashing.| [CLRS 11.2, 11.3.3, CLRS 11.5 ] [[https://repl.it/Ljuh/8|code]]|
|25.02.2020| Proxy caches and dictionaries with errors: Bloom filters. | {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|Survey: except par.2.5-2.6 (optional: par.2.2)}} |
|27.02.2020| 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]]|
|28.02.2020| Space-efficient implementation of Bloom filters using cuckoo hashing and succinct rank data structure. | {{ :magistraleinformatica:ad:ad_19:bloomcuckoorank.pdf | Notes (first part)}} |
|03.03.2020| Space-efficient storage of sets with approximate memberships: upper and lower bounds. | {{ :magistraleinformatica:ad:ad_19:bloomcuckoorank.pdf | Notes (second part)}} |
|10.03.2020| 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]] |
|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]]|
|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 (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]]|
|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]]|
|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 ==

  * 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)]].


== Spot yourself in the classroom ==

{{:magistraleinformatica:ad:ad_19:ad20192020.jpg?400|}}

{{:magistraleinformatica:ad:ad_19:ad201920_b.jpg?400|}}