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:01 (12 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 19: / Linea 20: @@
 We like students that make mistakes in a constructive way, since this is the starting point of our brainstorming to drive their reasoning paths, thus learning by mistakes. We are interested in the route that leads to the algorithmic solution, rather than the solution itself. Regarding mistakes and intelligence, Alan Turing wrote in 1947 that "... if a machine is expected to be infallible, it cannot also be intelligent". This is a motto for this class, and an invitation to express your own ideas even if they could be apparently wrong.
-==== Topics (in progress) ====
+==== Topics ====
 === Algorithms for massive data sets and hierarchical memories ===
@@ 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| .| |
+| 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| .| |
+| 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| .| |
+| 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 and general discussion of the exercises presented during the semester.| |
@@ Linea 67: / 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