CS 698 D : Special Topics in Data Compression

Table of Contents

1 Contents

You can find a tentative syllabus here.

2 Grading Policy

  1. 3 homeworks - 20 % each
  2. 2 Exams - 20 % each
During the course, we shall encounter several conjectures, and ideas for proofs that are not completed. Students are encouraged to try them out on their own. This will be considered for credit. (And especially good proofs will earn a straight A in the course!!)

3 Academic Honesty

We will follow the academic policy of the department. For homeworks, you are encouraged to collaborate and discuss with friends etc. But, write the answers on your own - do not copy verbatim from others. Also, acknowledge all your sources - friends, internet sources, academic papers etc. No points will be deducted for this, in fact, this is the behaviour that conforms to academic ethics.

4 Lecture Notes

Lecture Notes of an older offering of the course are available here.

Updated Lecture Notes, arranged topic-wise.

  1. Introduction to Lossless Data Compression.
  2. Run-Length Encoding : algorithm and probabilistic analysis
  3. Move-To-Front Encoding : algorithm and probabilistic analysis
  4. Introduction to Shannon Entropy and Kullback-Leibler Divergence
  5. Shannon-Fano Coding and Huffman Coding : algorithms and optimality
  6. Ziv-Lempel 78 : Algorithm and Pointwise Optimality
  7. Lempel-Ziv 77 : Algorithm and Pointwise Optimality
  8. Instability of Universal Compressors - ZL78 : Proof using cutting and stacking
  9. Asymmetric Numeral Systems : A variant and its optimality

5 Homework

Homework 2, due 15 November 2017.

Author: Satyadev Nandakumar <satyadev@cselinux1.cse.iitk.ac.in>

Date: 2017/10/19 11:10:53 IST