DidaWiki

Strumenti Utente

Strumenti Sito

Ti trovi qui: DidaWiki » Corso di Laurea Magistrale in Informatica » Algoritmica 2 » Year 2014-2015
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 [21/12/2014 alle 10:11 (9 anni fa)]
Roberto Grossi 		magistraleinformatica:alg2:algo2_14:start [04/10/2015 alle 10:06 (9 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 {{: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)   * 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 ==== ==== Overview ====
  
Linea 54: Linea 53:
 ^ Date ^ Topics ^ References and notes ^ ^ 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. 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. 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}}| | 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 71: Linea 70:
 | 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. 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]] {{:magistraleinformatica:alg2:algo2_14:np.pdf|pp.282-283}}| | 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. 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]] | | 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 == == 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 ==
  
-  * 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)]]   * Access to the [[https://esami.unipi.it/esami/|course evaluation form (questionario studenti)]]
  
 == Examination outcomes (in Italian) == == Examination outcomes (in Italian) ==
 +  * No more accessible
 +
magistraleinformatica/alg2/algo2_14/start.1419156665.txt.gz · Ultima modifica: 21/12/2014 alle 10:11 (9 anni fa) da Roberto Grossi

Strumenti Pagina

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki