Differenze

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

--- magistraleinformatica:alg2:algo2_14:start [21/12/2014 alle 10:03 (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 5: / Linea 5: @@
   * The {{:magistraleinformatica:alg2:algo2_14:esercitazioni2014.pdf|final list}} of problems discussed in class is available.
-  * The class lectures will be (mainly) given in English.  Tue 11-13 (aula A1), Wed 16-18 (aula C1), Thu 9-11 (aula N1).
   * Office hours: Thu 11-14 (Dipartimento di Informatica)
-  * Next examination dates: Room C1, 11:00-13:00, Dec. 17, 2014.
+  * Next written examination dates (please register): Room C1, 09:00-11:00, Jan. 20, 2015. Room C1, 15:00-17:00, Feb. 11, 2015.
+  * Next oral examination dates (meeting to fix dates): Teacher's office, 09:00, Jan. 14, 2015. Teacher's office, 09:00, Jan. 22, 2015. Teacher's office,, 09:00, Feb. 16, 2015.
 ==== Overview ====
@@ Linea 54: / Linea 53: @@
 ^ Date ^ Topics ^ References and notes ^
 | Oct. 29| Randomness and Kolmogorov complexity. Randomized quicksort.| [[http://www.eecs.berkeley.edu/~luca/cs172/notek.pdf| Notes (first 2 pages)]] {{:magistraleinformatica:alg2:algo2_13:randqs.pdf|par. 7.3}}|
-| Oct. 30| Las Vegas and Montecarlo algorithms. Analysis of randomised quick sort. Randomized algorithm for min-cut.| {{:magistraleinformatica:alga:algo2_13:qsrand.pdf|par.5.1}} {{:magistraleinformatica:alga:algo2_13:randqs.pdf|par. 7.3}} |
+| Oct. 30| Las Vegas and Montecarlo algorithms. Analysis of randomised quick sort. Randomized algorithm for min-cut.| {{:magistraleinformatica:alg2:algo2_13:qsrand.pdf|par.5.1}} {{:magistraleinformatica:alg2:algo2_13:randqs.pdf|par. 7.3}} |
 | Nov. 11| Problem solving. | {{:magistraleinformatica:alg2:algo2_14:esercitazioni2014.pdf|list of problems}}|
 | Nov. 12| Data Streaming Model. Motivations and examples.| {{http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf| sect.1}} [[https://sites.google.com/site/countminsketch/|Site]] {{:magistraleinformatica:alg2:algo2_12:count-min-sketch.pdf|Notes}}|
@@ Linea 69: / Linea 68: @@
 ^ Date ^ Topics ^ References and notes ^
-| Nov. 26| Complexity classes: P, NP, NPC. Polynomial reductions (prof. Pagli)| {{:magistraleinformatica:alg2:algo2_14:tm.pdf|Turing Machines}} {{:magistraleinformatica:alg2:algo2_14:np.pdf|pp.255-260, 264-274}}|
+| Nov. 26| Complexity classes: P, NP, NPC. Polynomial reductions (prof. Pagli)| {{:magistraleinformatica:alg2:algo2_14:tm.pdf|Turing Machines}} {{:magistraleinformatica:alg2:algo2_14:np.pdf|pp.255-260, 264-276}}|
-| Nov. 27| Example of reductions: SAT, 3-SAT, NE-3-SAT.| [[http://www.cs.sfu.ca/~kabanets/308/lectures/lec16.pdf|Notes]]|
+| Nov. 27| Example of reductions: SAT, 3-SAT, NE-3-SAT.| [[http://www.cs.sfu.ca/~kabanets/308/lectures/lec16.pdf|Notes]] {{:magistraleinformatica:alg2:algo2_14:np.pdf|pp.282-283}}|
-| Dec. 2| Problem solving | {{:magistraleinformatica:alga:algo2_14:esercitazioni2014.pdf|list of problems}} |
+| Dec. 2| Problem solving | {{:magistraleinformatica:alg2:algo2_14:esercitazioni2014.pdf|list of problems}} |
 | Dec. 3| NP-completeness of MAX-CUT. | [[http://www.cs.cornell.edu/Courses/cs4820/2014sp/notes/reduction-maxcut.pdf|Notes]] |
-| Dec. 4| Coloring problems. Reduction from 3-coloring of planar maps to 3-SAT. |  |
+| Dec. 4| Coloring problems. Reduction from 3-coloring of planar maps to 3-SAT. | {{:magistraleinformatica:alg2:algo2_14:2014.12.04.pdf|Notes}} |
-| Dec. 4| Problem solving | {{:magistraleinformatica:alga:algo2_14:esercitazioni2014.pdf|list of problems}} |
+| Dec. 4| Problem solving | {{:magistraleinformatica:alg2:algo2_14:esercitazioni2014.pdf|list of problems}} |
-| 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. | {{:magistraleinformatica:alg2:algo2_14:approxclrs.pdf| Except Sect.35.1}} |
-| Dec. 9| Problem solving (4 hours) | {{:magistraleinformatica:alga: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. | |
+| 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]] |
@@ Linea 92: / Linea 91: @@
 == 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 ==
-  * Access to [[http://upload.wikimedia.org/wikipedia/commons/0/00/Escribano.jpg|unimap log (registro delle lezioni)]]
+  * Access to [[http://unimap.unipi.it/registri/printregistriNEW.php?re=154493::::&ri=9172|unimap log (registro delle lezioni)]]
   * Access to the [[https://esami.unipi.it/esami/|course evaluation form (questionario studenti)]]
 == Examination outcomes (in Italian) ==
+  * No more accessible