## 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?