Computability and Algorithms

Spring 2016

MWF 9-10: Klaus 1456

Instructors: Eric Vigoda and Santosh Vempala
(email: vigoda,vempala <at>

Office hours: MW 10-11 (for the instructor who lectures) and by appointment

TAs: Yue Li, Bhavishya Mittal, and Jia Tan
(email: yueli, bmittal6, tanjia <at>
TA office hours: TBD

The office hours are located in between the theory labs (Klaus 2124 and Klaus 2116).

Grading: HW: 10%, Programming project: 10%, Midterm exams (3): 50% Final: 30%.

Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate who you worked with on your solution. Avoid looking up solutions online or in references.

The following books provide background beyond class notes, and we will refer to some of them from time to time:

Algorithms [Dasgupta, Papadimitriou, U. Vazirani]

Algorithm Design [Kleinberg, Tardos]

Foundations of Data Science [Blum, Hopcroft, Kannan]

Introduction to the Theory of Computation [Sipser]

Computational Complexity [Papadimitriou]

Computational Complexity: A Modern Approach [Arora, Barak]