====== Algoritmica 2======
Docenti: **Paolo Ferragina**, **Roberto Grossi**, **Fabrizio Luccio**, **Linda Pagli**, **Nadia Pisanti**


=== News ===

ATTENZIONE: Corona e Lima hanno un risultato diverso dalla prima pubblicazione dei risultati del compito del 1/2/2010

=== Obiettivi di apprendimento ===

In questo corso studieremo, progetteremo e analizzeremo soluzioni algoritmiche e strutture di dati avanzate per la risoluzione efficiente di problemi combinatori che coinvolgono vari tipi di dato, quali interi, stringhe, punti (geometrici), alberi, grafi.

Questo corso costituisce un naturale approfondimento e ampliamento delle conoscenze di base apprese nel percorso della laurea triennale.

Il suo syllabus è organizzato per ambiti applicativi, al fine di contestualizzare le tecniche studiate nella realizzazione di software efficiente per essi, e così da consentire adattamenti e specializzazioni di anno in anno che si renderanno necessari e/o opportuni.

=== Programma ===

== Accesso ai dati e loro compressione ==
     * Compressione di testi e di interi
     * Strutture di dati randomizzate
     * Motori di ricerca: liste invertite 

== Memorie gerarchiche ==
     * Modelli di computazione
     * Permutazioni e ordinamenti
     * Dizionari 

== Stringologia ==
     * Matrice dei suffissi
     * Albero dei suffissi
     * Algoritmi di pattern matching 

== Strutture di dati evolute ==
     * Strutture di dati distribuite
     * Analisi competitiva
     * Algoritmi on-line 

== Problemi "difficili" e loro soluzione ==
     * I problemi NP-hard
     * Algoritmi di approssimazione
     * Algoritmi randomizzati 

== Registro delle lezioni ==

     * [[http://unimap.unipi.it/registri/printregistriNEW.php?re=29405:::&ri=5777|REGISTRO DELLE LEZIONI]]


=== Materiale didattico ===
     * PROBLEMI DIFFICILI E APPROSSIMAZIONE {{:magistraleinformatica:alg2:dispensa_1.pdf|}}
        * L'esempio 12.2 contiene degli errori: individuarli.
        * Teoremi 12.5 e 12.7 senza dimostrazione.
        * Nel Teorema 12.8, k>=(1+e)n deve essere: k>=1+en.
     * ALGORITMI RANDOMIZZATI {{:magistraleinformatica:alg2:alg-random.pdf|}}

     * DATA COMPRESSION: {{:magistraleinformatica:alg2:07_mg-partchap2.pdf|}} 
        * Non studiare "Computing Huffman code lengths" e "Maintaining cumulative counts"
        * Studiare anche "Huffman canonico"
        * Esempio per {{:magistraleinformatica:alg2:bwt1.ppt|BWT}}
        * Dimostrazione performance di {{:magistraleinformatica:alg2:mtf-analysis.pdf|MTF}} (Teo 1 e Cor 1)
     * BLOOM FILTER {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|survey}} e {{:magistraleinformatica:alg2:bf_slides.pdf|slides}}
     * HASH UNIVERSALE E HASH PERFETTO {{:magistraleinformatica:alg2:clr-hash.pdf|}}
     * MOTORI DI RICERCA ({{:magistraleinformatica:alg2:searchengines_cenni_.ppt|cenni}}, {{:magistraleinformatica:alg2:chapferrluccio.pdf|note}})

     * STRINGOLOGIA
        * EXACT MATCHING ({{:magistraleinformatica:alg2:patternmatching1.pdf|}}, {{:magistraleinformatica:alg2:patternmatching2.pdf|}})
        * AHO-CORASICK{{:magistraleinformatica:alg2:uno.pdf|}} 
        * KARP-RABIN {{:magistraleinformatica:alg2:due.pdf|}}
        * SUFFIX TREE {{:magistraleinformatica:alg2:tre.pdf|}} 
        * SUFFIX ARRAY {{:magistraleinformatica:alg2:quattro.pdf|}}

     * ALGORITMI ON LINE
        * MOVE TO FRONT {{:magistraleinformatica:alg2:mtf.pdf|}}
        * Algoritmi per il problema del paging {{:magistraleinformatica:alg2:paging.pdf|}}
        * La dimostrazione dell'analisi competitiva dell'algoritmo DG è dubbia anche nell'articolo originale, non è da studiare.
        * WEB-Caching,  studiare paragrafo 3 e 4 {{:magistraleinformatica:alg2:gds.pdf|}}
     
     * HASHING DISTRIBUITO
        * Consisitent Hashing
        * Dalla tesi di master di Daniel M. Lewin{{:magistraleinformatica:alg2:ch1.pdf|prima parte}}
         {{:magistraleinformatica:alg2:ch2.pdf|seconda parte}}. Studiare fino all'enunciato del teorema 2.2.3. Poi i lemmi 2.2.5 e 2.2.6.

     * MEMORIE GERARCHICHE
        * Modelli di computazione, permutazioni e ordinamenti: J. S. Vitter. Algorithms and Data Structures for External Memory, Series on Foundations and Trends in Theoretical Computer Science, now Publishers, Hanover, MA, 2008. Also published as Volume 2, Issue 4 of Foundations and Trends in Theoretical Computer Science [[http://faculty.cse.tamu.edu/jsv/Papers/Vit.IO_book.pdf|VERSIONE ELETTRONICA (introduzione, sezione 2.1, capitolo 3, sezione 5.1/5.1.1, sezione 5.2, sezione 5.6, sezione 6)]]; L. Arge, M.G. Lagoudakis. External partition element finding [[http://www.daimi.au.dk/~large/ioS06/AL.pdf|VERSIONE ELETTRONICA]]
        * Dizionari: lucidi di L. Arge [[http://www.daimi.au.dk/~large/ioS08/Lecture2.pdf|VERSIONE ELETTRONICA (prime 21 pagine)]] e G. S. Brodal [[http://www.daimi.au.dk/~gerth/emF03/slides/b-trees.pdf|VERSIONE ELETTRONICA]] (guardare anche la bibliografia menzionata in tali lucidi).   
        * List ranking: Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-Memory Graph Algorithms, ACM-SIAM SODA 1995 [[http://www.cs.duke.edu/~jsv/Papers/CGG95.external_graph.pdf|VERSIONE ELETTRONICA (sezione 5)]]
        * Modello Cache-Oblivious (CO): L. Arge, G. S. Brodal and R. Fagerberg. Cache-Oblivious Data Structures. Chapter 38 in Handbook of Data Structures and Applications, CRC Press, 2004 [[http://www.daimi.au.dk/~large/ioS05/ABF.pdf|VERSIONE ELETTRONICA (sezioni 38.1 e 38.2/38.2.1)]]

=== Risultati e Soluzioni ===

Compitino del 17/12/2009  {{:magistraleinformatica:alg2:sol17-12-09.pdf|Soluzione}}

Primo Appello (11/1/2010) {{:magistraleinformatica:alg2:alg2-11-01-10sol.pdf|Soluzione}}

Secondo Appello dell'1/2/2010 {{:magistraleinformatica:alg2:alg2-02-02-10.pdf|Testo}}

Terzo Appello del 2/6/2010 {{:magistraleinformatica:alg2:alg2-02-06-10.pdf|Testo}}

Quarto Appello del 22/6/2010 {{:magistraleinformatica:alg2:alg2-22-06-10.pdf|Testo}}

Quinto Appello del 13/7/2010 {{:magistraleinformatica:alg2:alg2-13-07-10.pdf|Testo}}

Sesto Appello del 7/9/2010