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
In the second half of the course we'll introduce some more advanced 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.
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.
- wavelet trees
- compressed rank/select
- compressed full-text indexes
- Occam's Razor
- Kolmogorov Complexity
- Minimum Description Length
- compression-based classification
- group testing
- compressed sensing
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,
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
as they are finished.