magistraleinformatica:alg2:algo2_14:start
Differenze
Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente | ||
| magistraleinformatica:alg2:algo2_14:start [02/01/2015 alle 09:37 (10 anni fa)] – [Topics] Roberto Grossi | magistraleinformatica:alg2:algo2_14:start [04/10/2015 alle 10:06 (10 anni fa)] (versione attuale) – Roberto Grossi | ||
|---|---|---|---|
| Linea 7: | Linea 7: | ||
| * Office hours: Thu 11-14 (Dipartimento di Informatica) | * Office hours: Thu 11-14 (Dipartimento di Informatica) | ||
| * Next written examination dates (please register): Room C1, 09: | * Next written examination dates (please register): Room C1, 09: | ||
| - | * Next oral examination dates (meeting to fix dates): Teacher' | + | * Next oral examination dates (meeting to fix dates): |
| ==== Overview ==== | ==== Overview ==== | ||
| Linea 77: | Linea 76: | ||
| | Dec. 9| Notion of r-approximation algorithm. TSP: NP-hardness and difficulty of approximation. 2-approximation for metric TSP. | {{: | | Dec. 9| Notion of r-approximation algorithm. TSP: NP-hardness and difficulty of approximation. 2-approximation for metric TSP. | {{: | ||
| | Dec. 9| Problem solving (4 hours) | {{: | | Dec. 9| Problem solving (4 hours) | {{: | ||
| - | | Dec. 10| 2-approximation for MAX-CUT: local search, greedy. 2-approximation for minimum vertex cover. | [[http:// | + | | Dec. 10| 2-approximation for MAX-CUT: local search, greedy. 2-approximation for minimum vertex cover. | {{: |
| | Dec. 11| Approximation for bin packing and knapsack. | [[http:// | | Dec. 11| Approximation for bin packing and knapsack. | [[http:// | ||
| Linea 92: | Linea 91: | ||
| == Excercises discussed in class == | == Excercises discussed in class == | ||
| - | This is the {{: | + | This is the {{: |
| == Official class documents == | == Official class documents == | ||
| Linea 100: | 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 uses 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, | + | |
| - | |525822|--|Ex.1 done correctly, the figures are explanatory, | + | |
| - | |527114|--|Need student' | + | |
| - | + | ||
| - | + | ||
magistraleinformatica/alg2/algo2_14/start.1420191461.txt.gz · Ultima modifica: 02/01/2015 alle 09:37 (10 anni fa) da Roberto Grossi