CS698D: Special Topics in Data Compression

You can find a tentative syllabus here.

The course assumes a basic acquaintance with \(\epsilon\)- \(\delta\) -style proofs in Analysis. Though the course is reasonably self-contained - all the concepts needed in the course will be defined in the course - in order to be comfortable in doing the exercises, one needs proficiency in the concepts of continuous mathematics - limits, continuity and integration. The course also contains a certain amount of Measure Theory, I will try to cover the contents avoiding measure-theoretic concepts as much as possible.

There will be

1. 3 Homeworks - 16.67 % each
2. 2 Take-home exams - each of 1 1/2 day duration, 25 % each

Late submission policy for homeworks

1. deadline until 1 day past - 5 % penalty
2. 2 days - 1 week past deadline - 15% penalty

No homeworks will be accepted 1 week past the deadline. Please let me know if there are special circumstances which make it difficult for you to meet the deadline.

You are encouraged to discuss homework problems with your friends, TAs, and the instructor. However, the final answer should be written by you. Please acknowledge each person and source (books, websites) that you referred to or discussed with, for each answer. There are no penalties for discussion or reference.

( A general rule of thumb is - discuss the answers, and go back alone and write up the answer by yourself. )

Verbatim copying will be strictly penalized with a 0 in the particular homework in the case of the first instance, and with an F in the course for repeated violations.

Discussion is not allowed on take-home exams, except with the TAs or the instructor. You can refer to books, websites, papers etc. but please cite the sources when you do so. Verbatim copying from these sources however, will again be discouraged. Understand the contents, and write down the answer in your own words after proper citation of the sources. In the case of exams, even the first violation will lead to an F in the course.

• Lecture 1: (December 31, 2013). Introduction, Topics to be covered.
• Lecture 2: (January 1, 2014). Ad-hoc Compression Methods
• Lecture 3: (January 7, 2014). Shannon Entropy via Types, Basic Inequalities. Additional:Information Theoretic Inequalities
• Lecture 4: (January 8, 2014). Kullback-Leibler Divergence
• Lecture 5: (January 15, 2014). Limits,Continuity and Riemann Integration.
• Lecture 6: (January 18, 2014). Introduction to Measure - \(\sigma\) algebras and finite measures, measurable functions (random variables)
• Lecture 7: (January ?, 2014). Independence, Lebesgue integrability, Dominated Convergence Theorem. Weak and Strong Laws of Large Numbers
• Lecture 8: (January 28, 2014). Shannon-McMillan-Breiman Theorem, the iid case. Shannon-Fano Codes
• Lecture 9: (January 29, 2014). Huffman code, optimality of Huffman Code
• Lecture 10: (February 4, 2014). Arithmetic coding, Introduction to Lempel-Ziv algorithm
• Lecture 11: (February 5, 2014) LZ78
• Lecture 12: (February 11, 2014) LZ78
• Lecture 13: (February 12, 2014) Optimality of LZ78
• Lecture 14: (February 25, 2014) Optimality of LZ78
• Lecture 15: (February 26, 2014) Optimality of LZ78 http://dx.doi.org/10.1109%2FTIT.1978.1055934
• Lecture 16: (March 4, 2014) LZ77 http://dx.doi.org/10.1109%2FTIT.1977.1055714
• Lecture 18: (March 11, 2014) Shields' pointwise optimality of ULZ
• Lecture 19: (March 12, 2014) Shields' pointwise optimality of ULZ http://dx.doi.org/10.1109/18.761286
• Lecture 20: (March 25, 2014) Ergodicity - Introduction
• Lecture 21: (March 26, 2014) Ergodicity - Introduction Notes
• Lecture 22: (April 1, 2014) Cutting and Stacking
• Lecture 23: (April 2, 2014) Cutting and Stacking http://dx.doi.org/10.1109/18.104321
• Lecture 24: (April 9, 2014) V'yugin's nonrobustness result
• Lecture 25: (April 14, 2014) V'yugin's nonrobustness result http://arxiv.org/abs/0806.4572

…

• Homework 1 Due Date : January 28, 2014
• Midsem (takehome) : March 3-4, 2014
• Homework 2 Due Date : March 28, 2014
• Homework 3 Due Date : March 13, 2014
• Endsem (takehome) : April 23-24, 2014 (tentative)