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