CS 39: Theory of Computation
Spring 2019 | 10 hour (MWF 10:10-11:15, x-hr Th 12:15-13:05) | Sudikoff 115

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

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)
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