DEPARTMENT OF COMPUTING

Course Home | Syllabus | Assignments | Schedule | Downloads | [print]

CS 3530: Computational Theory

Fall 2022 Schedule

Day Topic Reading Work Due
Aug 23 Computability, Math Foundations of Computability Ch 0.1,0.2
Aug 25 Math Foundations of Computability, Proofs Ch 0.2,0.3 0a
Aug 27 0b
Aug 30 Proofs Ch 0.3,0.4 0c
Sep 1 Finite Automata Ch 1.1 0d
Sep 5 Labor Day (no classes)
Sep 6 Nondeterminism Ch 1.2 1a
Sep 8 Regular Expressions Ch 1.3 1b
Sep 10 1c
Sep 13 Nonregular Languages Ch 1.4 1d
Sep 15 Nonregular Languages Ch 1.4 1e
Sep 17 1f
Sep 20 Context Free Grammars Ch 2.1 1g
Sep 22 Pushdown Automata Ch 2.2 1h
Sep 24 2a
Sep 27 Non-context-free Languages Ch 2.3 2b
Sep 29 Non-context-free Languages Ch 2.3 2c
Oct 1 2d
Oct 4 Turing Machines Ch 3.1 2e
Oct 6 Turing Machine Variants Ch 3.2 2f
Oct 7-10 Exam 1 Ch 0-2 Exam 1
Oct 8 2g
Oct 11 Definition of Algorithm Ch 3.3 3a
Oct 13-14 Semester Break (no classes)
Oct 15
Oct 18 Decidability Ch 4.1 3b
Oct 20 The Halting Problem Ch 4.2 3c
Oct 22 4a
Oct 25 Undecidable Problems Ch 5.1 4b
Oct 27 Mapping Reducibility Ch 5.3 4c
Oct 29 4d
Nov 1 Mapping Reducibility Ch 5.3 5a
Nov 3 Measuring Complexity Ch 7.1 5b
Nov 5 5c
Nov 8 The Class P Ch 7.2 5d
Nov 9-14 Exam 2 Ch 3-5 Exam 2
Nov 10 The Class NP Ch 7.3
Nov 11 Code Camp
Nov 12 Code Camp
Nov 15 NP-completeness Ch 7.4 7a
Nov 17 NP-complete Problems Ch 7.5 7b
Nov 19 7c
Nov 22 NP-complete Problems Ch 7.5 7d
Nov 23-25 Thanksgiving Break (no classes)
Nov 26
Nov 29 Approximation Algorithms Ch 10.1 7e
Dec 1-5 Exam 3 Ch 7 Exam 3
Dec 1 Approximation Algorithms Ch 10.1 7f
Dec 3
Dec 6 Probabilistic Algorithms Ch 10.2
Dec 8 Probabilistic Algorithms Ch 10.2
Dec 10
Dec 12-16 Final Exams
Dec 15 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/05/2022