]!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
COMS 3261: Computability, Fall 2004
Monday and Wednesday, 9:30-10:45 am
People:Instructor: Zeph Grunschlag
Office Hours: Thursday 1-4 pm in 469 C.S. Building
TA's: You can find out TA office hours and updates from the Columbia Computer Science TA Page.
Prerequisite: Discrete Math (COMS 3203) and Data Structures (COMS 3137) or the instructor's permission.
Topics Covered: Models of Computation and Formal Languages: Deterministic and Non-deterministic Automata, Regular Expressions, Pushdown Stack Automata, Context Free Grammars, Deterministic and Non-Deterministic Turing Machines. Algorithmic Complexity: Complexity of Computational Models, P versus NP, NP-Complete Problems, Undecidable Problems.
Textbook: Introduction to the Theory of Computation by Sipser (PWS Publishing, ISBN: 053494728X). Available at Labyrinth books (112th between Broadway and Amsterdam).
Course Contract: Each student is required to read this contract as it contains important information about the course policy, expectations from students, special cicumumstances, etc.