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 2022-2023 ======

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


==== Announcements ====

  * The course will start on Feb. 22, 2023.

==== Schedule (work in progress) ====

  * Class hours: Mon 09‑11 (Fib-X1), Wed 09‑11 (Fib-L1), Fri 11-13 (Fib-L1)
  * MS Teams [[https://teams.microsoft.com/l/team/19%3amWvI5qL16To4yNegbZnOQ9KzD-kxZt6-XxE8jQHRTiQ1%40thread.tacv2/conversations?groupId=6f5050cd-97ff-4f93-bb90-e289c61479f4&tenantId=c7456b31-a220-47f5-be52-473828670aa1|channel here]], please subscribe
  * Office hours: remotely 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:// weekly hands-on in classroom (attendance is highly suggested).


//Oral exam:// topics discussed in class, please read the references in the notes.


//Syllabus:// [[https://unimap.unipi.it/registri/printregistriNEW.php?re=7084480:::&ri=9172|programma d'esame]]


==== Topics ====

  * Please see the topics listed below. Handouts are are available in the MS Teams channel.

== Activity in class ==

  * The screen snapshots shown during the classes are available in the MS Teams channel.

== Official forms for the course ==

  * Access to the [[https://esami.unipi.it/esami/|course evaluation form (questionario studenti)]] before taking examination.


==== Class schedule ====


^ Date ^ Topics ^ References and notes ^
|22.02.2023 | Introduction to the class. Course organization, schedule, and purpose. | |
|24.02.2023| 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]] |
|27.02.2023| 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]]|
|01.03.2023| Universal hashing. Markov's inequality. Perfect hashing.| [CLRS 11.2, 11.3.3, CLRS 11.5 ] [[https://repl.it/Ljuh/8|code]]|
|03.03.2023 | Weekly hands-on. | see Teams drive |
|06.03.2023 | Introduction to game theory. The theory of rational choice. Strategic games. The prisoner dilemma. Pollution game. Bach or Stravinsky. Matching Pennies. Stag hunt. (F. Geraci) | see Teams drive |
|08.03.2023 | Nash equilibrium. Review of example strategic games. Nash equilibrium of stag hunt with n players. Best response. Using best response to find the Nash equilibrium. (F. Geraci) | see Teams drive |
|10.03.2023 | Weekly hands-on. (F. Geraci) | see Teams drive |
|13.03.2023 | Game Theory. Improving and best response. Dominated actions. Vickrey auction (aka second price auction). Expected payoffs. (F. Geraci) | see Teams drive |
|15.03.2023 | Mixed strategy Nash equilibrium. Example: matching penny. Example: kicking penalty. Stable matching. (F. Geraci) | see Teams drive |
|17.03.2023 | Weekly hands-on. (F. Geraci) | see Teams drive |
|20.03.2023| 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]]|
|22.03.2023| Proxy caches and dictionaries with errors: Bloom filters. | {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|Survey: except par.2.5-2.6 (optional: par.2.2)}} |
|24.03.2023 | Weekly hands-on. | see Teams drive |
|27.03.2023| Space-efficient storage of sets with approximate memberships: upper and lower bounds. | {{ :magistraleinformatica:ad:ad_19:bloomcuckoorank.pdf | Notes (second part)}} |
|29.03.2023| 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]] |
|31.03.2023 | Weekly hands-on. | see Teams drive |
|03.04.2023| 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]]|
|05.04.2023| 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]]|
|14.04.2023 | Weekly hands-on. | see Teams drive |
|17.04.2023 | The data stream model. Cardinality estimation. Linear counting. LogLog counters. (F. Geraci) | see Teams drive |
|19.04.2023 | Bloom filters (probabilistic deletion and counting). Count min sketch. Heavy hitters. The space saving algorithm. (F. Geraci) | see Teams drive |
|21.04.2023 | Weekly hands-on. (F. Geraci) | see Teams drive |
|24.04.2023| Networked data and randomized min-cut algorithm for graphs. | {{:magistraleinformatica:alg2:algo2_15:mincut1.pdf| par.1.1}} |
|26.04.2023| Approximation in fine-grained algorithms and limitations. Case study: diameter in undirected unweighted graphs. | {{ :magistraleinformatica:ad:ad_17:diameterapprox.pdf | notes }} |
|03.05.2023| 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]]|
|08.05.2023| 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]] |
|10.05.2023| 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.05.2023| Local search, Greedy, Randomized: case study of max cut for graphs. | {{:magistraleinformatica:alg2:algo2_14:lec02.pdf|Notes}} |
|15.05.2023| NP-hard problems: download file manager and the knapsack problem. Dynamic programming algorithms for Knapsack: Case 1: integer weights, complexity O(nW). Case 2: integer values, complexity O(n<sup>2</sup>vmax). Examples.  General inapproximability results. Case study: travel salesman problem (TSP).  2-approximation algorithms for metric TSP. | [CLRS 35.2] [[https://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf|notes]] |
|17.05.2023| NP-hard problems: fully polynomial-time randomized approximation schemes (FPRASs). Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf|notes]] [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] |