Office Hours: Tuesday and Thursday, 3:00–5:00 and by appointment, Sanders Physics 305
Tuesday & Thursday, 9:00–10:15 a.m., Sanders Physics 105
This course introduces students to the theory of computation, the
mathematical foundation of computer science. We will consider what is an
appropriate mathematical model of a computer, what types of computations are
possible in the model, what types are not, the inherent complexity of certain
computations, etc. Although considering computers as abstract mathematical
objects may on the surface seem unrelated to “real” computing, in
fact many concepts you will encounter are fundamental to important areas of
computer science, including compiler design, hardware design, object-oriented
design, computational linguistics, and even the syntax of the
During the course, you will gain an understanding of the intimate connection between computation and language recognition. We will study several classes of abstract machine including finite automata, push-down automata, and Turing machines, along with several classes of languages such as regular and context-free languages. In addition, we will look at problems like the Halting Problem that are not amenable to a computer solution.
The course provides essential background for CMPU 331, Compiler Design: ideally, you should take CMPU 331 in the semester immediately following completion of this course.
Prerequisites: CMPU 102 and CMPU 145.
The calendar on this page will be updated throughout the semester with readings, assignments, and exams. Schedule a reminder to check it after each class.
The assigned chapters should be read before the corresponding class. You are responsible for keeping up with the reading and for all material covered in class (some of which may not be in the book). This includes classnotes, assignments, handouts, additional readings, etc. If you miss a class for any reason you are responsible for making arrangements with classmates to provide you with all information disseminated in class that day.
Read Chapter 0.
Read Section 1.1.
Read Section 1.2.
Read Section 1.3.
Read Section 1.4.
Exam 1 review
Handout: Exam 1 Topics
Slides: Practice proofs
Assignment 4 out
The primary textbook for this course is Introduction to the Theory of Computation, third ed., by Michael Sipser (2012).
There will be occasional supplemental readings made available on this website or distributed in class.
You are responsible for completing all assigned readings before the class indicated in the schedule on the webpage, whether or not the material is covered in lectures. (Exception: The readings for the first day. Don’t panic.)
One goal of this course is to develop your facility to manipulate language formalisms, so completion of weekly assignments is extremely important.
Assignments and due dates will be listed in the calendar, above. All assignments are due at the beginning of class on the indicated days and should be turned in directly to me.
When computing your final grade for the course, your lowest homework score from among the homeworks that were turned in – on time or late – will be dropped.
As with all policies, homework policies are intended to be fair to everyone involved in the course. They will be enforced fairly. Please feel free to ask me any questions about specific cases that may emerge over the semester.
Each problem will be graded along the following lines:
Note that strong effort as you get better will make up for poorer performances in previous weeks.
NB: Neatness counts! Two points (on the 0–4 scale) will be automatically deducted from any assignment that does not meet the following requirements:
You are encouraged to prepare your assignments using the typesetting language LaTeX, which is a standard tool for publishing research in computer science. To get started, you can refer to Getting Started with LaTeX, go to this list of LaTeX tutorials, or simply enter “latex tutorial” in a search engine to see many other links.
A LaTeX assignment template is available.
I recommend using Overleaf online so you don’t need to install anything and you can get an instant preview of your work. (I use Tectonic, but that’s a non-standard choice.)
Full solutions to all problems will be posted on the course webpage when graded assignments are returned. Exercises and problems in our textbook that are prefaced with an “A” have solutions at the end of each chapter. Be sure you understand all the book solutions as well as the assigned problems.
Permitted, but if you do cooperate, the solutions must be written up individually (not copied). If you cooperate with another student, indicate this on your assignment.
Receiving and copying solutions from any source (a classmate, a friend, a published text, an online source, etc.) is disallowed. Note that using material from sources (other than those explicitly given as course resources) as “inspiration” and submitting highly derivative solutions is viewed as copying. (Please read Going to the Source: A Guide to Academic Integrity and Attribution at Vassar College, available from the Dean of the College website.) Inappropriate use of sources (including people) will be reported to the Academic Panel.
There will be three exams. The first two focus on lectures and readings from the immediately preceding segment of the course. The third exam will focus primarily on later material but may also include material from earlier in the course.
The first two exams may be take-home.
Note that we may not cover all the assigned reading in class, but you are responsible for all assigned readings and all material covered in class for the exams.
The elements of the course will be weighted as follows when determing your overall grade:
|Written Assignments||40%||(About eight problem sets)|
An optional programming assignment may be done for extra credit.
This course includes a lot of detailed information that supports the “big ideas” that we will gain an understanding of during the course. Here are some suggestions for approaching the course material and lectures that can help guarantee that you get the most out of it.
Academic accommodations are available for students registered with the Office for Accessibility and Educational Opportunity (AEO). Students in need of disability (ADA/504) accommodations should schedule an appointment with me early in the semester to discuss any accommodations for this course that have been approved by the Office for Accessibility and Educational Opportunity, as indicated in your AEO accommodation letter.
Vassar College is committed to providing a safe learning environment for all students that is free of all forms of discrimination and sexual harassment, including sexual assault, relationship abuse, and stalking. If you (or someone you know) has experienced or experiences any of these incidents, know that you are not alone. Vassar College has staff members trained to support you in navigating campus life, accessing health and counseling services, providing academic and housing accommodations, helping with legal protective orders, and more.
Please be aware all Vassar faculty members are “responsible employees,” which means that if you tell me about a situation involving sexual harassment, sexual assault, relationship abuse, or stalking, I must share that information with the Title IX Coordinator. Although I have to make that notification, the Title IX office will only provide outreach by email. You will control how your case will be handled – you don’t have to read or respond to the email, and it is completely up to you whether to pursue a formal complaint. Our goal is to make sure you are aware of the range of options available to you and have access to the resources you need.
If you wish to speak to someone privately, you can contact any of the following on-campus resources:
The SAVP website and the Title IX section of the EOAA website have more information, as well as links to both on- and off-campus resources.