magistraleinformatica:ad:ad_19: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_19:start [27/03/2020 alle 16:57 (5 anni fa)] – Roberto Grossi | magistraleinformatica:ad:ad_19:start [07/07/2020 alle 07:59 (5 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:// | + | - Join the class on Google Classroom (use Android/iOS or connect to the [[https:// |
- Click on the link for streaming on [[https:// | - Click on the link for streaming on [[https:// | ||
Linea 53: | Linea 53: | ||
=== Randomization, | === Randomization, | ||
- | Randomization is a powerful tool to solve large-scale problems. After introducing the concept of randomized algorithms and hashing, we consider some applications, | + | Randomization is a powerful tool to solve large-scale problems. After introducing the concept of randomized algorithms and hashing, we consider some applications, |
^ Date ^ Topics ^ References and notes ^ | ^ Date ^ Topics ^ References and notes ^ | ||
Linea 67: | Linea 67: | ||
|13.03.2020| Multiplicative universal hashing.| [[https:// | |13.03.2020| Multiplicative universal hashing.| [[https:// | ||
|17.03.2020| Data streaming and sketching algorithms: approximate counters (part 1).| [[https:// | |17.03.2020| Data streaming and sketching algorithms: approximate counters (part 1).| [[https:// | ||
- | |19.03.2020| Case study on hashing: rsync and file synchronization using hash functions.| {{ : | + | |19.03.2020| Case study on hashing: rsync and file synchronization using hash functions |
|20.03.2020| Sketching algorithms: approximate | |20.03.2020| Sketching algorithms: approximate | ||
|24.03.2020| Sketching algorithms: approximate | |24.03.2020| Sketching algorithms: approximate | ||
|26.03.2020| Flajolet-Martin sketches for counting distinct elements.| [[https:// | |26.03.2020| Flajolet-Martin sketches for counting distinct elements.| [[https:// | ||
|27.03.2020| Count-Min sketches for frequent elements.| {{http:// | |27.03.2020| Count-Min sketches for frequent elements.| {{http:// | ||
+ | |31.03.2020| Integer counters and range queries with Count-Min Sketches: implementation and analysis. | {{https:// | ||
+ | |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:// | ||
+ | |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:// | ||
+ | |21.04.2020| Approximation in fine-grained algorithms and limitations. Case study: diameter in undirected unweighted graphs. | {{ : | ||
+ | |23.04.2020| Networked data and randomized min-cut algorithm for graphs. | {{: | ||
+ | |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< | ||
+ | |28.04.2019| NP-hard problems: heuristics based on dynamic programming; | ||
+ | |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, | ||
+ | |07.05.2020| NP-hard problems: fully polynomial-time randomized approximation schemes (FPRASs). Case study: #knapsack problem. | {{ : | ||
+ | |12.05.2020| General inapproximability results. Case study: travel salesman problem (TSP). | ||
+ | |14.05.2020| Randomized approximation and derandomization: | ||
+ | |15.05.2020| Fixed-parameter tractable (FPT) algorithms. Kernelization. Bounded search tree. Case study: min-vertex cover in graphs. | ||
+ | |19.05.2020| Randomized FPT algorithms: color coding and randomized separation. Case study: longest path in graphs and subgraph isomorphism. | [[https:// | ||
+ | |||
== 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:// | ||
+ | * Access to the [[https:// | ||
magistraleinformatica/ad/ad_19/start.1585328227.txt.gz · Ultima modifica: 27/03/2020 alle 16:57 (5 anni fa) da Roberto Grossi