Learning objectives
Overview of some of the most important algorithms
Prerequisites
algoritmi e strutture dati 1
Course unit content
• greedy algorithms, dynamic programming, branch-bound algorithms, local
search, Metropolis, simulated annehaling;
• computational geometry: convex hull, point location, polygonal triangu-
lation, sweeping algorithm, closest pair algorithm;
• DFT-IDFT: Cooley -Tuckey FFT algorithm, polynomial product/division,
interpolating polynomial, chinese remainder theorem, nite eld FFT,
Schonhage-Strassen algorithm for integer product;
• bilinear forms computation, matrix multiplication and related problems,
matrix multiplication algorithms;
• exact string matching: automata, Knuth-Morris-Pratt, Boyer-Moore, Aho-
Corasick algorithms; approximate string matching: Hamming distance,
edit distance, dynamic programming; trie, suffix tree, suffix array;
• the complexity classes P, NP, NPC and their relations, polynomial reduc-
tion, classes LOGSPACE and PSPACE, probabilistic complexity classes,
probabilistic algorithms, approximate algorithms.
Full programme
• greedy algorithms, dynamic programming: further applications;
• randomized algorithms, Miller-Rabin algorithm;
• parallel algorithms, PRAM, basic algorithms, Brent theorem;
• external memory model, k-way mergesort, distribution sorting;
• cache oblivious model, basic algorithms;
• online algorithms, competitive analysis; paging: LRU, Random, Marking; web caching: greedy dual, greedy dual size;
• computational geometry: convex hull, sweeping algorithm;
• DFT-IDFT: FFT algorithm, Cooley –Tuckey algorithm, polynomial multiplication, finite field FFT, Schonhage-Strassen algorithm for integer multiplication (sketch);
• exact string matching: Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm, suffix tree, suffix array;
• the complexity classes P, NP, NPC and their relations, polynomial reduction, approximate algorithms.
Bibliography
[1] F.P.Preparata, M.I.Shamos, Computational Geometry, Springer-Verlag.
[2] J.Kleinberg, E.Tardos, Algorithm design, Addison Wesley.
[3] C. H. Papadimitriou, Computational Complexity, Addison Wesley.
[4] A. Bernasconi, B. Codenotti, Introduzione alla Complessita Com-
putazionale, McGraw-Hill.
[5] D. Guseld, Algorithms on String, Trees, and Sequences: Computer science
and Computational Biology ,Cambridge University Press.
Teaching methods
class
Assessment methods and criteria
oral exam
Other information
- - -