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 Syllabus + 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 Pre-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 Immersing into Turing Machines 3.1-3.3 Async; HW1 Due
9 Monday, July 10, 2023 Advanced Regular Languages - -
Computability
10 Tuesday, July 11, 2023 Proving Decidability 4.1 HW2 Out
11 Wednesday, July 12, 2023 Practice with Decidability Review class concepts -
12 Friday, July 14, 2023 Undecidability: Pushing our Understanding of Decidabilty 4.2 -
13 Monday, July 17, 2023 Reducibility 5.1 -
14 Tuesday, July 18, 2023 Practice with Undecidability Review class concepts -
15 Wednesday, July 19, 2023 Advanced Topics: Mapping Reducibility* 5.3 Pre-HW2 Due
16 Friday, July 21, 2023 Refining Our Techniques: Additional Practice with Undecidability Review class concepts -
Complexity Theory
17 Monday, July 24, 2023 A Modern Twist: Complexity Theory 7.1-7.3 (you can skim pages 304 and onwards) HW2 Due; HW3 Out
18 Tuesday, July 25, 2023 Introduction to NP-Completeness 7.4 Pre-HW3 Due
19 Wednesday, July 26, 2023 Understanding P and NP in Practice Review class concepts -
20 Friday, July 28, 2023 More NP-Complete Problems 7.5 HW 3 Due
HW4 Out
Theory of Computation in Practice
21 Monday, July 31, 2023 Undecidability in Practice Review undecidability -
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