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 |