CS 383: Theory of Computation — Spring 2024

Prerequisites

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

Grading

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

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

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:

• TeX Live (all systems)
• MacTeX macOS 10.14 and higher
• MiKTeX Windows, macOS, and Linux

There are a number of good references on the Web, including

• The Not So Short Introduction to LaTeX, a good introduction;
• User’s Guide for the amsmath Package, documentation for mathematical environments;
• TeX Stack Exchange, a Q&A site; and
• Our Ed Discussion Forum;

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.