Algoritmica 2

Docenti: Paolo Ferragina, Roberto Grossi, Fabrizio Luccio, Linda Pagli, Nadia Pisanti

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

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.

• Compressione di testi e di interi
• Strutture di dati randomizzate
• Motori di ricerca: liste invertite

• Modelli di computazione
• Permutazioni e ordinamenti
• Dizionari

• Matrice dei suffissi
• Albero dei suffissi
• Algoritmi di pattern matching

• Strutture di dati distribuite
• Analisi competitiva
• Algoritmi on-line

• I problemi NP-hard
• Algoritmi di approssimazione
• Algoritmi randomizzati

• REGISTRO DELLE LEZIONI

• PROBLEMI DIFFICILI E APPROSSIMAZIONE 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 alg-random.pdf

• DATA COMPRESSION: 07_mg-partchap2.pdf
  • Non studiare “Computing Huffman code lengths” e “Maintaining cumulative counts”
  • Studiare anche “Huffman canonico”
  • Esempio per BWT
  • Dimostrazione performance di MTF (Teo 1 e Cor 1)
• BLOOM FILTER survey e slides
• HASH UNIVERSALE E HASH PERFETTO clr-hash.pdf
• MOTORI DI RICERCA (cenni, note)

• STRINGOLOGIA
  • EXACT MATCHING (patternmatching1.pdf, patternmatching2.pdf)
  • AHO-CORASICKuno.pdf
  • KARP-RABIN due.pdf
  • SUFFIX TREE tre.pdf
  • SUFFIX ARRAY quattro.pdf

• ALGORITMI ON LINE
  • MOVE TO FRONT mtf.pdf
  • Algoritmi per il problema del paging 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 gds.pdf

• HASHING DISTRIBUITO
• Consisitent Hashing
• Dalla tesi di master di Daniel M. Lewinprima parte

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 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 VERSIONE ELETTRONICA
  • Dizionari: lucidi di L. Arge VERSIONE ELETTRONICA (prime 21 pagine) e G. S. Brodal 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 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 VERSIONE ELETTRONICA (sezioni 38.1 e 38.2/38.2.1)

Compitino del 17/12/2009 Soluzione

Primo Appello (11/1/2010) Soluzione

Secondo Appello dell'1/2/2010 Testo

Terzo Appello del 2/6/2010 Testo

Quarto Appello del 22/6/2010 Testo

Quinto Appello del 13/7/2010 Testo

Sesto Appello del 7/9/2010