This is the first PhD-level course on the design and the analysis of efficient algorithms, with a strong emphasis on theoretical aspects. The prerequisites are a very basic knowledge of graph theory and computational complexity, as well as a good understanding of undergraduate-level courses of algorithms, discrete mathematics, and operation research.
It is not necessary to have already taken a graduate-level course on algorithms.
The goal of the course is to give a broad coverage of the main techniques in algorithm design and analysis, so that the course can be useful also for a researcher in a different field. To this purpose, the computational problems tackled are among the most basic problems on strings and graphs, such as pattern matching, vertex cover and max cut.
In fact, anyone that deals with one of the following questions will find the course interesting.
- How can I cope with problems that are provably hard to solve exactly (i.e. are NP-hard)?
- How can I exploit the massive availability of CPUs?
- How can I query efficiently massive texts?
Exam
The exam will consists of some exercises that will be given during the course.
Collaboration is encouraged, but each student must write their own version of the solution.
Schedule
- Jan. 15, 10:30-12:30 – meeting room III floor, U14 (lecturer Gianluca Della Vedova) Parallel algorithms. (PRAM model, prefix sum algorithm, Map-Reduce)
- Jan. 16, 10:30-12:30 – meeting room III floor, U14 (lecturer Gianluca Della Vedova) Randomized algorithms. (Karp-Rabin algorithm for pattern matching)
- Jan. 18, 10:30-12:30 – meeting room III floor, U14 (lecturer Raffaella Rizzi) Text indexing (Suffix trees, suffix arrays, pattern matching, generalized suffix trees, Longest Common Substring between two strings)
- Jan. 22, 10:30-12:30 – meeting room I floor, U14 (lecturer Gianluca Della Vedova) Fixed-parameter algorithms. (Vertex cover)
- Jan. 29, 10:30-12:30 – meeting room III floor, U14 (lecturer Gianluca Della Vedova) Approximation algorithms. (Algorithms for Vertex Cover, Max Cut.)
- Jan. 30, 13:30-15:30 – meeting room III floor, U14 (lecturer Gianluca Della Vedova) Approximation algorithms. (Satisfiability, Approximation Complexity)
- Feb. 1, 10:30-12:30 – meeting room III floor, U14 (lecturer Raffaella Rizzi) Text indexing (Computing a suffix array from the suffix tree, Longest Common Prefix LCP array)
- Feb. 5, 10:30-12:30 – meeting room III floor, U14 (lecturer Gianluca Della Vedova) External-memory algorithms. (Parallel Disk Model, Sorting, B-trees)
- Feb. 6, 10:30-12:30 – meeting room III floor, U14 (lecturer Gianluca Della Vedova) Streaming algorithms. (Heavy Hitters, Count-Min sketch, Reservoir sampling)
- Feb. 8, 10:30-12:30 – meeting room III floor, U14 (lecturer Raffaella Rizzi) Text indexing (Burrows-Wheeler Transform and FM-index)
Lecture notes
slides