magistraleinformatica:ad:ad_17:start
Differenze
Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente | ||
magistraleinformatica:ad:ad_17:start [27/12/2017 alle 16:01 (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 | ||
---|---|---|---|
Linea 11: | Linea 11: | ||
==== 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:// | * Timetable: [[https:// | ||
* Office hours: Thu. 14-17 or by appointment. | * Office hours: Thu. 14-17 or by appointment. | ||
- | |||
==== Overview ==== | ==== Overview ==== | ||
Linea 20: | Linea 20: | ||
==== 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 | ||
Linea 30: | Linea 30: | ||
Suggested reading: [[http:// | Suggested reading: [[http:// | ||
+ | |||
+ | Example of interaction: | ||
- | 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 ==== | ||
Linea 54: | Linea 56: | ||
|26.09.2017| Virus scan and stream analysis with Karp-Rabin fingerprints: | |26.09.2017| Virus scan and stream analysis with Karp-Rabin fingerprints: | ||
|28.09.2017| Dictionary of keywords. Quick review of classical hashing. Universal hashing. Markov' | |28.09.2017| Dictionary of keywords. Quick review of classical hashing. Universal hashing. Markov' | ||
- | |02.10.2017| Case study: rsync and file synchronization using hash functions | {{ : | + | |02.10.2017| Case study on hashing: rsync and file synchronization using hash functions | {{ : |
|02.10.2017| Data Streaming algorithms. Motivations and examples. Count-Min Sketches | {{https:// | |02.10.2017| Data Streaming algorithms. Motivations and examples. Count-Min Sketches | {{https:// | ||
|03.10.2017| Queries with Count-Min Sketches: implementation and analysis. | {{https:// | |03.10.2017| Queries with Count-Min Sketches: implementation and analysis. | {{https:// | ||
|04.10.2017| Document resemblance with MinHash, k-sketches and the Jaccard similarity index. Azuma-Hoeffding bound. | [[http:// | |04.10.2017| Document resemblance with MinHash, k-sketches and the Jaccard similarity index. Azuma-Hoeffding bound. | [[http:// | ||
- | |19.10.2017| Case study: document tagging and perfect hashing.| {{ : | + | |19.10.2017| Case study on hashing: document tagging and perfect hashing.| {{ : |
|23.10.2017| Networked data and randomized min-cut algorithm for graphs. | {{: | |23.10.2017| Networked data and randomized min-cut algorithm for graphs. | {{: | ||
|23.10.2017| Proxy caches and dictionaries with errors: Bloom filters. | {{: | |23.10.2017| Proxy caches and dictionaries with errors: Bloom filters. | {{: | ||
|24.10.2017| Randomness in data. Kolmogorov complexity. Generating random sequences and permutations (exercise: subsets). | [[http:// | |24.10.2017| Randomness in data. Kolmogorov complexity. Generating random sequences and permutations (exercise: subsets). | [[http:// | ||
|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:// | |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:// | ||
- | |06.11.2017| Case study: data stream analytics (part 1). | {{ : | + | |06.11.2017| Case study on data stream: statistics and analytics (part 1). | {{ : |
|07.11.2017| Distributed server and load balancing through hashing: revisited | [[https:// | |07.11.2017| Distributed server and load balancing through hashing: revisited | [[https:// | ||
|09.11.2017| The power of two random choices: Cuckoo hashing.| {{: | |09.11.2017| The power of two random choices: Cuckoo hashing.| {{: | ||
- | |13.11.2017| Case study: data stream analytics (part 2). | {{ : | + | |13.11.2017| Case study on data stream: statistics and analytics (part 2). | {{ : |
=== Enumeration, | === Enumeration, | ||
Linea 82: | Linea 84: | ||
|23.11.2017| General inapproximability results. Case study: travel salesman problem (TSP). | |23.11.2017| General inapproximability results. Case study: travel salesman problem (TSP). | ||
|27.11.2017| Case study on approximation for metric k-center: Clustering and video summarization. | [[https:// | |27.11.2017| Case study on approximation for metric k-center: Clustering and video summarization. | [[https:// | ||
- | |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. | {{: |
- | |30.11.2017| Randomized approximation. Derandomization: | + | |30.11.2017| Randomized approximation. Derandomization: |
|04.12.2017| Case study on approximation for graphs (max cut): single individual haplotypes reconstruction problem (hapcut) |[[https:// | |04.12.2017| Case study on approximation for graphs (max cut): single individual haplotypes reconstruction problem (hapcut) |[[https:// | ||
- | |05.12.2017| Fixed-parameter tractable (FPT) algorithms. Kernelization. Bounded search tree. Case study: min-vertex cover in graphs. | + | |05.12.2017| Fixed-parameter tractable (FPT) algorithms. Kernelization. Bounded search tree. Case study: min-vertex cover in graphs. |
- | |07.12.2017| 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:// |
- | |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. | + | |12.12.2017| Fine-grained algorithms. SETH conjecture and conditional lower bounds. Guaranteed heuristics. Case study: diameter in undirected unweighted graphs. | [[https:// |
+ | |14.12.2017| Approximation in fine-grained algorithms and limitations. Case study: diameter in undirected unweighted graphs. | ||
== Activity in class == | == Activity in class == |
magistraleinformatica/ad/ad_17/start.1514390465.txt.gz · Ultima modifica: 27/12/2017 alle 16:01 (7 anni fa) da Roberto Grossi