Introduction to the Theory of Computation

Samir Chopra

Tues/Thurs 11:00 a.m.-12:15 p.m.
CIWW 102

Textbook: "Elements of the Theory of Computation" by Lewis and Papadimitriou (2nd Edition), Prentice-Hall, ISBN #: 0-13-262478-8.

Typos in the textbook can be found here

The official course description is here.

Course Syllabus

The class requires some background in Discrete Mathematics and Algorithms. Chapter 1, Sections 1 through 6 provide all the math needed; students would do well to look through these sections and brush up on any material that looks unfamiliar. Some copies of the textbook might still be available in the bookstore. Unfortunately, the first edition of the textbook is not good enough, since there are significant differences between the two in terms of content and style.

Homework Assignments:

Homework 1

Homework 2

Homework 3 Solutions for HW3

Homework 4

Interesting Links:

The Alan Turing Home Page

Hilbert's Tenth Problem

The Church-Turing Thesis

P and NP :)

Does a Rock implement every finite state automaton?