Princeton University -- Department of Computer Science

COS 597D: Information theory in computer science

Fall 2011

Instructor: Mark Braverman, CS Building 411.
Meeting time&location: MW 3:00-4:20; Friend room 108.
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.
Links: 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.

Assignments

Due date Assignment
Jan 11 (outline due on Nov 28) Final presentation [pdf]
Oct 31 Assignment 2 [pdf]
Oct 12 Assignment 1 [pdf]

Announcements

Date Announcement(s)
Nov 15
(Tue)

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

Oct 17
(Mon)

    Assignment 2 has been posted. Due date is October 31.

Sept 25
(Sun)

  • 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

Lecture date Notes
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]