ALGORITMI E COMPLESSITA'
Anno Accademico 2010-2011
- Lezione 1: Introduzione alla complessità e ai modelli di
calcolo. Definizione di algoritmo, problema, istanza, complessità (in
tempo e spazio) al caso pessimo e medio. Algoritmi polinomiali ed
esponenziali. Problemi indecidibili: Fermata. Tecnica della
diagonalizzazione.
- Lezione 2: Random sampling su modello a disco o streaming, con lunghezza dell'input nota o sconosciuta.
- Lezione 3: Sorting e Permuting su modello a disco, multi-way mergesort, Snow-plow, limiti inferiori.
- Lezione 4: Quicksort and Random selection. Distribution sort on disk. Comments on the D disks case.
- Lezione 5: Bloom Filter, Spectral Bloom Filter, Count Min Sketch (proof for point-wise query).
- Lezione 6: CMS on skewed distributions, use of CMS for computing the dot-product and for determining the heavy-hitters (Also Karp's algorithm). Prefix search with tries, binary search, and 2-level indexing.
- Lezione 7: Prefix search: Patricia Trie, String B-tree, front-coding. Text indexing: suffix tree and suffix array, properties and text mining. Suffix array construction: qsort-based, skew.
- Lezione 8: k-mismatch search. LCA = RMQ and constant-time queries.Hashing: hashing with chaining, uniform hashing, universal hashing.
- Lezione 9: Perfect hashing, mionimal ordered perfect hashing, cuckoo hashing. Integer compression: gamma, delta, rice, variable-byte, PForDelta.
- Lezione 10: Data compression: entropy, prefix codes, huffman (with proof of optimality), arithmetic code (with proof of performance), lz77, gzip, rsync.
- Lezione 10: Burrows-Wheeler Transform, MTF, RLE, bzip. Treaps, random binary search trees and skip lists.
- Lezione 11: Class RP and Primality testing: Miller-Rabin's algorithm. pseudo-polynomial time algorithms: partition, knapsack 0-1. Optimal algorithm for knapsack real. FPTAS for knapsack 0-1.
- Lezione 12: Shortest Path: Dijkstra, Bellman-Ford (con prove di correttezza). MST: Prim, kruskal e backward (con prove di correttezza). Matching e Flusso massimo (con teoremi di ottimalita')
- Lezione 13: Approximation algorithms: vertex cover, TSP (with or without triangle inequality), set covering. Discussion on 3-SAT, 2-SAT and MAX 2-SAT. Polynomial time algorithm for 2-SAT.
- Lezione 14: Schemi di codifica e macchina di Turing. Tesi (estesa) di Church-Turing. Le classi P, NP e NPC. Riduzione polinomiale.
- Lezione 15: Il Teorema di Cook (con dimostrazione). Esempi di riduzione polinomiale: 3SAT, CLIQUE.