CIS 38

Theoretical Computer Science

Samir Chopra

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

Interesting Links:

The Alan Turing Home Page

Hilbert's Tenth Problem

The Church-Turing Thesis

P and NP :)

The Pumping Lemma - set to rhyme :)

Does a Rock implement every finite state automaton?