DidaWiki

Strumenti Utente

Strumenti Sito

Ti trovi qui: DidaWiki » Corso di Laurea Magistrale in Informatica » Algoritmica 2 » Year 2012-2013
magistraleinformatica:alg2:algo2_12:start

Differenze

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

Link a questa pagina di confronto

Entrambe le parti precedenti la revisione Revisione precedente
Prossima revisione 		Revisione precedente
magistraleinformatica:alg2:algo2_12:start [17/01/2013 alle 06:04 (12 anni fa)]
Roberto Grossi [Announcements] 		magistraleinformatica:alg2:algo2_12:start [04/10/2015 alle 10:07 (9 anni fa)] (versione attuale)
Roberto Grossi
Linea 4: Linea 4:
 ==== Announcements ==== ==== Announcements ====
  
-  * Calendario orali (venire comunque per fissare anche le successive date fino al prossimo appello):  +  * 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: mer. 06.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.     * The class lectures will be (mainly) given in English.  
 ==== Overview ==== ==== 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. 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. 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. 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}}| | 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 == == 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. 2.1.2]]]  [[http://en.wikipedia.org/wiki/Vertex_cover| [Approximate evaluation of VC]]]|+| 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.| [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/book/chapter02.pdf| [chapt.2: par. 2.1.1, par. 2.2.2]]] | | 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.| | | Dec. 18| Problem solving. Distinct elements in a stream and general discussion of the exercises presented during the semester.| |
Linea 73: Linea 74:
 == Exams == == Exams ==
  
-15.01.2013 (visione della correzione: venerdì 18.1.2013 ore 9:00): +  * No more accessible
- +
-     407568    24 +
-     416420    29 +
-     437532    27 +
-     438125    26 +
-     439415    27 +
-     443495    28 +
-      +
- +
-20.12.2012 (visione della correzione: venerdì 11.1.2013 ore 11:00-13:00): +
- +
-     242180    25 +
-     303756    27 +
-     407947    28 +
-     409125    18 +
-     437532    22 +
-     437749    29 +
-     438125    21 +
-     438422    27 +
-     438591    24 +
-     439415    ins +
-     443065    29 +
-     443495    24 +
-     451371    28 +
-     452095    27 +
-     453278    25 +
-     454413    29 +
-     490104    25 +
-     490537    27 +
-      +
- +
magistraleinformatica/alg2/algo2_12/start.1358402654.txt.gz · Ultima modifica: 17/01/2013 alle 06:04 (12 anni fa) da Roberto Grossi

Strumenti Pagina

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki