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

- 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 (112^{th} 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.