CS 3530: Computational Theory

Fall 2018 Schedule

Day Topic Reading Work Due
W01
Aug 21 Automata, Computability, and Complexity 0.1, 0.2 None
Aug 23 Mathematical Notions 0.2 0a
W02
Aug 28 Definitions, Theorems, and Proofs 0.3, 0.4 0b
Aug 30 Typs of Proof 0.3, 0.4 0c
W03
H Sep 3 Labor Day (no classes)
Sep 4 Finite Automata 1.1, 1.2 0d
Sep 6 Nondeterminism 1.1, 1.2 1a
W04
Sep 11 Regular Expressions 1.2, 1.3 1b
Sep 13 Nonregular Languages 1.3, 1.4 1c
W05
Sep 18 Regular Languages 1.4 2a 2b
Sep 20 Context-free Grammars 2.1, 2.2 3a
W06
Sep 25 Pushdown Automata 2.1, 2.2 3b 4a
Sep 27 Non-context-free Languages 2.2, 2.3 4b
W07
Oct 2 Context-Free Languages 2.3 4c 5a
Oct 4 Midterm Review 5b
W08
Oct 9 Written Examination I Written Examination I
H Oct 11-12 Fall Break (no classes)
W09
Oct 16 Turing Machines 3.1, 3.2 None
Oct 18 Algorithms 3.3 6a
W10
Oct 23 Decidable Languages 4.1 6b
Oct 25 The Halting Problem 4.2 6c
W11
Oct 30 Undecidable Problems 5.1 6d
Nov 1 Undecidable Problems 5.1 7a
W12
Nov 6 Mapping Reducibility 5.3 7b
Nov 8 Review 7c
W13
Nov 13 Written Examination II Written Examination II
Nov 15 Measuring Complexity 7.1
Nov 15 The Class P 7.2
W14
Nov 20 The Class NP 7.3 8a
H Nov 21-23 Thanksgiving Break (no classes)
W15
Nov 27 NP-Completeness 7.4 8b
Nov 29 Additional NP-complete Problems 7.5 8c
W16
Dec 4 Space Complexity 8 8d
Dec 6 Final Review 8e
W17
Dec 10-14 Final Exams
R Dec 13 Final Exam 1:0 pm - 2:50 pm Final Exam

Class announcements may modify schedule from that listed above.

Last Updated 11/24/2018