CS 3530: Computational Theory

Fall 2025 Schedule

Day	Topic	Reading	Work Due
Aug 21	Computability, Math Foundations of Computability	Ch 0.1,0.2
Aug 23			0a

Aug 26	Proofs	Ch 0.3,0.4	0b
Aug 28	Finite Automata	Ch 1.1	0c
Aug 30			0d

Sep 02	Nondeterminism	Ch 1.2	1a
Sep 04	Regular Expressions	Ch 1.3	1b
Sep 06			1c

Sep 09	Nonregular Languages	Ch 1.4	1d
Sep 11	Nonregular Languages	Ch 1.4	1e
Sep 13			1f

Sep 16	Context Free Grammars	Ch 2.1	1g
Sep 18	Pushdown Automata	Ch 2.2	1h
Sep 20			2a

Sep 23	Non-context-free Languages	Ch 2.3	2b
Sep 25	Non-context-free Languages	Ch 2.3	2c
Sep 27			2d

Sep 30	Turing Machines	Ch 3.1	2e
Oct 02	Turing Machine Variants	Ch 3.2	2f
Oct 04			2g

Oct 05-08	Exam 1	Ch 0-2	Exam 1
Oct 07	Definition of Algorithm	Ch 3.3
Oct 09	*Fall Break (no classes)
Oct 11

Oct 14	Decidability	Ch 4.1	3a
Oct 16	The Halting Problem	Ch 4.2	3b
Oct 18			3c

Oct 21	The Halting Problem	Ch 4.2	4a
Oct 23	Undecidable Problems	Ch 5.1	4b
Oct 25			4c

Oct 28	Mapping Reducibility	Ch 5.3	4d
Oct 30	Mapping Reducibility	Ch 5.3	5a
Nov 01			5b

Nov 04	Measuring Complexity	Ch 7.1	5c
Nov 06	Measuring Complexity	Ch 7.1	5d
Nov 08

Nov 09-14	Exam 2	Ch 3-5	Exam 2
Nov 11	The Class P	Ch 7.2	7a
Nov 13	The Class NP	Ch 7.3	7b
Nov 15			7c

Nov 18	NP-completeness	Ch 7.4	7d
Nov 20	NP-complete Problems	Ch 7.5	7e
Nov 22		Ch 7.5	7f

Nov 24-28	Thanksgiving Break (no classes)

Dec 01-06	Exam 3	Ch 7	Exam 3
Dec 02	Approximation Algorithms	Ch 10.1
Dec 04	Probabilistic Algorithms	Ch 10.2
Dec 06

Dec 11	Final Exam 11:00 am - 12:50 pm	Ch 0-5,7	Final Exam

Class announcements may modify schedule from that listed above.

Last Updated 08/09/2025