Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
Entrambe le parti precedenti la revisione Revisione precedente Prossima revisione | Revisione precedente Ultima revisione Entrambe le parti successive la revisione | ||
magistraleinformatica:alg2:algo2_12:start [17/01/2013 alle 06:04 (12 anni fa)] Roberto Grossi [Announcements] |
magistraleinformatica:alg2:algo2_12:start [24/10/2013 alle 09:26 (11 anni fa)] Roberto Grossi [Topics] |
||
---|---|---|---|
Linea 4: | Linea 4: | ||
==== Announcements ==== | ==== Announcements ==== | ||
- | * Calendario orali (venire comunque | + | |
- | | + | |
- | | + | |
- | * Examination dates: Dec. 20 at 9:30 (" | + | |
+ | * Examination dates: Dec. 20 at 9:30 (" | ||
* The class lectures will be (mainly) given in English. | * The class lectures will be (mainly) given in English. | ||
==== Overview ==== | ==== Overview ==== | ||
Linea 47: | Linea 48: | ||
| Nov. 13| Problem solving. Count-Min Sketch. Cuckoo hashing.| {{: | | Nov. 13| Problem solving. Count-Min Sketch. Cuckoo hashing.| {{: | ||
| Nov. 14| Class canceled.| [[http:// | | Nov. 14| Class canceled.| [[http:// | ||
- | | Nov. 16| Bloom filters. Design parameters and probabilistic analysis, with applications.| {{: | + | | Nov. 16| Bloom filters. Design parameters and probabilistic analysis, with applications.| {{: |
| Nov. 20| Problem solving. Count-Min Sketch for interval queries and inner product.| [[http:// | | Nov. 20| Problem solving. Count-Min Sketch for interval queries and inner product.| [[http:// | ||
| Nov. 21| Randomized quicksort. Skiplists. Randomized binary search trees.| {{: | | Nov. 21| Randomized quicksort. Skiplists. Randomized binary search trees.| {{: | ||
Linea 57: | Linea 58: | ||
== Hard problems == | == Hard problems == | ||
- | | Dec. 7| NP-Hard problems. Approximation algorithms. Traveling Salesman Problem (TSP): hardness of approximation and 2-approximation for metric instances.| {{: | + | | Dec. 7| NP-Hard problems. Approximation algorithms. Traveling Salesman Problem (TSP): hardness of approximation and 2-approximation for metric instances.| {{: |
- | | Dec. 11| Further examples: approximation for Maximal independent sets (MIS) and Vertex Cover (VC).| | + | | Dec. 11| Further examples: approximation for Maximum Independent Set (MIS) and Vertex Cover (VC).| |
| Dec. 14| Knapsack problem: bad example for greedy and its refinement for 2-approximation. Approximation for Min Bin Packing using Next Fit and First Fit Decreasing strategies.| [[http:// | | Dec. 14| Knapsack problem: bad example for greedy and its refinement for 2-approximation. Approximation for Min Bin Packing using Next Fit and First Fit Decreasing strategies.| [[http:// | ||
| Dec. 18| Problem solving. Distinct elements in a stream and general discussion of the exercises presented during the semester.| | | | Dec. 18| Problem solving. Distinct elements in a stream and general discussion of the exercises presented during the semester.| | | ||
Linea 72: | Linea 73: | ||
== Exams == | == Exams == | ||
+ | |||
+ | 05.02.2013 (visione della correzione: mercoledì 06.02.2013 dalle 9:00 alle 11:30): | ||
+ | |||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
15.01.2013 (visione della correzione: venerdì 18.1.2013 ore 9:00): | 15.01.2013 (visione della correzione: venerdì 18.1.2013 ore 9:00): |