Advanced Techniques for Combinatorial Algorithms

In February-March 2016, we will give a PhD course on 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 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 official page is here.

Schedule

  • Feb. 2, 10:30-12:30 – meeting room III floor, U14, (lecturer Gianluca Della Vedova). Parallel Algorithms. (PRAM model, prefix sum algorithm, tree depth, connectivity). slides
  • Feb. 3, 10:30-12:30 – meeting room III floor, U14, (lecturer Gianluca Della Vedova). Randomized Algorithms. (Karp-Rabin algorithm for pattern matching). Succinct representations of data (Entropy, Huffman codes, Jensen’s Inequality, Elias’ gamma and delta codes) slides
  • Feb. 8, 14:00-16:00 – Seminar Room, U14 (lecturer Pawel Gawrychowski). Suffix arrays (construction and pattern matching) slides
  • Feb. 9, 14:00-16:00 – T014 (lecturer Pawel Gawrychowski). Suffix arrays 2 (Burrows-Wheeler transform and Lempel-Ziv factorization) slides
  • Feb. 11, 11:00-13:00 – Seminar Room, U14 (lecturer Pawel Gawrychowski). Indexing with errors (indexing with k mismatches, heavy path decomposition) slides
  • Feb. 16, 11:00-13:00 – meeting room III floor, U14 (lecturer Travis Gagie). Basic Lossless Data compression (The Kraft Inequality and Jensen’s Inequality; Shannon’s Noiseless Coding Theorem; Shannon and Huffman Codes; Canonical Codes; Elias Codes; empirical entropy; LZ77 and LZ78; BWT)
  • Feb. 17, 11:00-13:00 – meeting room III floor, U14, (lecturer Travis Gagie). Compressed data structures (Bitvectors; wavelet trees; compressed permutations; rank and select on sequences; succinct trees). voce enciclopedia articolo introduttivo slides
  • Feb. 18, 11:00-13:00 – Seminar Room, U14, (lecturer Travis Gagie). Self-Indexes for Strings and Graphs (LZ-based indexes; FM-indexes; LZ/FM-hybrid indexes; the XBWT for labelled trees; BWT-based representations of de Bruijn graphs; the GCSA for genomic graph references) articolo introduttivo slides
  • Mar. 1, 14:00 – 16:00 – meeting room III floor, U14, (lecturer Gianluca Della Vedova) Approximation Algorithms. (Algorithms for Vertex Cover, Satisfiability, Max Cut. Approximation Complexity)
  • Mar. 8, 14:00 – 16:00 – meeting room III floor, U14, (lecturer Gianluca Della Vedova) Approximation Algorithms. slides