Theory of Computing

Computer Science 461 - Fall 2023

Basic Info


Tentative Schedule

The schedule below is tentative, and may be subject to change. Changes will be announced in class, and you are responsible for knowing about any changes even if you miss the class when they are announced.


Week Topic Notes Homework
1 Boolean circuits Week 01 HW1
2 Finite automata Week 02 HW2
3 Nondeterministic finite automata Week 03 HW3
4 Regular expressions & languages Week 04 HW4
5 Pumping lemma, Midterm 1 Week 05
6 Context free languages Week 06 HW5
7 Pushdown automata Week 07 HW6
8 Pumping lemma 2 Week 08 HW7
9 Turing machines Week 09 HW8
10 Decidability, Midterm 2 Week 10
11 Enumerability Week 11 HW9
12 Complexity theory Week 12 HW10
13 Nodeterministic algorithms Week 13 HW11
14 NP-completeness, Midterm 3 Week 14

Attendance Policy

Attendance in this class is required. Repeated absences may result in a forced withdrawal from the course. You are responsible for any material you miss due to absence. Please let me know ahead of time if you know that you will not be able to attend class.

Grading Policy

The term grade will be based on the following factors.

Component     Proportion    
Homework 40%
Midterms 30%
Final Exam 30%


There will be homework problems assigned every week. These will typically be collected on Mondays. I will drop the lowest homework grade. Late homework will only receive a fraction of the full possible grade.


There will be three in-class midterm exams and a cumulative final. These exams will be announced in advance, and you will know exactly what concepts will be covered on each exam.

Office Hours

My office hours are shown on my weekly schedule. I am also available by appointment. If you can’t stop by during my regular office hours, just ask me after class or by e-mail, and I’ll be happy to make an appointment that works for both of us.

Special Accommodations

Students who think they may need accommodations in this course because of the impact of a disability are encouraged to meet with me privately at the beginning of the semester. Students also should contact Melissa Wood, Title IX/504 Coordinator (, 434-223-6061) to verify their eligibility for reasonable accommodations. Early contact will help to avoid unnecessary inconvenience and delays.