Computer Science Theory for the Information Age, Spring 2012.

15-496/15-859X: Computer Science Theory for the Information Age, Spring 2012

Instructors: Venkatesan Guruswami and Ravi Kannan

Time: Tuesdays & Thursdays, 1:30-2:50 PM, WEH 5421. (First lecture on January 17, 2012)

Office hours:

Venkat: Tuesdays, 4:30-5:30pm
Yuan: Wednesdays, 4:30-5:30pm

Course material

The course will be based on a draft of an upcoming book by John Hopcroft and Ravi Kannan. Chapters of the book will be posted here as the course proceeds. Here is a draft of the table of contents of the book to give you an idea of the topics. There is no other required text for the course.

Draft of the whole book (will be periodically updated)
Notes 1: Geometry of high-dimensional space
Notes 2: Singular Value Decomposition
Notes 3: Algorithms for Massive Data Sets
Notes 4: Random graphs (see Chapter 3 of draft of whole book)
Notes 5: Markov chains
Notes 6: Learning theory (see Chapter 6 of draft of whole book)
Notes 7: Clustering

Problem sets

Problem set 1 (due Thursday, Feb 2) PS1 Solutions
Problem set 2 (due Friday, Feb 17) PS2 Solutions
Problem set 3 (due Friday, Mar 9) PS3 Solutions
Problem set 4 (due Thursday, Mar 29) PS4 Solutions
Problem set 5 (due Friday, April 13) PS5 Solutions
Problem set 6 (due Thursday, April 26) PS6 Solutions

Take Home Final (due Friday, May 4)

Solutions to final

Course Description

In the first 50 odd years of its existence, computer science and the mathematical theory supporting it have flourished, enabling the widespread use of computing and algorithms today. Today, a fundamental change is taking place in computer science with the focus shifting from making computers useful and more towards applications. The reasons for this change are many, including the merging of computing and communication, the pervasiveness of data in digital form, and the emergence of social and sensor networks. With this in mind, this course will aim to cover the mathematical theory likely to be important for algorithmic applications in the next few decades. One of the major changes is the switch from discrete mathematics to an increased emphasis on probability, statistics, linear algebra, high-dimensional geometry, etc. The course will cover a spectrum of such topics, the following being a suggestive list of possibilities:

The geometry of high-dimensional space (concentration of measure, dimension reduction,...)
Singular value decomposition
Random graph models and threshold phenomena
Markov chains and rapid mixing
Algorithms for massive data problems (sampling,streaming)
Graphical models and belief propagation
Compressed sensing and coding
Learning and VC-dimension
Spectral methods and applications (eg. clustering)

Prerequisites/Intended audience

The course is cross-listed as a joint undergraduate/graduate course. The course will be fast paced and theoretical, so mathematical maturity and comfort with material in 15-251 and basic algorithms is required. The suggested prerequisites are 15-251 and 15-451. (In exceptional cases, if you haven't taken these courses at CMU but feel that you have the required mathematical background and would like to try this course, you may sign-up for the course after the obtaining the instructors' permission.) Students who have taken 15-359 and enjoyed it are particularly encouraged to consider taking this course. The overlap with 15-359 will be small, so doing both courses in parallel is also encouraged.

Grading: The grading will be based on roughly bi-weekly problem sets, attendance and class participation, and a final exam. For the graduate version, a class project might be possible in lieu of the final (this is tentative, and details will be confirmed and made clear later on).

Maintained by Venkatesan Guruswami