Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- magistraleinformatica:alg2:algo2_12:start [14/01/2013 alle 10:58 (13 anni fa)] – Roberto Grossi
+++ magistraleinformatica:alg2:algo2_12:start [04/10/2015 alle 10:07 (10 anni fa)] (versione attuale) – Roberto Grossi
@@ Linea 4: / Linea 4: @@
 ==== Announcements ====
-  * Calendario orali (venire comunque per fissare anche le successive date di quel mese):
+  * Avviso: l'esame scritto del 12 luglio sarà gestito dalla prof.ssa Pagli.
-     * per il mese di gennaio: ven. 18.01.2013 ore 9:00 nello studio del docente;
+  * Calendario orali (contattare il docente per fissare una data specifica nel periodo indicato):
-     * per il mese di febbraio: lun. 11.02.2013 ore 9:00 nello studio del docente.
+     * dal 17.06.2013 al 4.07.2013;
-  * Examination dates: Dec. 20 at 9:30 ("compitino", aula C1), Jan. 15 at 9:30 (aula A), Feb. 5 at 9:30 (aula A).
+     * dal 22.07.2013 al 31.07.2013.
+  * Examination dates: Dec. 20 at 9:30 ("compitino", aula C1), Jan. 15 at 9:30 (aula A), Feb. 5 at 9:30 (aula A), Jun. 12 at 9:00 (Aula A), Jul. 12 at 9:00 (Aula A).
   * The class lectures will be (mainly) given in English.
 ==== Overview ====
@@ Linea 47: / Linea 48: @@
 | Nov. 13| Problem solving. Count-Min Sketch. Cuckoo hashing.| {{:magistraleinformatica:alg2:algo2_12:count-min-sketch-median.pdf|Notes}}|
 | Nov. 14| Class canceled.| [[http://www.mit.gov.it/mit/site.php?p=scioperi|Transportation strike]]|
-| Nov. 16| Bloom filters. Design parameters and probabilistic analysis, with applications.| {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|Survey}}|
+| Nov. 16| Bloom filters. Design parameters and probabilistic analysis, with applications.| {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|Survey: except par.2.5-2.6 (optional: par.2.2)}}|
 | Nov. 20| Problem solving. Count-Min Sketch for interval queries and inner product.| [[http://www.research.att.com/people/Cormode_Graham/library/publications/CormodeMuthukrishnan04CMJalg.pdf|Paper]]|
 | Nov. 21| Randomized quicksort. Skiplists. Randomized binary search trees.| {{:magistraleinformatica:alg2:algo2_10:randqs.pdf|[sez.2.5.4]}} {{:magistraleinformatica:alg2:algo2_11:skip.pdf|[sez.3.3]}} {{:magistraleinformatica:alg2:algo2_12:rbst.pdf|Paper (pages 288-302}}|
@@ Linea 57: / Linea 58: @@
 == Hard problems ==
-| Dec. 7| NP-Hard problems. Approximation algorithms. Traveling Salesman Problem (TSP): hardness of approximation and 2-approximation for metric instances.| {{:magistraleinformatica:alg2:algo2_10:dispensa_0.pdf|[chapt.9 (Italian)]}}|
+| Dec. 7| NP-Hard problems. Approximation algorithms. Traveling Salesman Problem (TSP): hardness of approximation and 2-approximation for metric instances.| {{:magistraleinformatica:alg2:algo2_10:dispensa_0.pdf|[chapt.9: par. 9.3-9.4 (Italian)]}}|
-| Dec. 11| Further examples: approximation for Maximal independent sets (MIS) and Vertex Cover (VC).|  [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/book/chapter02.pdf| [chapt.2: pp.39-40, par. 212]]  [[http://en.wikipedia.org/wiki/Vertex_cover| [wikipedia: item "Approximate evaluation"]]|
+| Dec. 11| Further examples: approximation for Maximum Independent Set (MIS) and Vertex Cover (VC).|  [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/book/chapter02.pdf| [chapt.2: pp.39-40, par. 2.1.2]]]  [[http://en.wikipedia.org/wiki/Vertex_cover| [Approximate evaluation of 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.| |
+| 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://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/book/chapter02.pdf| [chapt.2: par. 2.1.1, par. 2.2.2]]] |
-| Dec. 18| Problem solving. Distinct elements in a stream. 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.| |
-    * NP-completezza e approssimazione I {{:magistraleinformatica:alg2:algo2_10:dispensa_0.pdf|[cap.9]}} {{:magistraleinformatica:alg2:algo2_10:alg2_21-12.pdf|[appunti Dinelli]}}
-    * Approssimazione II [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/libro.html|[cap.2:pp.39-47, paragrafo 2.2.2]]]
-    *
 == Excercises discussed in class ==
@@ Linea 70: / Linea 68: @@
 {{:magistraleinformatica:alg2:algo2_12:esercitazioni2012.pdf| List of problems}} discussed during the problem solving session (in Italian).
-== Exams ==
+== Official class log (registro) ==
-.12.2012 (visione della correzione: venerdì 11.1.2013 ore 11:00-13:00):
+[[http://unimap.unipi.it/registri/printregistriNEW.php?re=89100:::&ri=9172| Registro su unimap]]
-    25
-    27
-    28
-    18
-    22
-    29
-    21
-    27
-    24
-    ins
-    29
-    24
-    28
-    27
-    25
-    29
-    25
-    27
+== Exams ==
+  * No more accessible