Columbia University
Fall 2004
Monday and Wednesday, 9:30-10:45 am
633 Mudd
People:
Instructor: Zeph GrunschlagOffice 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.
- Salman Baset
Monday 11:00 am - 1:00 pm in the Mudd basement TA room. - Gabriella Cretu
Office hours: Wednesday 11:00 am - 1 pm in CEPSR 6LE1.
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).
Important Dates:
- Bi-Weekly homework assignments (see schedule)
- Midterm Exams in class:
- Wednesday, October 20
- Monday, November 22
- Pre-Election Holiday: no class Monday, November 1
- Final exam: In class, Monday, December 12
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.