Fall 2024 CS235
Welcome to CS235, an introduction to the theory of computation
Tanner Conference
Thanksgiving
Thanksgiving
Thanksgiving
Assessment 4
Assessment 3 (retake)
Where do we go from here?
Reading Period
Reading Period
Final Exams
Final Exams
Final Exams
Final Exams
Digital computers can do a great deal that is useful, but not everything that is useful. Computers can be taught to recognize lots of complicated languages, but not all languages. The goal of CS235 is to explore the power and limitations of the modern digital computer.
We will introduce several restricted models of computing machines: finite automata; pushdown automata; and Turing machines. Each model assumes an esstential role in computer science. For example, finite automata are used to design and implement digital logic circuits. Pushdown automata and the languages they recognize are central to the theory of programming languages. Program time and space complexity are analyzed using Turing machines. Taken together, these models form an elegant theory of languages and computation. We will focus on the language aspects of this theory through an exploration of the Chomsky hierarchy of languages: finite automata and regular languages; pushdown automata and context-free grammars; Turing machines and recursively enumerable languages.
After a brief introduction to the theory of computation, we begin by introducing the problem of representation of languages by finite specifications. Initially, we will study the simplest language recognition devices: finite automata. Next, we will investigate properties of languages accepted by these machines. Then we switch gears and study an alternative model of computation: context-free grammars. By adding a stack memory to our finite state machines, we prove the equivalence of these two notions of computation. We complete our hierarchy of languages and computation by studying Turing machines and exploring the limits of computer power. The course concludes by examining complexity theory.
The aim of this course is to enable students to engage in a world shaped by computation, so that students can evaluate and distinguish problems that can and cannot be solved by computers, and students can understand and analyze the complexity of such problems.
Students who complete this course should be able to:
The textbook for the course is Introduction to the Theory of Computation, 3rd Edition by Michael Sipser, published by Cengage Learning.
Throughout the semester you will compile your portfolio, consisting of assignment submissions, video-proofs, and proof-feedbacks.
Each video-proof has to explain a different proof and it has to be submitted individually, even if you submitted that particular proof as part of a team. Each video-proof has to explain a proof in a different module (so having two video-proofs in your portfolio covering material from the same module won’t satisfy the requirement). The instructor will view your video-proof (not other students), but the intended audience for your proof should be an imaginary student who is taking the class and is struggling a little with the material (so make sure to use clear language, not to skip any steps, to describe all work, etc.).
You will be providing feedback on others' proofs - sometimes proofs from the instructor and sometimes proofs from other students. When you are providing feedback for other students' proofs, you will receive an email from the instructor containing the proof. The target audience of your feedback here is a fellow class mate. There is an expectation of clear, effective, and respectful language. Nonetheless, the feedback will be seen only by the instructors and will not be shared with your class mate.
We design the course (scaffolding assessments, scheduling office hours, etc.) so that, given the expected number of hours a student would spend on CS 235 as a 1-credit course, assignments can be completed during the appropriate window in the calendar. Since much of the course material cumulatively builds off of previous content from earlier in the course, it is necessary to keep on schedule so that students have the background to engage with the material as it appears in class, and to work effectively with their classmates. Keeping on schedule is also helpful to avoid becoming overwhelmed, and to put students’ best self forward. For these reasons, excepting the lateness coupons described below, we cannot accept late assignment/video-proof/proof-feedback submissions. In extenuating circumstances (e.g., sickness, personal crisis, family problems, religious holidays), you may request an extension. We will often require that an extension request be made on your behalf by your dean.
In order to offer some amount of flexibility and exception to the above policy, we offer five lateness coupons to be used at the discretion of each student:
Assignments are due on Gradescope at 9:30am on the due date indicated in the course calendar. Solutions will be handed out in class. Assignments are graded on a completion basis. You may receive some qualitative feedback on your assignments, and we recommend you read it carefully, in order to, over time, improve your proof writing style, clarity, and effectiveness. It is beneficial to student learning for course work to be completed regularly throughout the semester, so make sure to submit what you have, in whatever state it’s in, by the given deadline.
Video-proofs are due on Gradescope at 5:00pm on the due date indicated in the course calendar. Video-proofs are graded on a completion and best-effort basis – if, after viewing the video, we can’t follow your proof, you will be asked to submit another video for the same proof.
Proof-feedbacks are due on Gradescope at 5:00pm on the due date indicated in the course calendar. Proof-feedbacks are graded on a completion and best-effort basis – if, after reading your feedback, we can’t follow the feedback, or it is incorrect (e.g. claiming a proof is correct when it isn’t), you will be asked to submit the feedback for that proof again.
Module assessments are not subject to extensions. Their dates are fixed, as noted in the course calendar. Please arrange accommodations with the instructor at least 5 days ahead of module assessments. If an emergency prevents you from completing the assessment as scheduled, we can schedule a make-up assessment with the support of your class dean or health services. This sets a common standard for all students and ensures you are getting the support you need for your emergency.
We believe that collaboration fosters a healthy and enjoyable educational environment. For this reason, we encourage you to talk with other students about the course material and to form study groups.
You are encouraged on any assignment (but not video-proof, proof-feedback, quiz, or module assessment) to form a two-person "team" with a partner. The two team members must work closely together on the assignment and turn in a single assignment submission for the team. The grade received on such a submission will be given to both team members. When considering who to partner with for an assignment, you may find your own partner or you may use this shared Google document to indicate your interest in working with a partner.
Team efforts on assignments are subject to the following ground rules:
Unless otherwise instructed, teams are allowed to discuss problem sets with other teams and exchange ideas about how to solve them. However, there is a thin line between collaboration and plagiarizing the work of others. Therefore, I require that each (one-person or two-person) team must compose its own solutions to each assignment. In particular,
You must compose your own solution to each assignment. You may discuss strategies for approaching the problems with your classmates and may receive general advice from them, but you are required to write up all of your own solutions. Furthermore, you should never look at another student's solutions.For example, it is OK to borrow ideas from the textbook, from materials discussed in class, and from other sources as long as you give proper credit. However it is unacceptable and constitutes a violation of the Honor Code (1) to write a solution together (with someone not part of your team) and turn in two copies of the same solution, (2) to copy a solution written by your classmates, (3) to read another student's or team's solution, (4) to view assignments, assessments, and solutions from previous terms of CS235, (5) to ask someone for solutions from previous terms of CS235, (6) to make any of the assignment or assessment solutions available for others online or offline, or (7) to post CS235 assignment/assessment problems to stackexchange, ChatGPT, or other such resources to get help in solving the problems (if you don't know whether using a particular resource is a violation of the Honor Code, it is your responsibility to check in with the instructors before using it).
In keeping with the standards of the scientific community, you must give credit where credit is due. If you make use of an idea that was developed by (or jointly with) others, please reference them appropriately in your work. It is unacceptable for students to work together but not to acknowledge each other in their write-ups.
Your final grade will be based on a weighted average of the following components:
At the end of the semester, we will compute a weighted average for each student and assign letter grades. In general, the mapping from numerical score to letter grade looks like this: >= 93.33 is an A, >= 90.00 is an A-, >= 86.67 is a B+, >= 83.33 is a B, >= 80.00 is a B-. >= 76.67 is a C+, >= 73.33 is a C, >= 70.00 is a C-, >= 60.00 is a D and < 60.00 is an F.
Depending on the overall performance of the class, we may adjust this mapping.
There are CS235 Google Groups named
CS-235-01-FA24
and CS-235-02-FA24
.
These groups have several purposes. We will use it to make
class announcements, such as corrections to assignments and
clarifications of material discussed in class. We encourage you
to post questions or comments that are of interest to students
in the course. The instructor will read messages
posted to the groups on a regular basis and post
answers to questions found there. If you know the answer to a
classmate's question, feel free to post a reply yourself. The
course groups are also good places to find people to join
a study group. You should plan on reading messages sent to the group
on a regular basis.
Masks will be optional in this class. Please note that masks are an important tool in helping limit the spread of COVID-19 and other respiratory illnesses. We kindly ask you to wear a mask if you feel unwell, have sniffles, or think you may have been exposed to someone with COVID-19 or the flu. The instructor reserves the right to ask you to mask up or change policies on masking during the semester.
Please be respectful to members of our community (students, faculty, staff, and others) who choose at any point in time to wear or not to wear a face mask. Please refrain from making any judgments as masking may help reduce allergies, prevent the spread of respiratory illnesses, or protect immunocompromised individuals or their families.
Here is a form for providing anonymous feedback to the instructor. You must be logged in to a Wellesley account to use the form, however neither your email address nor any other identifying information will be recorded.
If you have a disability or condition, either long-term or temporary, and need reasonable academic adjustments in this course, please contact Accessibility and Disability Resources to get a letter outlining your accommodation needs, and submit that letter to me. You should request accommodations as early as possible in the semester, or before the semester begins, since some situations can require significant time for review and accommodation design. If you need immediate accommodations, please arrange to meet with me as soon as possible. If you are unsure but suspect you may have an undocumented need for accommodations, you are encouraged to contact Accessibility and Disability Resources. They can provide assistance including screening and referral for assessments.
Accessibility and Disability Resources can be reached at accessibility@wellesley.edu, at 781-283-2434, by scheduling an appointment online at their website www.Wellesley.edu/adr , or by visiting their offices on the 3rd floor of Clapp Library, rooms 316 and 315.
Pursuant to Wellesley College policy, all employees, including faculty, are considered responsible employees. That means that any disclosure of discrimination, harassment, or sexual misconduct to a faculty member will need to be shared with the College's Director of Non-Discrimination Initiatives / Title IX and ADA / Section 504 Coordinator (781-283-2451; titleix@wellesley.edu). Students who do not wish to have these issues disclosed to the College should speak with confidential resources who are the only offices at the College that do not have this same reporting obligation. On campus, confidential resources include Health Services (781-283-2810 available 24/7), the Stone Center Counseling Services (781-283-2839 available 24/7) and the Office of Religious and Spiritual Life (781-283-2685). You should assume that any person employed on campus outside of these three confidential offices has an obligation to share information with Wellesley College through the Office of Non-Discrimination Initiatives.