Notice

This course has ended. This website exists for archival purposes.

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: 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...

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

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

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