Fall 2024 CS235

Overview

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.

Learning Goals

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:

• Apply mathematical concepts, especially proof techniques, to problems in theoretical computer science.
• Identify languages at different levels of the Chomsky hierarchy.
• Design appropriate finite state machines to recognize different languages.
• Analyze the limits of different computational models such as finite automata, pushdown automata, or Turing machines.
• Describe examples of problems at each level of computability and complexity.
• Explain computability, complexity, undecidability, and NP-completeness at various degrees of technical detail.
• Argue formally whether a problem admits efficient solutions using theory of computation proof techniques.
• Communicate theory of computation concepts effectively through different media, such as writing formal proofs, drawing representations of computational models, and creating video presentations of proofs.
• Develop the practice of providing feedback for others’ proofs and arguments.
• Work collaboratively with partners or small groups to solve theory of computation problems.

Textbook

The textbook for the course is Introduction to the Theory of Computation, 3rd Edition by Michael Sipser, published by Cengage Learning.

Course Requirements

• Class meetings: Class meets twice per week. If you miss a class for some reason, you are responsible for studying the notes on the course website (and corresponding reading from the text). If you have questions about the material, you should see the instructor during regular office hours.
• Class videos: Videos are available to introduce many but not all topics. Videos should be watched before the corresponding class so that you come to class prepared to engage in activities based on material presented in the video. Videos usually have corresponding quizzes. The quiz corresponding to a video should be taken after watching the video and before coming to class.
• Quizzes: Many classes have videos that introduce new material, and most of these videos have corresponding quizzes. Before class, you should watch the video and then take the quiz. The purpose of each quiz is to help you assess your understanding of the most recent material. You may take a quiz as many times as you like and only your highest score on that quiz will be retained.
• Portfolio: Throughout the semester you will be compiling a portfolio of proofs that you complete, videos walking others through your proofs, and providing feedback for others' proofs.
  • Assignments: During the term, there will be regular homework assignments. You can complete these individually or in teams of two students, though you cannot work with the same person twice.
  • Video-proof: A "video-proof" is a video recording of yourself walking through a proof from an assignment, while writing it. You will submit 3 of these videos by the end of the semester, each one corresponding to a proof in a different module. Problems on assignments that qualify as candidates for these video-proofs will be marked as such.
  • Proof-feedback: You will provide thoughtful and rigorous feedback for others' proofs. Some of the proofs that you will provide feedback for will be from the instructors and some will be from other students.
• Module assessments: The course is split into four modules. There will be an assessment for each module, so there will be four module assessments during the semester. The assessments will be in-class and will be closed book and closed notes.

Portfolio

Throughout the semester you will compile your portfolio, consisting of assignment submissions, video-proofs, and proof-feedbacks.

Video-proofs

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

Proof-feedbacks

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.

Late Policy

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:

1. Each student gets five lateness coupons. Each coupon corresponds to a 24-hour extension. Coupons can be used at any time during the semester up to the last day of classes but may not be used to extend deadlines into reading period or final exam period (College legislation restricts work, other than final exams/papers/projects from being due after the last day of classes). Coupons may not be used for module assessments. Multiple coupons may be used for a single assignment or distributed across assignments as a student deems best.
2. Coupons are not fractional in nature. If an assignment is one hour, or twelve hours, or 24 hours late, one entire coupon must be used.
3. A coupon can be used only on assignments, not on module assessments.
4. For partnered assignments, only one team member needs to use coupons for each 24 extension. Thus, if the partnered group wants to submit an assignment 3 days after the deadline, one team member can use 3 coupons while the other uses 0 coupons, or one team member can use 2 coupons while the other uses 1 coupon. It is up to the team members to work this out together in advance.
5. While we use the term "coupon" there are not actually physical coupons. A student simply submits a Google form each time they use a coupon, indicating how many coupons they are using, i.e., how many days late they are submitting the assignment. You can access the Google form here.

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.

Collaboration Policy

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:

• The work must be a true collaboration in which each member of the team will carry their own weight. It is not acceptable for two team members to split the problems of the assignment between them and work on them independently. Instead, the two team members must actively work together on all parts of the assignment.
• You can only work with a given partner on a single assignment during the semester. So if you want to continue to collaborate, you must choose a different partner for every assignment. Rotating through partners is a good way to build community in the class and is helpful for avoiding situations where one individual feels pressured to continue working with another.
• You are encouraged to work with a partner on all assignments but you are not required to do so. Based on past experience, working with a partner can significantly decrease the amount of time you spend on an assignment, because you are more likely to avoid silly errors and blind alleys. You are also more likely to have a deeper understanding of a problem if you talk it through with someone else.

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.

Grading Policy

Your final grade will be based on a weighted average of the following components:

• Module 1 assessment: 20%
• Module 2 assessment: 15%
• Module 3 assessment: 15%
• Module 4 assessment: 10%
• Quizzes: 5%
• Portfolio: 35%
  • Assignments: 5%
  • Video-proofs: 15%
  • Proof-feedbacks: 15%

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.

Google Group

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.

Masking

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.

Anonymous Feedback Form

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.

Disabilities and Accommodations

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.

Faculty Responsibilities on Disclosures of Discrimination, Harassment, and Sexual Misconduct

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.