Babbage's Analytical Engine
COMS 3261: Computability, Fall 2004
Columbia University
Fall 2004
Monday and Wednesday, 9:30-10:45 am
633 Mudd


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.

  • 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:
    1. Wednesday, October 20
    2. 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.

Last modified: Thu Oct 14 15:37:27 2004