CS6800 11F: Syllabus

Note: This is an approximate syllabus; it may change at any time.

1. Lecture 01, Fri, Sep 09 2011
   • Admistrivia
   • Introduction to Information Theory and its applications

2. Lecture 02, Tue, Sep 13 2011
   • Probability primer I

3. Lecture 03, Fri, Sep 16 2011
   • Probability primer II
   • Homework 01 assigned

4. Lecture 04, Tue, Sep 20 2011
   • Entropy and its properties
   • Reading: Cover and Thomas 2.1-2

5. Lecture 05, Fri, Sep 23 2011
   • Conditional entropy, relative entropy, mutual information
   • Reading: Cover and Thomas 2.2-4
   • Homework 01 due
   • Homework 02 assigned

6. Lecture 06, Tue, Sep 27 2011
   • Chain rules, data processing inequality, Fano's inequality
   • Reading: Cover and Thomas 2.5-6, 2.8, 2.10

7. Lecture 07, Fri, Sep 30 2011
   • Compression I: codes and decodability, Kraft's inequality, bounds on optimal codes
   • Reading: Cover and Thomas 5.1-4
   • Homework 02 due
   • Homework 03 assigned

8. Lecture 08, Tue, Oct 04 2011
   • Compression II: more Kraft's inequality, block coding, Huffman codes
   • Reading: Cover and Thomas 5.5-8

9. Lecture 09, Fri, Oct 07 2011
   • Compression III: twenty questions, randomness
   • Reading: Cover and Thomas 5.7, 5.10, 5.11, 13.3
   • Homework 03 due

10. Lecture 10, Tue, Oct 11 2011
    • Markov chains, entropy rate of stochastic processes
    • Reading: Cover and Thomas 4

11. Lecture 11, Fri, Oct 14 2011
    • Asymptotic Equipartition Property (AEP) and its consequences
    • Reading: Cover and Thomas 3
    • Homework 04 assigned

12. Lecture 12, Tue, Oct 18 2011
    • Lempel-Ziv, universal source coding
    • Reading: Cover and Thomas 13.4-5

13. Lecture 13, Fri, Oct 21 2011
    • Arithmetic codes, Fibonacci codes, Elias Omega codes
    • Start information theory and statistics: the method of types and applications
    • Reading: Cover and Thomas 13.2-3, 11.1-6

14. Lecture 14, Tue, Oct 25 2011
    • Finish information theory and statistics: the method of types and applications
    • Start large deviation theory
    • Reading: Cover and Thomas 11.1-6
    • Homework 04 due

15. Lecture 15, Fri, Oct 28 2011
    • Finish large deviation theory
    • Start the maximum entropy method
    • Reading: Cover and Thomas 12.1-2

16. Lecture 16, Tue, Nov 01 2011
    • Finish the maximum entropy method
    • Reading: Cover and Thomas 12.1-2
    • Homework 05 assigned

17. No Class, Fri, Nov 04 2011
    • No class... (Prof. Aslam out of town)

18. Lecture 17, Tue, Nov 08 2011
    • Channel coding
    • Reading: Cover and Thomas 7

19. No Class, Fri, Nov 11 2011
    • No class... (Veteran's Day)

20. Lecture 18, Tue, Nov 15 2011
    • Entropy: Approximations and Applications
      • recurrences involving entropy
      • approximations of entropy
      • Renyi entropy
    • Homework 05 due

21. Lecture 19, Fri, Nov 18 2011
    • Finish Renyi entropy
    • Finish channel coding

22. Lecture 20, Tue, Nov 22 2011
    • An information-theoretic design criteria for mobile device keypads

23. No Class, Fri, Nov 25 2011
    • No class... (Thanksgiving Break)

24. Lecture 21, Tue, Nov 29 2011
    • MDL, the minimum description length principle
    • The information bottleneck method (Golbus)

25. Lecture 22, Fri, Dec 2 2011
    • An information-theoretic similarity metric (Palshikar)
    • One-way functions and pseudorandom generators (Mayberry)
    • Network coding I (Harwood)
    • Network coding II (Bhat)

26. Lecture 23, Tue, Dec 6 2011
    • Gambling and investments (D. Liu)
    • Machine learning: decision trees (Ede)
    • NLP: language trees and zipping (Ekstrand-Abueg)
    • Kolmogorov complexity (Glenn)

27. Lecture 24, Fri, Dec 9 2011
    • ML/IR: text categorization (Zhang)
    • IR: language modeling (Mai)
    • ML/IR: clustering (Y. Liu)
    • Computational biology (Balasubramanian)

Switch to:

• CS6800 11F Home Page