|
Franklyn Turbak (call me "Lyn") Pronouns: he/him Office: SCI W120 (x3049) Email: fturbak asperand wellesley dot edu Web: http://cs.wellesley.edu/~fturbak |
cs-235-01-sp24@wellesley.edu)
This course offers an introduction to the theory of computation. Topics include languages, regular expressions, finite automata, grammars, pushdown automata, and Turing machines. The first part of the course covers the Chomsky hierarchy of languages and their associated computational models. The second part of the course focuses on decidability issues and unsolvable problems. The final part of the course investigates complexity theory.
Distributions: MM - Mathematical Modeling and Problem Solving
Prerequisites(s): CS 230 and either MATH 225 or permission of the instructor.
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 decidable and recursively enumerable languages.
We will begin with a review of the mathematical concepts and notations that are the foundation of the rest of the course. Key concepts include relations, mathematical functions (in contrast with programming language functions), countability, proof by induction, and the notion of a formal language being a set of strings.
Then we study models of computation that represent formal languages by finite specifications. Initially, we will study the simplest language recognition devices, finite automata, studying both deterministic and nondeterministic variants. We will investigate properties of so-called regular languages accepted by these machines, and will see that that this class of languages can be specified by regular expressions. We will learn the pumping lemma technique to show that certain languages are not regular.
Next, we study more powerful models of computation that describes context-free languages. These include context-free grammars, a way to specify the generation of strings in these languages, and pushdown automata, which extend finite automata with a stack memory. We will prove the equivalence of these two notions of computation, and expand the pumping lemma technique to show that certain languages are not context free.
We complete our hierarchy of languages and computational models by studying Turing Machines, which specify computation in terms of automata that can read and write symbols in the cells of an infinite tape. We will explore the difference between Turing-decidable and Turing-acceptable (recursively enumerable) languages.
Next, we explore the limits of computational power by studying undecidability, which is the notion that certain languages cannot be decided by Turing Machines. The Halting Problem is the canonical example of such a language. We will learn the notion of reducibility, and see how knowing that certain languages are undecidable can help prove that other languages are undecidable. We will learn that increasing computational power to the level of Turing Machines necessarily introduces the threat of nontermination in programming languages.
The last module of the course covers complexity theory, which involves categorizing decidable language by their use of resources, particularly time. We will study language categories known as P (languages decidable in polynomial time) and NP (languages that can be verified by a witness in polynomial time). We conclude with NP-completeness, a notion that certain NP languages are as "hard" as any other NP language, and use reducibility-style proofs to show that certain languages are NP-complete. NP-completeness will also help us understand one of the most famous open problems in Computer Science and Mathematics: whether or not P = NP.
Along the way, we will see that there are practical applications of the concepts in this course, and you will get experience with some of these. These applications include using regular expressions in programming, designing lexers to tokenize strings, and designing parsers to form abstract syntax trees from sequences of tokens.
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:
This course will be taught in a flipped classroom style in which students are expected to study lecture materials before the in-person lecture sections. The in-person sessions will be used to review lecture concepts, answer questions, and do interactive problem solving involving the current material.
Preparation for each lecture will typically involve reading textbook sections, reviewing the lecture slides, and watching pre-recorded video segments of me going through the lecture slides. The materials for a week will typically be published a week in advance, so that you can study ahead if you want to. Consult the the course schedule for or all materials associated with a particular class day.
You will practice your understanding of the material by doing problem set problems. Many of the problem set problems are challenging and may take mutiples sessions across several days to solve. Note that you can work with a partner on problem sets; see details below.
Your understanding of the course material will be tested by solo assignments, on which you must work individually. See details below.
This number is ballpark average. The actual numbers will depend on the particular student and the particular week.
Lecture slide and videos of me working through these slides (which include exercises) are the main way in which topics will be presented in this course. The slides, exercises, and videos for a particular day can be found in the course schedule.
Since lecture slides and pre-recorded asynchronous videos are the main notes for the class, you are expected to study them carefully. You should review them before the associated synchronous class session, and may want to review parts of them again after class.
I will sometimes post some synchronous video segments of Zoom class sessions recorded when I taught this course remotely during the 2020-21 academic year. Perhaps the most important parts of the synchronous class recordings are when I discuss solutions to in-class exercises. I will sometimes post solution slides for exercises that appear in the slides.
Some notes:
The course also has readings from several textbooks. These readings should typically be done after you have watched the current day's videos. But different students learn in different ways, so do what's best for you!
Readings are tagged as:
We will be using three textbooks this semester:
See this textbook document for more details on these textbooks.
Reading and watching videos about topics can make you feel like you understand them, but the most of the actual learning occurs when you work on problems involving these topics. For this reason, you will do lots of problem solving in problem sets (psets) this semester. See the the course schedule for details.
Additionally, there will be solo assignments on which you must work individually and can receive no help from anyone else (including the instructor and tutors). Solo assignments are effectively a mini-take-home exam covering material from previous problem sets that you have already submitted. You are strongly encouraged to carefully study solutions to the previous problem set before working on the corresponding solo assignment.
Some problem sets will also include one or more extra credit problems. These are fun and challenging problems for which you can earn extra points in the course. Because they tend to be very challenging, you should not attempt these until you have finished the regular problems on a problem set.
Extra credit problems have no deadline; you can submit them at any point during the semester. You should not submit them with the problem set in which they are described. Instead, you should submit them in a separate Extra Credit Document. as described at the end of the CS235-S4 Pset Submission Instructions.
Additionaly, extra credit problems must be done individually. You cannot work with a partner on an extra credit problem.
In Spring 2024, the policy for extra credit is that up to 50 extra credit points can be added to the regular (non-solo) problem portion of your grade, and such extra credit cannot raise the regular (non-solo) problem portion of your grade beyond 100%. See the Course Grade section for more details.
Although extra credit problems are intended to be done in addition to regular problems, this policy allows you to choose to replace certain regular problems by extra credit problems. But be careful: the extra credit problems are typically more challenging than the regular ones. the regular ones.
Everyone wants COVID to be over, but it's not. There are new strains circulating, and because Wellesley brings together people from all over the world, many of whom travel to MIT and Olin an a weekly basis, it is a fertile environment for COVID (and also flus, colds, and other ailments) to spread.
Indeed, a relatively large percentage of CS317 students contracted COVID in the Fall 2023 semester, which in some cases significantly impacted their work in the course.
For the Spring 2024 semester, I have the following COVID masking policy, which is adapted from a COVID policy due to CS Prof. Peter Mawhorter:
Statistically, it’s fairly likely that at least one member of our class will have an asymptomatic case of COVID-19 this semester (so that nobody, including them, will know they have it). So it is is prudent for us to wear masks at all times in the classroom, including during student hours. See this calculator page for a model of the probabilities involved. Feel free to adjust the numbers there and see how they play out. Even at just 1 case per week across the whole campus, the probability across the entire semester that a member of the class will have an asymptomatic cases of COVID is about 10%. If the campus cases/week goes up to 5, the whole-semester probability is ~40%. I recommend you experiment with the numbers in this model.
Given vaccinations, many people are now treating COVID-19 like just another flu: something to be avoided, but not necessarily to take stringent precautions against. This attitude is sadly not supported by the data. COVID-19, unlike the flu, has a significant (likely greater than 1/1000, possibly as high as 1/10 or greater) risk of long-term, potentially-permanent complications. (This meta-analysis from January this year has an overview, although some of its percentages may be somewhat pessimistic.) In contrast, the risks of such complications from the flu are more like 1/100,000 or lower. Also, for immunocompromised people who cannot effectively be vaccinated (e.g., cancer patients undergoing chemotherapy), the risk of death from COVID-19 is still significant and is much greater than that from the flu.
There may be immunocompromised students in our class, and in principle, I’d like to create a classroom where such students could be included (despite the risks inherent in an in-person setting, which we have already decided to move to given the significant drawbacks of remote learning). Because of this, as a basic gesture of inclusivity, and as something that will help limit the number of sick days we collectively have due to other airborne illnesses, I recommend that we should all wear masks in the classroom & during student hours.
Because the campus policy does not require wearing masks in the classroom, I will not require wearing a mask in class and in-person help hours, although I strongly recommend doing so. Other professors may have different policies.
If you test positive for COVID, you must follow the campus policy for students who testing positive:
Also, students who test positive for COVID should email me ASAP so that we can make a plan for your work that makes sense for your individual situation. In particular, since many CS235 assignments involve partners, the plan must take into account your partner(s) as well as you.
I believe that collaboration fosters a healthy and enjoyable educational environment. For this reason, I encourage you to talk with other students about the course material and to form study groups.
For any pset (but not any solo assignments), you are also encouraged to form a two-person "team" with a partner and work on the pset together. 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. Use the CS235-S21-t4 Pset Partner GDoc (1) to indicate that you're looking for a pset partner and (2) to record the members of your pset partner team when you form one.
Team efforts on assignments are subject to the following ground rules:
While many of you know that I am a huge proponent of the divide/conquer/glue (DCG) approach to problem solving, this methodology is not appropriate with partner work on pset. I really do expect you to be meeting by Zoom to collaborate on all problems on a partner pset. It would be OK if, after you've collaboratively solved a problem, that one of you takes charge of "writing up" the details of the solution. What is not OK is having a group member completely solve a problem on their own, and just have their partner simply review the final solution.
The main problem with applying DCG to psets is that it reduces the learning that pair problems solving is supposed to promote. When only one partner solves a problem, the other partner isn't learning how to solve that kind of problem, and so is at a disadvantage when it comes to solving that kind of problem independently in solo problems or in their future CS work.
In this course, 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 to do any of the following:
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.
I have adapted this wording from Ben Wood
For the purposes of the collaboration policy, the word "team" will refer to an individual working on the pset alone as well as a two-person partner group working on the pset together. A team works as one to complete and submit one assignment solution.
Violating the collaboration policy as stated below is unacceptable and constitutes a violation of the Honor Code. Anyone violating these policies with be charged with an honor code violoation.
Rules of thumb for collaborating outside your team:
Team Policy
Each graded assignment follows one of two team policies:
In general, common sense applies. If you are unsure of the boundaries of acceptable collaboration or use of reference material, please ask me = Lyn. In this case, it is far better to ask permission than to seek forgiveness!
Assignments have two purposes: to help you learn, and to help both of us assess your learning (so that you can learn better, and I can help you learn better). Because assignments play such an important role in your learning, it is very important to me that you do the assignments. As a consequence, I do not deduct points for late assignments, since I find that doing so discourages completing the assignment and gaining its learning-related benefits. For this reason, I use the term dueish with regard to assignment submission dates to emphasize that "it is recommended that you submit the assignment by this date, but there is built-in flexibility to submit it later". However, there are important ground rules for late submission:
The purpose of this policy is to help you balance the requirements of this course with your mental, physical, and emotional health. I recognize that your personal life is important, and my goal with this policy is to help you find the flexibility you need. You are never expected or required to tell me any personal or private details of your life. However, I am always available to listen should you feel that sharing anything will help me support you.
A major downside of this policy is that, if you are not careful, it can lead to an accumulation of late work that is impossible to complete by the end of the semester, which may result in an incomplete grade (see the section on Incompletes below). This is why it is very important to frequently communicate with me about any delays longer than 2 days.
My job is to help each and every one of you learn, and part of that is making accommodations for any disabilities you might have. Please feel free to speak with me about concerns or suggestions about how I can make the course more accessible to you. I will never judge you or your disabilities, and I will keep the details of our conversations confidential. If you prefer, you may instead use a Anonoymous Feedback Form for this class. Though you are welcome to share any details that will help me assist in your learning, you are never required to share any private details of your life with me.
If you have a disability or condition, either long-term or temporary, and need reasonable academic adjustments in this course, it is also strongly recommended that you contact Accessibility and Disability Resources (ADR). If they know about your accommodation needs, they will send me an email describing your accommodations. It is also a good idea to meet with me early in the semester to discuss your accommodations. If you need immediate accommodations, please arrange to meet with me as soon as possible.
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 are unsure but suspect you may have an undocumented need for accommodations, you are encouraged to contact ADR They can provide assistance including screening and referral for assessments.
Problem sets and solo assignments often have a number of points that differs from 100. A graded assignment will indicated both the number of points earned and the percent of points earned on that assignment.
By default, students who work together as a pair on an assginment will earn the same score. However, if both members of a project pair agree that one member did significantly more work than another, the member doing less work may get a lower score.
As described in the CS235-S24 Pset Submission Instructions GDoc, you will submit assigments via Google Docs. The graders and I will provide feedback on your work (including numerical grades) using the Google Docs comment feature, so make sure that this feature is enabled.
The graders and I will make every effort to provide feedback on your work in a timely fashion. We will strive to have your work graded within 10 days of submission, ideally within a week.
An assignment is considered graded when I post a comment containing a numerical score for all parts at the top of the assignment.
In some cases where you have lost a significant number of points due to a misconception or some other issues, my grading comments on an assignment may indicate that you may redo a problem or a part of a problem to earn more points. If you redo the problem, please email me when you modify your Google Doc with the revised solution so that I know to regrade it. Of course, you should not consult any solutions when redoing a problem. Typically, your score on a revised problem will be capped at 80% of a problem (or problem part) grade by revising it.
Below I describe my current plan for determining course grades in Spring 2021 Term T4. If I make any change to this plan, it will always be in the favor of the student. I.e., any change will give you a grade greater than or equal to the one described in the following plan.
As a default, your course grade will be determined by the following weighting:
The score in each category will be determined as a percentage of points earned out of possible points.
Any points earned from extra credit problems (up to a maximum of 50 points) will be added to the points earned in the regular (non-solo) problems category. However, the percentage for this category may not exceed 100%. For example, suppose the total number of pset points is 680:
Based on the weighting, grades will be allocated according to the following boundaries. (Descriptions in parentheses are the definiition of grades provided in the Wellesley College Grading Policy.)
The A grade threshold is set at 95% rather than 93.33% because (1) there is no A+ grade and (2) according to the Wellesley College grading policy, "Grade A is given to students who meet with conspicuous excellence every demand which can fairly be made by the course.". The 95% threshold better reflects this standard, and is used in many CS courses.
Nevertheless, *many* students every semeseter are able to earn an A in these courses.I give these details just to tell how I grade, not to foster a preoccupation about grades. I encourage students to think of grades like Monopoly money; sure, it's nice to get lots of money in a game of Monopoly, but it doesn't have a big impact on the rest of your life. Focus on learning rather than grades.
In keeping with the Wellesley College grading policy, there is no limit on the number of A grades in the course, nor is there a goal for a particular grade to be the average grade in the course.
You may take this course Credit/Non, which means:
For students who receive a grade of C or higher in a course that they have elected to take Credit/Non-Credit, a notation of CR (credit) will appear on the transcript; for students who receive a grade lower than a C, a notation of NCR (no credit) will appear on the transcript.
During Spring 2024, the deadline to declare Credit/Non is Friday Feb 16 @ 11:59pm ET.
Some things to think about with regard to credit/non:
In the past, many students who have taken a CS course credit/non do not get a C grade and either need to retake the course or need to take an incomplete in the course and earn more points before the beginning of the next semester just to get credit (CR). For seniors, this can delay the awarding of a diploma. Because many credit/non students who do not get credit by the end of the course would be able to get a D, they tend to regret their decision to take the course credit/non. A motto to remember in this regard is "D is for Diploma".
I strongly encourage any student considering taking the course credit/non to meet with me during the first fewweeks of the semester to discuss this decision.
Due to extenuating circumstances, some of you may run out of time/energy to complete this course in the way you would like. In this case, an option is to take an incomplete. In this option, you have until the beginning of classes in Fall 2024 to submit your incomplete work.
The fact that much work for CS317 is designed to be done in teams makes taking and incomplete in CS317 more complicated than in other courses.
If you are considering taking an incomplete, you must have a conversation with Lyn about this possibility.
There is no shame in taking an incomplete, but it does mean that you are putting off work now that you will have to do later. On the other hand, you may have more time over the summer than you do during the Spring semester to devote to the course materials.
An incomplete in a course required for the CS Major is potentially problematic in the case of graduating students who are in their final semester, since it usually means the delay of their diploma.
Another aspect of taking an incomplete is that an "I" mark will appear next to your final grade indicating that it was the result of finishing an incomplete course. If you have a medical (or other major) reason for taking an incomplete, you can have a discussion with your Class Dean and request an excused incomplete, in which case the "I" mark will not appear.
The contents of this syllabus (and the associated course schedule) are my (Lyns) current best guess of how things will proceed, but they are tentative and subject to change.
I need feedback from you on what is working and not working about the course. At any point, you may email me with any ideas about how to improve the course. If you prefer to give anonymous feedback, you can fill out the anonymous feedback form below:
Wellesley College considers diversity essential to educational excellence, and we are committed to being a community in which each member thrives. The College does not allow discrimination or harassment based on race, color, sex, gender identity or aexpression, sexual orientation, ethnic or national origin or ancestry, physical or mental disability, pregnancy or any other protected status under applicable local, state or federal law.
If you or someone you know has experienced discrimination or harassment, support is available to you: