Data Compression

Suppose someone collapses something to a fraction of its size and then expands it to its original form again: with a bike, it's engineering; with an apple, it's magic; with a book, it's data compression.

In the first half of the course we'll cover basic and intermediate topics, such as

• prefix coding
• the Kraft-McMillan Inequality
• Shannon coding
• Huffman coding
• 0th-order (empirical) entropy
• adaptive Huffman coding
• Jensen's Inequality
• Elias codes
• move-to-front coding
• arithmetic coding
• adaptive arithmetic coding
• kth-order (empirical) entropy
• Ziv-Lempel coding
• Prediction by Partial Match
• the Burrows-Wheeler Transform.

In the second half of the course we'll introduce some more advanced topics, such as

• wavelet trees
• compressed rank/select
• compressed full-text indexes
• Occam's Razor
• Kolmogorov Complexity
• Minimum Description Length
• compression-based classification
• group testing
• compressed sensing

which students will have a chance to explore for their projects. A second- or third-year course on algorithms and data structures is recommended as background.

Most of the lectures and homework assignments will be in period III. Most of period IV will be left free for project work and exam preparation. Marks will be assigned on the basis of

• 4 homework assignments,
  each worth 10%
• the project, worth 30%
• the final exam, worth 30%.

For more information or to register, please email the instructor, Travis Gagie, at firstname.lastname@aalto.fi. Please do not try to sign up on Oodi. The first class will be on January 18th. Notes, slides and homework assignments will be posted here as they are finished.