COMP361 - Theory of Computation (Spring 2025)
Welcome to the COMP361 (Theory of Computation) Course Page. For course policies, please check the syllabus.
Resources
Textbook
We will be using Sipser’s Introduction to the Theory of Computation, 3rd edition.
Be aware of known typos in the book as you read.
Office Hours
MON 4:30-6pm
THU 4:30-5:30pm
FRI 4:30-5:30pm
OLRI 229
If you cannot make these times, please feel free to set up an appointment via email.
Schedule
The schedule below will be updated to keep track of all released course materials. Keep in mind that I may shift planned topics to adjust pace as necessary.
| Week | Date | Topic | Reading | Materials |
|---|---|---|---|---|
| 0 | TH 1/23 | Course Overview | NA | Beginning-of-Semester Survey |
| 1 | TU 1/28 | Mathematical Foundations | Sipser 0 | Proof Guide |
| 1 | TH 1/30 | DFAs | Sipser 1.1 | Induction for DFAs |
| 2 | TU 2/4 | Proving Regularity | ||
| 2 | TH 2/6 | Closure Properties of Regular Languages | ||
| 3 | TU 2/11 | NFAs | Sipser 1.2 | |
| 3 | TH 2/13 | Closure Properties of Regular Languages 2 | ||
| 4 | TU 2/18 | RegExp | Sipser 1.3 | |
| 4 | TH 2/20 | Proving Non-Regularity (Pumping Lemma) | Sipser 1.4 | Puzzle Problem |
| 5 | TU 2/25 | Pumping Lemma 2 | ||
| 5 | TH 2/27 | No Class: Capstones! | ||
| 6 | TU 3/4 | CFGs | Sipser 2.1 | |
| 6 | TH 3/6 | PDAs and Pumping lemma for CFLs | Sipser 2.2–2.3 | |
| 7 | TU 3/11 | CFGs/PDA Equivalence | Sipser 2.2 | |
| 7 | TH 3/13 | Exam 1 | ||
| 8 | - | Spring Break | ||
| 9 | TU 3/25 | Turing Machines 1 | Sipser 3.1 | |
| 9 | TH 3/27 | Turing Machines 2 | Sipser 3.2 | |
| 10 | TU 4/1 | Algorithms & Church-Turing Thesis | Sipser 3.3 | |
| 10 | TH 4/3 | Decidability | Sipser 4.1 | |
| 11 | TU 4/8 | Undecidability & Halting Problem | Sipser 4.2 | |
| 11 | TH 4/10 | Reductions to Undecidability | Sipser 5.1/5.3 | |
| 12 | TU 4/15 | Exam 2 | ||
| 12 | TH 4/17 | Complexity Theory | Sipser 7.1 | |
| 13 | TU 4/22 | P vs. NP | Sipser 7.2–7.3 | |
| 13 | TH 4/24 | NP-Completeness & Cook-Levin | Sipser 7.4 | |
| 14 | TU 4/29 | Reduction Practice | ||
| 14 | TH 5/1 | Special Topic: Circuit Complexity | Sipser 9.3 | |
| FINALS | SA 5/10 10:30-12:30pm | FINAL EXAM |
Homeworks
All homework assignments will be posted here, but are to be submitted on the Moodle Course page.
Note that while you are expected to complete all homework problems, some assignments may only have a subset of problems that will be graded for accuracy. These problems will be indicated in the instructions, if in a PDF, or by bolding if the problems are listed here.
Homework 0
Sipser Problems: - 0.4 ($AxB$), - 0.5 (size of the power set of $A$), - 0.11 ($C(n) = \sum^n i^3$), - 0.12 (All horses are the same color), - 0.13 (Every graph w/ $\geq2$ nodes has 2 nodes with equal degree), - 0.14 (Ramsey’s Thm.)
Bolded questions will be graded for correctness and clarity. I recommend struggling with 0.14 for at least a day or two before consulting the provided solution.
Out: Jan 23rd. Due: 11:59pm, Jan 31st. Template: LaTeX
NOTES: This assignment will hopefully mostly review of material from (primarily) Discrete Mathematics, as well as some moderate extensions of things you should already know to fit the context of this course. Be aware that things you do already know might look a bit unfamiliar at first! This is an opportunity to familiarize yourself with my style of presentation without having to worry about being unfamiliar with the material!
WARNING: Apparently problem numbers are shuffled between editions. A short description has been added so you solve the right problems.
Homework 1
Out: Feb 3rd.
Due: 11:59pm, Feb 9th.
Instructions
Template: LaTeX
NOTES: Problem 2 is a good example of the kind of presentation/support I’d provide for a problem that requires you to prove a DFA accepts a particular language. 2b is a good example of a place where using induction to do so may be helpful.
Homework 2
OUT: Feb 10th.
DUE: 11:59pm, Feb 17th.
Instructions
Template: LaTeX
Notes: Be aware that while 2b is not graded, a reasonable solution to 2b is necessary to get full points on 2c, so it is ungraded but effectively mandatory.
Homework 3
OUT: Feb 19th
DUE: 11:59pm Feb 26th
Instructions
Template: LaTeX
Homework 4
OUT:: Feb 27th
DUE: 11:59pm March 10th
Instructions
Template: LaTeX
Homework 5
OUT:: April 1st
DUE: 11:59pm April 8th
Instructions
Template: LaTeX
Homework 6
This assignment contains no graded problems
OUT:: April 10th
Instructions
Template: LaTeX