CS 3530: Computational Theory

Fall 2024 Schedule

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

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

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

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

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

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

Sep 30	Turing Machines	Ch 3.1	2e
Oct 2	Turing Machine Variants	Ch 3.2	2f
Oct 3-7	Exam 1	Ch 0-2	Exam 1
Oct 4		Ch 3.2	2g

Oct 7	Definition of Algorithm	Ch 3.3
Oct 9	Definition of Algorithm	Ch 3.3	3a
Oct 11	Decidability	Ch 4.1	3b

Oct 14	The Halting Problem	Ch 4.2	3c
Oct 16		Ch 4.2	4a
Oct 18	Semester Break (no classes)

Oct 21	Semester Break (no classes)
Oct 23	Undecidable Problems	Ch 5.1	4b
Oct 25	Mapping Reducibility	Ch 5.3	4c

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

Nov 4	The Class P	Ch 7.2	5c
Nov 6	The Class NP	Ch 7.3	5d
Nov 7-11	Exam 2	Ch 3-5	Exam 2
Nov 8	The Class NP	Ch 7.3

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

Nov 18	NP-complete Problems	Ch 7.5	7c
Nov 20	Approximation Algorithms	Ch 10.1	7d
Nov 22	Approximation Algorithms	Ch 10.1	7e

Nov 25	Approximation Algorithms	Ch 10.1	7f
Nov 25-Dec 3	Exam 3	Ch 7	Exam 3
Nov 27-29	Thanksgiving Break (no classes)

Dec 2	Probabilistic Algorithms	Ch 10.2
Dec 4	Probabilistic Algorithms	Ch 10.2

Dec 9	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/08/2024