This is the site of Wim van Dam's graduate course "Information Theory" (CS225 and ECE205A) at UC Santa Barbara in Winter 2012.
Copyright 2012 Wim van Dam (UC Santa Barbara). It is forbidden to copy, distribute, or transit this work, nor is it allowed to alter, transform, or build upon this work.
- 2012-03-29: The grades have been submitted. Well done everybody. So long and thanks...
- 2012-01-07: Welcome to the CS225|ECE205A web site for Winter 2012, UCSB
General Course Information
- Course no: CS225 and ECE205A
- Course title: Information Theory
- 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
- Credit: 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: ECE 140 or PSTAT 120A-B
Professor
- Wim van Dam
- vandam@cs.____.___
- Harold Frank Hall, Room 2151
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
- Your final grade for the course will be determined by your scores for the 5 homework assignments. Each assignment will have 4 questions, worth 3 points each, hence in total you can get 60 points.
- Per question the 3 points are awarded using the following scale:
- 3 points: Exemplary; student applies knowledge with virtually no conceptual or procedural errors
- 2 points: Adequate; student applies knowledge with no significant conceptual errors and only minor procedural errors.
- 1 point: Minimal; student applies knowledge with occasional conceptual errors and only minor procedural errors.
- 0 points: Unsatisfactory; student makes significant conceptual and/or procedural errors when applying knowledge.
LaTeX
It is strongly recommended that you typeset your answers to the homework assignments in LaTeX. See here for information about LaTeX and here for some general advice on writing academic papers.
Class and Office Hours
- Tuesday 13:00/14:50: Class in Phelps 2510
- Thursday 10:00/12:00: Office hours in HFH 2151
- Thursday 13:00/14:50: Class in Phelps 2510
The norm will be that classes end at 14:30, but sometimes the amount of material might require us to run until 14:50.
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.
Academic Honesty
The following applies to every course you attend at UC Santa Barbara (from UCSB Campus Regulations, Chapter VII: "Student Conduct and Discipline"):
It is expected that students attending the University of California understand and subscribe to the ideal of academic integrity, and are willing to bear individual responsibility for their work. Any work (written or otherwise) submitted to fulfill an academic requirement must represent a student’s original work. Any act of academic dishonesty, such as cheating or plagiarism, will subject a person to University disciplinary action. Using or attempting to use materials, information, study aids, or commercial “research” services not authorized by the instructor of the course constitutes cheating. Representing the words, ideas, or concepts of another person without appropriate attribution is plagiarism. Whenever another person’s written work is utilized, whether it be a single phrase or longer, quotation marks must be used and sources cited. Paraphrasing another’s work, i.e., borrowing the ideas or concepts and putting them into one’s “own” words, must also be acknowledged. Although a person’s state of mind and intention will be considered in determining the University response to an act of academic dishonesty, this in no way lessens the responsibility of the student.
Specifically for the current CS225|ECE205A course this means that
- You are not allowed to copy or transcribe answers to homework assignments from others or other sources.
- Although you are allowed to discuss homework assignments with others, you should write down your answers independently. You should always be able to argue and explain your answers when asked for clarifications.
- When you will be unable to hand in the homework in time you should report this to WvD as soon as possible, but always before the deadline. No matter the reason, you will always be asked to present documentation.
- When in doubt, ask.
- Students violating the rules of Academic Honesty will receive an "F" for the course and will be reported to the Dean of Students Office.
Schedule of Topics and Homeworks
The page numbers in the references [EoIT] refer to to the 2nd edition of Elements of Information Theory.
Homework
- HW1: "Entropy"; announced 2012-01-19 (Week II, Thursday); due 2012-01-26 (Week III, Thursday, 23:59)
- HW2: "Data Compression"; announced 2012-01-27 (Week III, Friday); due 2012-02-03 (Week IV, Friday)
- HW3: "AEP, Gambling, Kolmogorov Complexity"; announced 2012-02-17 (Week VI, Friday); due 2012-02-24 (Week VII, Friday)
- HW4: "Channel Capacity"; announced 2012-02-24 (Week VII, Friday); due 2012-03-02 (Week VIII, Friday)
- HW5: "Error Correcting Codes, Rate-Distortion Theory"; announced 2012-03-09 (Week IX, Friday); due 2012-03-16 (Week X, Friday)
Week I [January 9/January 15]
- Topics: introduction to the course, Introduction and Preview [EoIT, pp. 1--12], discrete random variables, informal statement of the Asymptotic Equipartition Property (AEP); Entropy, Relative Entropy and Mutual Information [EoIT, pp. 13--18], entropy, joint entropy and conditional entropy
Week II [January 16/January 22]
- Topics: Entropy, Relative Entropy and Mutual Information [pp. 19--34], relative entropy and mutual information, Jensen's inequality, concavity of entropy function, Information inequality D(p||q)≥0, interpretation of relative entropy/Kullback-Leibler distance
- Monday January 16 is Martin Luther King, Jr. Day.
- Thursday January 19 WvD is traveling, hence there will be no class.
- Homework 1: "Entropy" will be announced on Thursday, January 19, and will be due on Thursday, January 26, 23:59.
Week III [January 23/January 29]
- Topics: Data Compression, examples of codes, non-singular codes, uniquely decodable codes, prefix/instantaneous codes, Kraft's inequality, proof of Kraft's Inequality; optimal codes, bounds on optimal codelengths, Shannon's Lossless Source Coding Theorem, Huffman codes; Shannon-Fano-Elias coding, arithmetic coding, universal coding, Lempel-Ziv coding, data compression in the real world and other applications of data compression such as machine learning
Week IV [January 30/February 5]
- Topics: Asymptotic Equipartition Property, proof of AEP, data compression as a consequence of AEP, high probability sets and the typical set; Gambling and Data Compression
Week V [February 6/February 12]
- Topics: Gambling and Data Compression; Kolmogorov Complexity
Week VI [February 13/February 19]
- Topics: Kolmogorov Complexity
- Thursday February 16 WvD will be traveling hence there will be no class.
Week VII [February 20/February 26]
- Monday February 20 is Presidents' Day.
- Topics: Channel Capacity, channels, some examples of noisy channels, informal statement of channel coding theorem, jointly typical sequences, proof of noisy channel theorem
Week VIII [February 27/March 4]
- Topics: error correcting codes, Hamming distance, Hamming codes, linear codes, Hamming bound, perfect codes
Week IX [March 5/March 11]
- Topics: Rate Distortion Theory
- Thursday March 8 WvD will have no office hours
Week X [March 12/March 16]
- Topics: quantum information theory
Finals Week [March 17/March 23]