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