CS 383: Theory of Computation — Fall 2023
Instructor: Professor Stephen Checkoway firstname.lastname@example.org
Lectures: Monday, Wednesday, Friday. 13:30–14:20 in King 243
Exam 1: Friday, September 29
Exam 2: Friday, November 10
Final Exam: Sunday, December 17 from 19:00–21:00
Office Hours: Thursday 13:30–15:30 in King 231
- CSCI 280: Algorithms
- MATH 220: Discrete Mathematics
This is a theoretical course. Students are expected to be familiar with the basics of structuring and writing proofs involving sets and functions.
The final course grade is based on exams, homework, labs, and quizzes.
- Homework (60%)
- Midterm exams (20%)
- Final exam (20%)
Letter grades will be assigned based on your weighted total points.
- 85%–100% – A
- 70%–84% – B
- 60%–69% – C
- 50%–59% – D
- 0%–49% – F
Any student who does not take the final exam will receive an F.
There are two midterm exams and one final exam at the dates and times listed at the top of this page.
Exams are open book and notes.
There will be weekly homework assignments during the semester. Per the collaboration policy, you are free to work with other students on the homeworks, but you must write up your own solutions.
All of your written solutions must be typeset. You are strongly encouraged to use the LaTeX typesetting system to write up your solutions, but you are free to use other tools (such as Microsoft Word). See the resources below for more information on LaTeX.
In addition to written solutions, you will also produce DFAs, NFAs, PDAs, and Turing machines using JFLAP.
- Required. Michael Sipser. Introduction to the Theory of Computation, 3rd edition. This book is very expensive right now for some reason. I strongly recommend getting an international edition or a used version. The 2nd edition of the book is cheeper and all of the material we’ll be using is in the second edition.
- Optional. Richard Hammack Book of Proof (available online).
JFLAP is software that you will use for building the machines we will be discussing in class.
LaTeX is a typesetting system which you are encouraged to use to write up solutions to the homework. Here is an example proof written in LaTeX and here is the corresponding source code.
LaTeX distributions are available for macOS, *NIX, and Windows:
There are a number of good references on the Web, including
There are many tools that can assist in writing LaTeX, including a variety of specialized editors such as Texmaker and TeXShop. There are also add-ons for editors like Emacs (AUCTeX is the best of those) and Vim.
Writing your solutions in LaTeX will take time at first, but as you become more familiar with it, you’ll find that it’s an invaluable tool. I strongly recommend you learn to use it well.
Generative AI/Large Language Model Policy
You are not allowed to use Generative AI (for example, but not limited to, ChatGPT and Google Bard) to solve problems in this class.
You are not required to attend; however, research indicates that students who attend class are more likely to be successful. You are strongly encouraged to attend every class. If you are unable to attend class, you should consider asking a classmate to take notes for you.
Missed or Late Work Policy
Homework is due by 23:59 on the day specified on each homework page. You have 3 late days that you can use throughout the semester. If you run out of late days, homeworks turned in late will receive a score of 0. You are responsible for keeping track of your late days. There will be no exceptions to this policy without prior approval from Prof. Checkoway.
College policy prohibits accepting any work after the scheduled final exam time for a course without an incomplete.
Electronic Communication Policy
All electronic communication with course staff should take place on Ed unless emails are specifically requested by the staff. Course staff may, from time to time, respond to emails, but a response to one email does not guarantee a response to a second. Use Ed!
You are allowed, and encouraged, to work with other students on all homeworks; however, you must write up your solutions yourself.
Exams are to be completed individually.
Academic Integrity Policy
You must adhere to the Oberlin College Academic Integrity Policy. Please familiarize yourself with the Honor Code.
Religious Holiday Observance Policy
Students wishing to be excused from class in order to observe religious holidays must follow the Oberlin College Religious Holiday Observance Policy.