CS 3530: Computational Theory

Fall 2023 Schedule

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

Aug 28	Proofs	Ch 0.3,0.4	0c
Aug 30	Finite Automata	Ch 1.1	0d
Sep 1			1a

Sep 4	Labor Day (no classes)
Sep 6	Nondeterminism	Ch 1.2	1b
Sep 8	Regular Expressions	Ch 1.3	1c

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

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

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

Oct 2	Turing Machines	Ch 3.1	2e
Oct 4	Turing Machine Variants	Ch 3.2	2f
Oct 5-9	Exam 1	Ch 0-2	Exam 1
Oct 6		Ch 3.2	2g

Oct 9	Definition of Algorithm	Ch 3.3
Oct 11	Definition of Algorithm	Ch 3.3
Oct 12-13	Semester Break (no classes)

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

Oct 23	Undecidable Problems	Ch 5.1	4a
Oct 25	Mapping Reducibility	Ch 5.3	4b
Oct 27	Mapping Reducibility	Ch 5.3	4c

Oct 30	Mapping Reducibility	Ch 5.3	4d
Nov 1	Measuring Complexity	Ch 7.1	5a
Nov 3	Measuring Complexity	Ch 7.1	5b

Nov 6	The Class P	Ch 7.2	5c
Nov 8	The Class NP	Ch 7.3	5d
Nov 9-13	Exam 2	Ch 3-5	Exam 2
Nov 10	The Class NP	Ch 7.3

Nov 13	NP-completeness	Ch 7.4
Nov 15	NP-complete Problems	Ch 7.5	7a
Nov 17	NP-complete Problems	Ch 7.5	7b

Nov 20	NP-complete Problems	Ch 7.5	7c
Nov 22-24	Thanksgiving Break (no classes)

Nov 27	Approximation Algorithms	Ch 10.1	7d
Nov 29	Approximation Algorithms	Ch 10.1	7e
Nov 30-Dec 4	Exam 3	Ch 7	Exam 3
Dec 1	Approximation Algorithms	Ch 10.1	7f

Dec 4	Probabilistic Algorithms	Ch 10.2
Dec 6	Probabilistic Algorithms	Ch 10.2
Dec 8	Probabilistic Algorithms	Ch 10.2

Dec 11-15	Final Exams
Dec 11	Final Exam 09:00 am - 10:50 am	Ch 0-5,7	Final Exam

Class announcements may modify schedule from that listed above.

Last Updated 08/16/2023