Professor
- Wim van Dam
- vandam@cs.____.___
- Harold Frank Hall, Room 2151
- during Fall 2009 I will more often than not be at the KITP
Teaching Assistant
Description
- List of topics: Entropy, mutual information, and Shannon's coding theorems, lossless source coding, Huffman, Shannon-Fano-Elias, and arithmetic codes, channel capacity; aspects of rate-distortion theory, lossy source coding, source-channel coding, Kolmogorov/algorithmic complexity and information; applications of information theory in various fields
- This 4 unit, graduate course is listed both for the CS department and the ECE department, and will be taught alternately by Wim van Dam (CS) and Kenneth Rose (ECE). For CS students this course will satisfy the 'theory track'.
Prerequisites
Required Texts
- Elements of Information Theory, Thomas M. Cover and Joy A.Thomas, John Wiley, 1991
- Both editions, the 1st from 1991 or the 2nd from 2006, are fine.
Final Grade
- The final grade will be determined 60% on the basis of the three take-home exercises and 40% on the basis of the final paper that you will write.
Class and Office Hours
- Monday 11:00-13:00: Class in Phelps 1401
- Tuesday 13:00-15:00: Office hours WvD in Harold Frank Hall, room 2151
- Wednesday 11:00-13:00: Class in Phelps 1401
- Thursday 12:00-14:00: Office hours LF in Harold Frank Hall, room 2120B (Applied Algorithms lab)
Contacting/Questions
- I prefer that you use my office hours for your questions, rather than doing a lengthy Q&A exchange via email or an impromptu office visit. Please email me for an appointment in the afternoon if the office hours do not work for you. Thanks.
Week-by-Week Schedule
- Week 1 (September 27 - October 3)
- Topics: introduction to the course, discrete random variables, entropy, joint entropy, informal statement of the Asymptotic Equipartition Property (AEP)
- Announcement of Assignment 0; due Tuesday October 7
- Week 2 (October 4 - 10)
- Topics: conditional entropy, relative entropy, mutual information, Jensen's inequality, concavity of entropy function, Information inequality D(p||q)≥0; interpretation of relative entropy/Kullback-Leibler distance, data compression, non-singular codes, uniquely decodable codes, prefix/instantaneous codes, Kraft's inequality
- Assignment 0 due on Tuesday October 7
- Week 3 (October 11 - 17)
- Topics:proof of Kraft's Inequality, bounds on optimal codelengths, Shannon's Lossless Source Coding Theorem, Huffman codes; Shannon-Fano-Elias coding, arithmetic coding, universal coding, Lempel-Ziv coding
- Assignment 1 will be announced (on entropy and data compression); it will be due at the end of Week 4.
- Week 4 (October 18 - 24)
- Topics: Asymptotic Equipartition Property, unusual application of data compression, machine learning; channel capacity, preview of noisy channel theorem
- Assignment 1 is due on Friday October 23
- Week 5 (October 25 - 31)
- Topics: jointly typical sequences, proof of noisy channel theorem (handout)
- Assignment 2 will be announced (on the noisy channel theorem); it will be due at the end of Week 6.
- Week 6 (November 1 - 7)
- Topics: error correcting codes, Hamming distance, Hamming codes, linear codes, Hamming bound, perfect codes
- Assignment 2 is due on Friday November 6
- Week 7 (November 8 - 14)
- Topics: error correction in practice (time permitting)
- No Class Wednesday November 11 (Veterans Day)
- Week 8 (November 15 - 21)
- Topics: Rate distortion theory
- Assignment 3 will be announced (on error correction and rate distortion theory); it will be due before Thanksgiving
- Week 9 (November 22 - 28)
- Topics: Assignment 3; information theory of rate distortion theory
- Assignment 3 is due on Wednesday November 25
- No class Wednesday November 25 (pre Thanksgiving)
- Week 10 (November 29 - December 5)
- No class Monday November 30 (post Thanksgiving)
- Topics: writing the final paper
- Finals Week (December 6 - 12)
- Friday December 11: Final paper is due
Assignments
- Assignment 0: Before Wednesday October 7, email WvD a LaTeX file and the corresponding pdf that contains your name, student number, students status and any additional, relevant information along with an equation expressing the definition of entropy. The goal of this assignment is to make certain that everyone can work with LaTeX, before the first real assignment. Here are some pointers to information on how to install and work with LaTeX.
- Assignment 1 (Assignment1.pdf): No later than Friday October 23, email the TA (Luca Foschini) your answers to the questions. Your answers should be typeset in LaTeX and you will have to email both the pdf and the original LaTeX file. It is strongly recommened that you use the LaTeX file yourname_A1.tex as the skeleton of your answers. Please cc WvD when you email your answers (after renaming the file of course) to the TA.
- Regarding Question 3: We say that X 'equals' Y when there is a bijection f from X to Y such that Pr[X=x] = Pr[Y=f(x)] for all x; and with g the inverse of f we also have Pr[Y=y] = Pr[X=g(y)] for all y. However, this mapping between X and Y only concerns the elements x for which p(x) > 0 and the elements y for which p(y)>0. So it is possible to have two alphabets of different size for X and Y, yet still X=Y. Another way of phrasing this is to say that "X=Y" means that the multiset of nonzero probabilities p(x) equals the multiset of nonzero probabilities p(y).
- Here are the Answers to Assignment 1.
- Assignment 2 (Assignment 2): No later than Friday November 6 email the TA (cc WvD) your answers. As with Assignment 1, your answers should be typeset in LaTeX. The only reference that you are allowed to use is the textbook by Cover and Thomas; indicate where and how you used it in your answers. Question 2 should be answered without using any reference, not even Cover and Thomas. All 8 questions are worth 100 points. Let WvD or the TA know if you have questions about this exercise. Like with the previous assignment you can use the skeleton LaTeX file yourname_A2.tex.
- Here are the Answers to Assignment 2.
- Assignment 3 (Assignment 3): No later than Friday November 27 email the TA (and cc WvD) your answer to the last assignment. As usual, your answers should be typeset in LaTeX using the skeleton yourname_A3.tex. All your proofs should be self-contained; if you used references to find your proofs, you should mention them. Here are the answers to Answers to Assignment 3.
Final Paper
The Final Paper is due on Friday December 11 (23:59 PST); email your paper in pdf and LaTeX to WvD. No extensions will be given for the Final Paper.
Requirements: The paper should be typeset in LaTeX and should be at most 5 pages (excluding references and appendix). Large images can be put separately after these 5 pages as well. The font should be a standard one like Computer Modern or Times; the font size should be at least 11pts. The paper should be letter-sized with margins of at least 1 inch. When running out of space, choose depth over width in your paper. Here is a skeleton file for the final paper: yourname_Final_Paper.tex.
See here for some advice on writing academic papers and here for information about LaTeX.
Here are some good examples of final papers of previous installments of the course (note that these are longer than is required this quarter though):