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

Basic Policies

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 Fri Apr 5 (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.

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.

Graded Work

Submissions and Lateness Policy

All homework and take-home exams must be turned in electronically, using file upload on 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.


Start working on each homework set the day it is posted. The problems won't be solvable in one sitting. Sleep on them; the solutions will come to you over the course of several days.

Do not put off homework submission until the last few minutes before the deadline! It can cost you a lot. The deadline is totally strict. You are responsible for ensuring that a clear, complete, and readable submission has been uploaded to Canvas before the deadline. So, before the deadline has elapsed, go on Canvas and access your submission there to make sure all is good.

Homework Grading Standards

Several homework problems will be long-answer questions worth 7 points. On such problems, our grading guidelines are as follows.

  • 7 points: A mathematically correct and concise solution that is written well. Contains no errors other than perhaps small spelling mistakes and minor grammatical errors.
  • 6 points: A basically correct solution but with one of the following small flaws.
    • One or two small typos that makes the solution technically wrong.
    • A proof that is missing one or two minor steps of reasoning.
    • A mathematically correct solution but with grammatical errors that make parts of it hard to read or confusing. This includes not writing in complete sentences.
    • An otherwise correct solution that is a bit longer than necessary and the excess length subtracts from its clarity.
  • 5 points: A mostly correct solution with more than a minor flaw. For example
    • Minor flaws in two or three places, as above.
    • Mathematically correct solution but with poor grammar throughout.
    • A correct solution that is much longer than necessary (e.g., writing two full pages when half a page would have sufficed).
  • 4 points: A solution that is on the right track but has a big mistake somewhere. To get this score, the problem must require at least two major ideas and the mistake cannot be in the more/most important idea.
  • 3 points: An attempted solution that has some of the important ideas required but with a mistake in the most important idea.
  • 2 points: An attempted solution that solves only a easy special case of the problem, where solving the full problem would require much more sophisticated idea(s).
  • 1 point: An answer that would qualify for 2 points except that it has typos or small errors.
  • 0 points: An answer that does not make useful progress towards a solution, or is a solution to something other than what was asked.

In all cases, too many typos, too many flaws in grammar, or excessive length (as indicated under "6 points" and "5 points" above) may cause 1 or 2 points to be taken off.

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 22:00:00 on June 2. 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.

Extra Credit and Solutions

Challenge Problems

Many homework sets will have one or two "challenge problems" accompanying the regular homework. These are meant to provide a higher level of challenge for students who want to dig deeper into the subject and relish a strong challenge. My recommendation is that you think about these problems only if you have completed the regular homework and you found the homework easy. Your grade will never suffer because of not working on challenge problems and in fact it is unwise to skimp on regular homework to work on these challenge problems.

If you do solve a challenge problem, don't submit it with your regular homework. Instead, put a hardcopy (printout, write-up) of your solution in Professor Chakrabarti's mailbox before class on the day after the homework is due (i.e., by Wednesday 10:00 am). This is considered extra-credit work, so it won't be graded in the usual sense, but Professor Chakrabarti will keep a count of how many of these you have solved over the term. Only 100% rigorous solutions will count!

Don't be upset if you cannot solve any of the challenge problems. Most of them are very hard!

Homework Solutions

Sample solutions will (usually) be posted late Wednesday nights on Canvas (under Files). These solutions may subsequently be edited to include a summary "common mistakes" found in students' submissions.

Our sample solutions may be quite different from yours and may point out useful insights. For these reasons, please treat all sample solutions as required reading, even if you solved all the homework problems correctly.