Learning objectives
Overview of some of the most important algorithms
Prerequisites
Algoritmi e strutture dati e Laboratorio di Algoritmi e strutture dati
Course unit content
<br />
<br />
<br />
• greedy algorithms, dynamic programming, branch-bound algorithms, local <br />
search, Metropolis, simulated annehaling; <br />
• computational geometry: convex hull, point location, polygonal triangu- <br />
lation, sweeping algorithm, closest pair algorithm; <br />
• DFT-IDFT: Cooley -Tuckey FFT algorithm, polynomial product/division, in- <br />
terpolating polynomial, chinese remainder theorem, finite field FFT, Schonhage- <br />
Strassen algorithm for integer product; <br />
• bilinear forms computation, matrix multiplication and related problems, <br />
matrix multiplication algorithms; <br />
• exact string matching: automata, Knuth-Morris-Pratt, Boyer-Moore, Aho- <br />
Corasick algorithms; approximate string matching: Hamming distance, <br />
edit distance, dynamic programming; trie, suffix tree, Ziv-Lempel algo- <br />
rithm; <br />
• the complexity classes P, NP, NPC and their relations, polynomial reduc- <br />
tion, classes LOGSPACE and PSPACE, probabilistic complexity classes, <br />
probabilistic algorithms, approximate algorithms.
Bibliography
<br />
<br />
[1] C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1995. <br />
[2] A. Bernasconi, B. Codenotti, Introduzione alla Complessita Com- <br />
putazionale, McGraw-Hill, 1998. <br />
[3] D. Gusfield, Algorithms on String, Trees, and Sequences: Computer science <br />
and Computational Biology Cambridge University Press, 1997. <br />
