CS 383: Theory of Computation — Spring 2024

Instructor: Professor Stephen Checkoway stephen.checkoway@oberlin.edu
Lectures: Monday, Wednesday, Friday. 15:30–16:20 in King 239
Exam 1: Friday, March 1
Exam 2: Friday, April 12
Final Exam: Friday, May 17 from 09:00–11:00 in King 239
Office Hours: Tuesday 13:30–15:00 in King 231

Prerequisites

This is a theoretical course. Students are expected to be familiar with the basics of structuring and writing proofs involving sets and functions.

Grading

The final course grade is based on exams, homework, labs, and quizzes.

Letter grades will be assigned based on your weighted total points.

Any student who does not take the final exam will receive the average (arithmetic mean) score of the first two midterms as the grade for the final.

Exams

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.

Homework

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.

Course Materials

Textbooks

Resources

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.

Course Policies

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.

Attendance Policy

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!

Collaboration Policy

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.