##

##
V22.0453-001

##
Introduction to the Theory of Computation

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