## Course Description

This course serves as an introduction to formal models of languages and computation. Topics covered include finite automata, regular languages, context-free languages, pushdown automata, Turing machines, computability, and NP-completeness.

This course has substantial mathematical content. It is expected
that a student who enrols for this course *already knows how to write
mathematical proofs* and is generally mathematically mature. If a
student passes this basic criterion and is interested in thinking
philosophically about what a computer can or cannot do, then this course
should be great fun.

## Administrative Information

- Instructor
- Amit Chakrabarti | Sudikoff 107 | Office hours Fri 11:15-12:00, Mon 11:15-12:00, or by appointment
- Teaching Assistant
- Zephyr Lucas | Office hours Sun 15:00-16:00 in Sudikoff 213, Mon 14:45-15:45 in Sudikoff 004
- Getting Help
- Primary method: piazza
- For exceptional circumstances: Email cs39@cs.dartmouth... (Don't email just the professor; the TA needs to be in the loop)
- Prerequisites
- Either CS 30 or CS 31, or
- a
*strong*mathematics backround and permission of the instructor - Required Textbook
- Michael Sipser.
*Introduction to the Theory of Computation*(third edition). - Suggested additional reading; not a required book
- J. E. Hopcroft and J. D. Ullman.
*Intro. to Automata Theory, Languages and Computation*(2nd edition).

## Work and Grading

- Grading Scheme
- Weekly homework (32%); Quizzes (14%); Midterm exam (20%); Final exam (30%); Participation (4%)
- Homework and Exam Schedule
- Eight homework sets, due Tuesday nights at 22:00:00 (i.e., 10:00pm sharp)
- Quiz 1: In class on Mon Apr 15
- Quiz 2: In class on Mon May 13
- Midterm exam: Take home, due Apr 30 at 22:00:00 (no homework due that day)
- Final exam: Take home, 48-hour time limit, due Jun 3 at 11:00:00