(: title COS597D Fall 2011:)

    Princeton University  -- Department of Computer Science
!! COS 597D: Information theory in computer science

Fall 2011



 Mark Braverman, CS Building 411.

Meeting time&location:

MW 3:00-4:20; Friend room 108. <tr>

Course information sheet:

[pdf Δ] (updated September 24).

Brief outline:

We will explore information theory and recent research in computer science that applies information-theoretic techniques. We will start by developing the basic notions from information theory, such as Shannon's entropy, mutual information and Kolmogorov complexity. We will then proceed to explore applications in several areas including combinatorics, communication complexity, and data structures lower bounds.


A similar course taught by Anup Rao at the University of Washington: here.
An outline of a minicourse by Michael Saks covering similar topics, including an extensive reading list: here. </tbody>



 <tr align="left">

<th align="left" valign="top">Due date</th> <th align="left" valign="top">Assignment</th> </tr>

Jan 11 (outline due on Nov 28)

Final presentation [pdf Δ]

Oct 31

Assignment 2 [pdf Δ]

Oct 12

Assignment 1 [pdf Δ] </tbody>


<tbody><tr align="left"> <th align="left" valign="top">Date</th> <th align="left" valign="top">Announcement(s)</th> </tr>

Nov 15

<ul> Final project description has been posted. Presentations will be held on January 11th. Outlines are due on November 28th. </ul>

Oct 17


Assignment 2 has been posted. Due date is October 31. </ul>

Sept 25
  • An updated course information sheet has been posted.
  • Assignment 1 has been posted. Due date is October 12.
  • Lectures 1 and 2 have been posted.


Lecture notes


 <tr align="left">

<th align="left" valign="top">Lecture date</th> <th align="left" valign="top">Notes</th> </tr>

Sept 19

Lecture 1 [pdf Δ]

Sept 21

Lecture 2 [pdf Δ]

Sept 26

Lecture 3 [pdf Δ]

Sept 28

Lecture 4 [pdf Δ]

Oct 3

Lecture 5 [pdf Δ]

Oct 5

Lecture 6 [pdf Δ]

Oct 10

Lecture 7 [pdf Δ]

Oct 12, 17

Lecture 8-9 [pdf Δ]

Oct 19, 24

Lecture 10-11 [pdf Δ]

Oct 24, 26

Lecture 11-12 [pdf Δ]

Nov 7

Lecture 13 [pdf Δ]

Nov 9

Lecture 14 [pdf Δ]

Nov 14, 16

Lecture 15-16 [pdf Δ]

Nov 21, 23

Lecture 17-18 [pdf Δ]