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


Parts of this course website are under construction. Any content that's colored light gray is tentative and subject to change.

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: Mon 14:00-15:00, Thu 13:30-14:30
Teaching Assistants
Suman K. Bera | Head TA | Office hours Sun 15:00-16:00, Tue 10:00-11:00 in Sudikoff 245
Kirti Rathore | TA and Grader | Office hours Mon 15:00-17:00, in Sudikoff 245
Getting Help
Primary method: piazza
Only under exceptional circumstances: cs39@cs.dartmouth...
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 16
Quiz 2: In class on Mon May 14
Midterm exam: Take home, due May 1 at 22:00:00 (no homework due that day)
Final exam: Take home, 48-hour time limit, due Jun 4 at 11:00:00


No-Laptop/No-Phone Policy

We have a firm no-laptop/no-phone policy in class. Texting, sleeping or engaging in other activities unrelated to the class is also forbidden. This policy will be strictly enforced so as to encourage active participation by all students and to avoid distracting people that are focusing on the lecture. If you come to class you are expected to obey this policy. A penalty of 5% will be applied to the final grade every time this policy is violated. (Please read this article to better understand this policy.)

Absences and Scheduling Conflicts

The material in each class relies heavily on previous classes, so if you miss a class, it is your responsibility to figure out ways to catch up at once on the material covered. If you have a truly unavoidable academic conflict with one of the scheduled quizzes, you must let me know by 23:59 on Apr 6 (firm deadline) and make alternative arrangements. It is not possible to get an extension or to reschedule the midterm and final exams, so plan accordingly.

Submissions and Lateness Policy

All homework and take-home exams must be turned in electronically, using canvas.

Doing homework on time is crucial to your understanding in this course and being late is strongly discouraged. However, to allow for unexpected and unavoidable issues, you are allowed to be late with a homework submission at most 3 times over the course of the term. On each such occasion, you are allowed to be at most 24 hours late. Any lateness outside these bounds will result in your homework being left ungraded (and earning a score of 0). No exceptions! I urge you to note that being even one second late counts as one of your 3 allowed late submissions: in short, if the Canvas timestamp says you're late, you're late; no exceptions.

Late submissions for the midterm or the final exam will not be accepted. Don't be late with those; they will earn a score of 0 if you're late.

Regrading Policy

If you are unsure why you lost points on a homework or exam problem, or feel that the grader made a mistake, you must act before the resolution deadline for that homework/exam. The resolution deadline for a homework or the midterm is 22:00:00 on the Tuesday after its was due, except for Homework 8, whose resolution deadline is 17:00:00 on June 3. Before the resolution deadline you must first contact the relevant grader(s) and try to resolve the matter with them. If you are unable to resolve the matter at this step, you may (optionally) make a formal regrade request. This must be made within 12 hours of the resolution deadline.

To make such a request you must email the course staff (cs39@cs.dartmouth...) with a subject line that says something like "Formal regrade request for HW4", give evidence of having tried to resolve the matter with the graders, and say why you still feel something is wrong. The professor will then make a final determination. Be aware that if you make a formal regrade request then the professor may regrade your entire homework and the professor typically has stricter standards than the graders.

Academic Integrity

Collaboration on Written Homework

When working on homework problems, you may collaborate and discuss with the course staff and other students enrolled in this term's offering of this course (and not with any other persons). However, when you prepare the final draft of your solutions, you must work entirely by yourself and write answers in your own words. At the top of your submission, you must list all people you collaborated with, received help from, or gave help to. If you did the entire homework on your own, you must state that in writing.


When working on homework problems, you may consult this course's website, any handouts given out in class, discussions on this course's piazza forum, the listed textbooks for this course, and your own notes. "This course" means this particular term's offering of CS 39. Consulting any other sources is forbidden, unless the professor has made an exception in writing.

Quizzes and Exams

Collaboration is absolutely not allowed on the quizzes and exams. Giving and receiving help on exams is forbidden, except that you may ask the course staff for clarifications. The in-class exams are closed-book and closed-notes. The take home exams allow you to consult sources similar to those allowed for the homework; precise instructions will be given on the exams.

These rules will be strictly enforced and any violation will be treated with the utmost seriousness.