198:509: Foundations of Computer Science

Meeting times and location: Mondays and Wednesdays in Beck Hall 252 (Livingston); 3:20--4:40

Professor Eric Allender


Phone: (848) 445-7296
FAX: (732) 445-0537

Email: allender@cs.rutgers.edu

Office: Hill 442
Click here for current Office Hours.


Grader: Harsha Srimath Tirumala


The text for the class is: Theory of Computation by Dexter Kozen. It appears that the book is also available in electronic form. Here is information about errata in the textbook. Let me know about additional errors as you discover them. We will also augment with some material on Kolmogorov complexity, by Lance Fortnow.
Click here to find out about what was covered in class, and what material you should read next.

Rough Outline


Prerequisites:Graduate standing.

Expected Work: There will be one midterm and one (take-home) final. The midterm will be held in class. In addition, there will be homework every two or three lectures; this homework is a major consideration in assigning grades.