Syllabus
If all goes well, we will be studying the following topics, in more-or-less the order given below.
- Discrete probability distributions, random variables (refresher)
- Definition of entropy
- Properties of entropy, Kullback-Leibler (KL) divergence
- Mutual information and its properties
- Entropy and data compression
- Error-correcting codes, communication through a noisy channel
- Sampling of applications of information theory in combinatorics
- Communication complexity and information complexity
- Applications to data structures
- Applications in optimization (extension complexity)
- Applications in game theory (parallel repetition)
- Further applications in combinatorics
Topics and Events, Day by Day
The table below will be updated throughout the term.
Starting with Jan 19, zoom recordings of live sessions can be found by navigating to "Panopto video" on the course's Canvas site. For earlier sessions, the link appears in the table below. These videos aren't accessible outside Dartmouth.
| # | Date | What to do before class | What we did during the live class | Resources |
|---|---|---|---|---|
| 1 | Th Jan 07 | Welcome to CS 49 | Introductions, general comments on how the course will run, reminder of Homework 0 (diagnostic test), reminder to read all course policies. | video recording |
| 2 | Tu Jan 12 | From the course's Canvas site, watch the lectures for Module 1. Complete Homework 0 by tonight, though doing it before class would be ideal. | Review of marginal distributions and product distributions. Discussion about upcoming homework. | video recording |
| 3 | Th Jan 14 | Watch the three videos in Module 2. The third video is mathematically heavy. | Reviewed some of the proofs from Module 2, based on student questions. Used breakout rooms to work on ungraded problems from HW1. Wrapped up with professor's solutions to some of the ungraded problems. | video recording |
| 4 | Tu Jan 19 | View the first video in Module 3. If needed, re-watch the third video in Module 2, making sure you have understood everything there. Submit Homework 1 by tonight. | This was a quick session, with just a little Q&A, mostly on Module 2. | recording |
| 5 | Th Jan 21 | Complete watching all videos in Module 3. | We had a lively session, working through the ungraded problems from Homework 2. We also thought through a couple of questions about Huffman codes beyond what's in the lectures. | recording, whiteboard |
| 6 | Tu Jan 26 | View at least the first video in Module 4. It will help to have worked on HW2 so that some of the ideas in the video feel natural. Submit Homework 2 by tonight. | TBD | tbd |
| 7 | Th Jan 28 | Finish watching all videos for Module 4. Do some thinking about what kind of project you want to take up. | Several students attended and we worked through ungraed problems in Homework 3. The open-ended question about Tunstall coding brought forth some thoughtful responses. | tbd |
| 7x | Fr Jan 29 | Watch the single video in Module 5, which is an interlude. | No live meeting | tbd |
| 8 | Tu Feb 02 | Watch as much as you can of the Module 6 videos. Submit Homework 3 by tonight. | This session was mostly Q&A, with the agenda set by students' questions. | tbd |
| 9 | Th Feb 04 | Finish watching all available videos in Module 6: for now, the impossibility portion of the channel coding theorem has been covered. | No live meeting. | tbd |
| 9x | Fr Feb 05 | The achievability portion of the channel coding theorem is now available: watch those videos, which will complete Module 6. | We worked on the ungraded problems in Homework 4. We plan to finish up this work in next Tuesday's session. | tbd |
| 10 | Tu Feb 09 | Watch the video on error-correcting codes in Module 7. This module will soon be rounded out with other combinatorial applications of information theory. | TBD | tbd |
| 11 | Th Feb 11 | Finish watching all of Module 7. Submit Homework 4 by this afternoon. | TBD | tbd |
| 12 | Tu Feb 16 | TBD | TBD | tbd |
| 13 | Th Feb 18 | TBD | TBD | tbd |
| 14 | Tu Feb 23 | TBD | TBD | tbd |
| 15 | Th Feb 25 | TBD | TBD | tbd |
| 16 | Tu Mar 02 | TBD | TBD | tbd |
| ? | Th Mar 4 | TBD | Final project presentations—I | See projects tab |
| ? | Tu Mar 09 | TBD | Final project presentations—II | See projects tab |