Advanced Techniques for Combinatorial Algorithms

This course focuses 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.
The topics are:

  1. Approximation Algorithms. (Algorithms for Vertex Cover, Satisfiability, Max Cut. Approximation Complexity)
  2. Randomized Algorithms. (Karp-Rabin algorithm for pattern matching)
  3. Parallel Algorithms. (PRAM model, prefix sum algorithm, Map-Reduce)
  4. Text Algorithms. (Suffix trees, suffix arrays, LCP array)
  5. Compressed data structures (compressed suffix arrays, compressed graphs)
  6. Succinct representations of data (Entropy, Huffman codes, Jensen’s Inequality, Elias’ gamma and delta codes)

The exam will consists of some exercises that will be given during the course.
Collaboration is encouraged, but the groups should be small (max 3 or 4 students) and each student must write their own version of the solution.

Schedule

  • Feb. 2, 10:30-12:30 – meeting room III floor, U14
  • Feb. 3, 10:30-12:30 – meeting room III floor, U14
  • Feb. 8, 14:00-16:00 – Seminar Room, U14 (lesson held by Pawel Gawrychowski)
  • Feb. 10, 14:00-16:00 – Seminar Room, U14 (lesson held by Pawel Gawrychowski)
  • Feb. 11, 11:00-13:00 – Seminar Room, U14 (lesson held by Pawel Gawrychowski)
  • Feb. 16, 11:00-13:00 – meeting room III floor, U14 (lesson held by Travis Gagie)
  • Feb. 17, 11:00-13:00 – meeting room III floor, U14, (lesson held by Travis Gagie)
  • Feb. 18, 11:00-13:00 – Seminar Room, U14, (lesson held by Travis Gagie)
  • Mar. 1, 14:00 – 16:00 – meeting room III floor, U14
  • Mar. 8, 14:00 – 16:00 – meeting room III floor, U14