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; context-free grammars; and Turing machines. Each model assumes an essential role in computer science. For example, finite automata are used to design and implement digital logic circuits. Context-free grammars play a central role in compilers and programming languages. Program time and space complexity are analyzed using Turing machines. Taken together, these models form an elegant theory of languages and computation.
The course will end with a brief introduction to complexity theory. We will learn about the two most important complexity classes P and NP and explore important NP-complete problems. We will learn how to do reductions to prove that a given problem is ''NP-hard'', that is, it is unlikely to be efficiently solvable.
Learning goals
At the end of the course students should be able to:- Apply concepts from Discrete Mathematics learned in cS 230/Math 255, 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.
- Explain how mathematical models of computing relate to formal languages.
- Analyze the limit of different computational models such as finite automata and Turing machines.
- Explain the concept of undecidability and list undecidable problems.
- Identify and prove that certain problems do not admit efficient solutions through reductions from well-known intractable problems.
Textbook and Course Materials
The textbook for the course is Introduction to the Theory of Computation, 3rd Edition by Michael Sipser, published by Cengage Learning.
Instructors
Instructor | Section | Office | Phone | Office Hours | |
---|---|---|---|---|---|
Cibele Freire | 1 | S160 | - | cmatosfr@wellesley.edu |
Thursday 1 pm - 3 pm Friday 10 am - 12 pm By appointment |
Shikha Singh | 2 | E114 | - | shikha.singh@wellesley.edu |
Monday 2 pm - 4 pm Thursday 10 am - 12 pm By appointment |
Tutors
Tutor | Drop-in hours | Room |
---|---|---|
Catherine Chen |
Wednesday 8 pm - 10 pm | SCI E111 |
Safia Williams |
Sunday 3:00 pm - 5:00 pm | SCI Microfocus |
Google Group
The Google Groups are CS-235-01-FA18 and CS-235-02-FA18 for Sections 1 and 2 respectively. You should make sure that you are subscribed to this group. Important course announcements will be posted to the group. You are also encouraged to post questions/comments that are of general interest to your classmates.
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 instructors during regular office hours.
- Problem sets: During the term, there will be regular homework assignments.
- Midterm examinations: The first midterm will be take-home exam and the second midterm will be two hours long and held in class. Please note these dates in your calendar
- Final examination: There will be a comprehensive final examination at the end of the semester. The final exam is self-scheduled.
Assignment Policy
- Assignment distribution, submission and grading will be handled through Gradescope. You should sign up on Gradescope using the course code 9E72N8.
- All assignments must be submitted in PDF format and must be typeset using LaTeX, LyX, Microsoft Word, or similar platforms. Scanned handwritten documents will not be accepted.
- LaTeX is the most widely used tool to professionally typeset mathematical content, proofs, conference and journal papers, etc.
- Here are some useful resources to learn LaTeX: Learn LaTeX in 30 minutes, Doing your HW in LaTex, LaTeX Cheat Sheet, A Beginner's Guide to LaTeX, The Not so Short Introduction to LaTeX2e. LaTex Stack Exchange has answers to many common LaTeX issues.
- To help start you up, LaTeX, a template for HW solutions will be provided on Overleaf, a free online LaTeX platform, similar to Share LaTeX.
- For drawing finite state diagrams or other figures, you can use any graphics generation tool of your liking. Some examples are given below.
Neat and properly scanned hand drawn figures are allowed.
- JFLAP lets you not only draw DFAs/NFAs and export their image, but you can also use it to simulate the machines on given inputs.
- The finite state machine designer by Evan Wallace is an easy way to produce simple automata.
- Other general graphic design tools such as GraphViz, Powerpoint, Keynote, Inkscape, etc.
- Assignments are due 9pm EST on the due date.
- Late Passes: You are allowed two late passes for assignments (of total 48 hours), no questions asked. You have to communicate you are using your late pass before the assignment is due, and you can either submit 1 assignment 48 hours late or 2 assignments each 24 hours late. No other way of using the 48 hours is allowed.
Collaboration Policy
You are encouraged to talk with other students about the course and to form study groups. Unless otherwise instructed, feel free to discuss problem sets with other students and exchange ideas about how to solve them.
You are encouraged to work in teams with other students. The team members can work together closely but each student must write and submit their own solution. You should mention the names of your collaborator(s) in your assignment.
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 team members to split the homework problems between them and work on them independently. Instead, the team members must actively work together on all parts of the assignment.
- Working with a partner or in a group 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.
While open exchange of ideas is encouraged, there is a thin line between collaboration and plagiarism. Please note that you must compose your own solution to each assignment. 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 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 or (4) to view assignments, exams and solutions from previous terms of CS235.
In keeping with the standards of the scientific community, you must give credit where credit is due. If you use an idea that was developed by (or jointly with) others, please reference them in your work. It is unacceptable for students to work together but not to acknowledge each other in their write-ups.
Grading
All assignments will be graded. The assignment with the lowest score will be dropped.
Your final grade will be based on a weighted average of the following components:
Homework Assignments | 30% |
Midterm Examination 1 (Take Home) | 15% |
Midterm Examination 2 (In Class) | 20% |
Final Exam (Self Scheduled) | 35% |
Special Accommodations
If you have a disability or condition, either long-term or temporary, and need reasonable academic adjustments in this course, please contact Disability Services to get a letter outlining your accommodation needs, and submit that letter to your instructor. 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 the instructor for your section as soon as possible. If you are unsure but suspect you may have an undocumented need for accommodations, you are encouraged to contact Disability Services. They can provide assistance including screening and referral for assessments.
Disability Services can be reached at disabilityservices@wellesley.edu, at 781-283-2434, by scheduling an appointment online at their website, or by visiting their office: 3rd floor of Clapp Library (rooms 316 & 315).