CSC 282 | Summer 2023

Computer Models and Limitations - Summer 2023
Tentative Schedule
This schedule is subject to change based on the class's pace. Any change will be announced in class and will be reflected here.
NOTE:  There are two recommended ways of doing the readings. Ideally, you would skim the suggested readings prior to lecture (to not feel lost during lecture) 
and then you would do a closer reading when reviewing the material. The next best approach is to do the suggested readings after each lecture.
Regardless of the approach you choose, ask a lot of questions in class!
# Date Topic Suggested Readings Notes
Regular and Context-Free Languages
1 Monday, June 26, 2023 Mathematical Rigor and Proving Things 0.1-0.4 -
2 Tuesday, June 27, 2023 Regular Languages 1.1-1.3 HW1 Out
3 Wednesday, June 28, 2023 Nonregular Languages 1.4 -
4 Friday, June 30, 2023 Context-Free Languages 2.1-2.2 -
5 Monday, July 3, 2023 Non-CF Languages 2.3 Minor HW1 Due
6 Tuesday, July 4, 2023 University Holiday: No class - -
7 Wednesday, July 5, 2023 Practice with Pumping Lemmas Review class concepts Async
8 Friday, July 7, 2023 Advanced Regular Languages* - Async; Major HW1 Due
9 Monday, July 10, 2023 Practice with  Advanced Regular Languages* Review class concepts -
Computability
10 Tuesday, July 11, 2023 Immersing into Turing Machines 3.1-3.3 HW2 Out
11 Wednesday, July 12, 2023 Proving Decidability 4.1-4.2 -
12 Friday, July 14, 2023 Practice with Decidability Review class concepts -
13 Monday, July 17, 2023 Undecidability: Pushing our Understanding of Decidabilty 5.1, 5.3 Minor HW2 Due
14 Tuesday, July 18, 2023 Practice with Undecidability Review class concepts -
15 Wednesday, July 19, 2023 Refining Our Techniques: Undecidability in Practice 5.3 -
16 Friday, July 21, 2023 Advanced Topics in Computability* - Major HW 2 Due
Complexity Theory
17 Monday, July 24, 2023 A Modern Twist: Complexity Theory 7.1–7.5 (you can skim pages 304 and onwards) HW3 Out
18 Tuesday, July 25, 2023 Understanding P and NP in Practice Review class concepts Minor HW3 Due
19 Wednesday, July 26, 2023 Exploring Properties of SAT: Complexity of Variants, Self-Reducibility, etc. - -
20 Friday, July 28, 2023 Deterministic Space and Time Hierarchy 9.1 Major HW 3 Due
HW4 Out
Final Phase
21 Monday, July 31, 2023 The RAM Model of Computation - -
22 Tuesday, August 1, 2023 Presentations - Ask lots of questions!
23 Wednesday, August 2, 2023 Presentations - Ask lots of questions!
24 Friday, August 4, 2023 Buffer - HW 4 Due
*: If time permits