Information Theory: Math 696-Special Topics, Fall 2001
Schedule and Assignments



In the schedule and on the assignment sheets,
PI refers to Abramson's book, Probability and Information Theory.
EPT refers to Chung's book, Elementary Probability Theory.
PRP refers to Grimmet and Stirzaker's book Probability and Random Processes.

Schedule

I will try to keep to this schedule but will update it as needed. -->
Day Topics Preparation
Wed. 9/5 Introduction .
Fri. 9/7 Counting formulas, gambling problems PI Ch. 2; EPT Ch. 3
Mon. 9/10 Boolean algebras PI Ch. 3
Wed. 9/12 Finite probability spaces, random variables PI Ch. 4
Fri. 9/14 Expected value, examples PI Secs. 5.1-3; EPT Secs. 4.1-4
Mon. 9/17 Conditioning PI Sec. 4.3; EPT Secs. 5.1-2
Wed. 9/19 Joint probabilities, Bayes' theorem PI Sec. 4.4; EPT Secs. 5.1-2
Fri. 9/21 Channel maps, Markov processes PRP p. 75-77, 195-200
Mon. 9/24 Simpson's paradox, Markov processes PRP p. 19-20, 75-77, 195-200
Wed. 9/26 Classification of channels, the binary symmetric channel My notes.
Fri. 9/28 A menagerie of random variables
and expectations
PI 5.1-3, 5.7-8
Mon. 10/1 Moments, variance, generating functions PI 5 ex. 37-41
Wed. 10/3 Joint distributions, covariance, correlation PI 5.4
Fri. 10/5 Generating function for joint distributions and
the sum of random variables
PI 5.6-7,
Mon. 10/8 The Poisson distribution,
conditionals and generating functions
PRS 3.7, 5.2
Wed. 10/10 Problem session .
Fri. 10/12 Information content, entropy PI 6.1-2
Mon. 10/15 Entropy and its properties
the grouping law
PI 6.2-3
Wed. 10/17 Axiomatic derivation of entropy PI 6.6
Fri. 10/19 Bounds on entropy PT 6.2-3
Mon. 10/22 Information with 3 random variables,
conditional information. Venn diagrams
.
Wed. 10/24 Markov chains .
Fri. 10/26 An example with I(X,Y,Z) negative
the maximum entropy principle
Sec. 6.5
Mon. 10/29 More on the maximum entropy principle Sec. 6.5
Wed. 10/31 Source coding for data compression Sec. 7.3
Fri. 11/2 The Kraft-McMillan inequality Sec. 7.3
Mon. 11/5 Huffman codes, they are compact P. 124-125, handout
Wed. 11/7 Noiseless coding theorem, Shannon codes Sec. 7.4
Fri. 11/9 Shannon codes .
Mon. 11/12 Shannon-Fano-Elias codes .
Wed. 11/14 Arithmetic codes: preliminaries .
Fri. 11/16 Arithmetic codes .
Mon. 11/19 Efficient Encoding/decoding
of arithmetic codes
.
Wed. 11/21 Dictionary methods: Ziv-Lempel 77 .
Mon. 11/26 Ziv-Lempel 78 and variants .
Wed. 11/28 Codes for error correction PI Sec. 7.1, 5
Fri. 11/30 Linear codes over finite fields .
Mon. 12/3 Reed-Solomon codes .
Wed. 12/5 Law of large numbers and other preparatory results PI 7.5, 8.4
Fri. 12/7 Channel capacity PI 7.5
Mon. 12/10 Noisy Coding Theorem .
Wed. 12/12 Evaluation and miscellaneous .
Fri. 12/14 Questions .

Assignments

Due dates may change depending on schedule.
Assignment Topics covered Due date

First Assignment
Combinatorics Fri. 9/14

Second Assignment
Expected value Wed. 9/26

Third Assignment (ps file)
Third Assignment (pdf file)
Conditional and joint probabilities, Bayes' Theorem
Markov chains, Simpson's paradox
Wed. 10/3

Fourth Assignment
Discrete Random variables, generating functions Fri. 10/12

Fifth Assignment
Entropy Mon. 10/22

Sixth Assignment
Information Mon. 10/29

Seventh Assignment (ps file)
Seventh Assignment (pdf file)
Noiseless coding theorem,
Huffman, Shannon and arithmetic codes
Wed. 11/21

Eighth Assignment (ps file)
Eighth Assignment (pdf file)
Ziv-Lempel algorithms Wed. 11/28

Ninth Assignment (ps file)
Ninth Assignment (pdf file)
Channel capacity, etc. Fri. 12/14