Strumenti Utente

Strumenti Sito


magistraleinformatica:alg2:algo2_14: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_14:start [12/01/2015 alle 15:06 (9 anni fa)]
Roberto Grossi [Announcements]
magistraleinformatica:alg2:algo2_14:start [04/10/2015 alle 10:06 (9 anni fa)] (versione attuale)
Roberto Grossi
Linea 76: Linea 76:
 | Dec. 9| Notion of r-approximation algorithm. TSP: NP-hardness and difficulty of approximation. 2-approximation for metric TSP. | {{:magistraleinformatica:alg2:algo2_14:approxclrs.pdf| Except Sect.35.1}} | | Dec. 9| Notion of r-approximation algorithm. TSP: NP-hardness and difficulty of approximation. 2-approximation for metric TSP. | {{:magistraleinformatica:alg2:algo2_14:approxclrs.pdf| Except Sect.35.1}} |
 | Dec. 9| Problem solving (4 hours) | {{:magistraleinformatica:alg2:algo2_14:esercitazioni2014.pdf|list of problems}} | | Dec. 9| Problem solving (4 hours) | {{:magistraleinformatica:alg2:algo2_14:esercitazioni2014.pdf|list of problems}} |
-| Dec. 10| 2-approximation for MAX-CUT: local search, greedy. 2-approximation for minimum vertex cover. | [[http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec02.ps|Notes]]{{:magistraleinformatica:alg2:algo2_14:approxclrs.pdf| Sect.35.1}} |+| Dec. 10| 2-approximation for MAX-CUT: local search, greedy. 2-approximation for minimum vertex cover. | {{:magistraleinformatica:alg2:algo2_14:lec02.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_14:approxclrs.pdf| Sect.35.1}} |
 | Dec. 11| Approximation for bin packing and knapsack. | [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/book/chapter02.pdf| chapt.2: par. 2.1.1, par. 2.2.2]] | | Dec. 11| Approximation for bin packing and knapsack. | [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/book/chapter02.pdf| chapt.2: par. 2.1.1, par. 2.2.2]] |
  
Linea 91: Linea 91:
 == Excercises discussed in class == == Excercises discussed in class ==
  
-This is the {{:magistraleinformatica:alg2:algo2_14:esercitazioni2014.pdf|final list}} of problems. Some of the [[https://www.dropbox.com/sh/4gseckzpbyix3mm/AABZj_Lp06BwMuy_CyVOQWgqa?dl=0|screen snapshots]] shown in the classroom.+This is the {{:magistraleinformatica:alg2:algo2_14:esercitazioni2014.pdf|final list}} of problems. Some of the [[https://www.dropbox.com/sh/dxj7dm1u0tjebf6/AAAqDxclSXVdrOIibNLLu2qoa?dl=0|screen snapshots]] shown in the classroom.
  
 == Official class documents == == Official class documents ==
Linea 99: Linea 99:
  
 == Examination outcomes (in Italian) == == Examination outcomes (in Italian) ==
- +  * No more accessible
-Examination date 17.12.2014 +
- +
-^ Matricola ^ Score/30 ^ Comments ^ +
-|423458|29|Ex.1 missing the part on showing how to implement EM mergesort and analyzing its cost. Ex.2 done, with a small typo. Ex.3 done.| +
-|451619|29|Ex.1 done with some issues in the analysis of the CPU time: it is not specified which choice of k and, although the CPU complexity of the k-way merge is proven to be O(N log k), it is then used O(N k) in the rest of the analysis. Ex.2-3 done.| +
-|464229|24|Ex.1 discusses the analysis in a too light fashion. Ex.2 does not use dyadic intervals, so the solution is good only if the range is very small. Ex. 3 done.| +
-|471122|28|Ex.1 done. Ex.2 needs to introduce a global variable for the sum of the counters as suggested in the text of the exercise. Ex.3 done.| +
-|473711|29|Ex.1 does not specify the choice of k, and does not conclude the analysis for the CPU time. Ex.2 has an unclear step using the complement. Ex.2 done.| +
-|478750|30-|Ex.1 done, the proposed algorithm is for main memory but then it is said how to use it in EM. Ex.2-3 done.| +
-|480474|29|Ex.1 done but the proposed algorithm is for main memory and it does not specify how to get it for EM; the analysis is correct but cannot be referred otherwise to that algorithm. Ex.2 done with a small typo; appreciated that it is proved why at most 2 log n intervals are needed. Ex.3 done.| +
-|499434|20|Ex.1 starts from a concrete example but then it does not generalize; also, analysis is missing. Ex.2 not done. Ex.3 same as the first exercise, some effort is needed to learn how to generalize the ideas.| +
-|508710|29|Ex.1 missing the part on showing how to implement EM mergesort and analyzing its cost. Ex.2 done, one step is not completely clear. Ex.3 done.| +
-|525804|--|Ex.1 done correctly. Ex.2-3 not done.| +
-|525820|--|Ex.1 done partially, the few figures are explanatory, but more explanatory text would be appreciated. Ex.3 started with the definition of max cut but not completed. Ex.2 not done.| +
-|525822|--|Ex.1 done correctly, the figures are explanatory, more explanatory text would be appreciated. Ex.2-3 not done.| +
-|527114|--|Need student's help to read it, I cannot decode some parts of the text.| +
- +
- +
  
magistraleinformatica/alg2/algo2_14/start.1421075219.txt.gz · Ultima modifica: 12/01/2015 alle 15:06 (9 anni fa) da Roberto Grossi