Fall'23: Undergraduate Computability and Complexity Theory (CS 452)
Wednesday: 15:50-17:00
Science & Engineering Resource Center - Room 203
Instructor: Karthik C. S. (Office hours at Core 308: Monday, 14:30-15:30)
Recitations: Mursalin Habib (Science & Engineering Resource Center - Room 207 on Wednesday: 19:45-20:40).
Scribing
Please use this latex template for the scribes.
You may scribe in groups of size 1 or 2. At most two groups can scribe each of the lectures.
The scribes of the Monday lecture are due by Friday night of the same week. The scribes of the Wednesday lecture are due by Sunday night of the same week.
A perfect scribing of the lecture with all missing details filled in will be given 200 points. A scribe which merely copies what is written on the board and does not add any additional context or details will be given at most 50 points.
Grading
Your grade is computed out of 1000 points (you may accumulate at most 1000 points; if you obtain more than 1000 points then it will be capped to exactly 1000 points).
You can accumulate at most 200 points from scribing lecture notes. Midterm I is 250 points, Midterm II is assigned 300 points, and the final exam is assigned 350 points.
Your grade will be computed solely based on the sum of all the points acquired through scribing, midterms, and final exam. There are no other extra credits activities for the course. No exceptions.
Topics and schedule
| Lecture # | When | Topic | Scriber(s) |
| Lecture 1 | 09/06 | Cantor's Diagonalization Argument | |
| Lecture 2 | 09/11 | Gödel's Incompleteness Theorems | |
| Lecture 3 | 09/13 | Finite Automata and Regular Languages | |
| Lecture 4 | 09/18 | Regular Operators and NFA | |
| Lecture 5 | 09/20 | Equivalence of NFA and DFA | |
| Lecture 6 | 09/25 | Regular Expressions | |
| Lecture 7 | 09/27 | Pumping Lemma for Regular Languages | |
| Lecture 8 | 09/02 | Summary of Topics I | |
| 10/04 | Midterm I Parts 1 and 2 | ||
| Lecture 9 | 10/09 | Context Free Grammar | |
| Lecture 10 | 10/11 | Ambiguity and Chomsky Normal Form | |
| Lecture 11 | 10/16 | Push Down Automata | |
| Lecture 12 | 10/18 | Equivalence of CF Grammars and PDA | |
| Lecture 13 | 10/23 | Pumping Lemma for Context Free Languages | |
| Lecture 14 | 10/25 | Turing Machines and Decidability | |
| Lecture 15 | 10/30 | Undecidable Problems | |
| Lecture 16 | 11/01 | Halting Problem and Rice's Theorem | |
| Lecture 17 | 11/06 | Summary of Topics II | |
| Lecture 18 | 11/08 | Complexity Theory: Formalism | |
| Lecture 19 | 11/13 | P, NP, NP-Completeness | |
| Lecture 20 | 11/15 | Cook-Levin Theorem I | |
| 11/15 | Midterm II Part 1 | ||
| 11/20 | Midterm II Part 2 | ||
| 11/22 | NO LECTURE | ||
| Lecture 21 | 11/27 | Cook-Levin Theorem II | |
| Lecture 22 | 11/29 | Natural NP-Complete Problems I | |
| Lecture 23 | 12/04 | Natural NP-Complete Problems II | |
| Lecture 24 | 12/06 | Fine-Grained Complexity I | |
| Lecture 25 | 12/11 | Fine-Grained Complexity II | |
| Lecture 26 | 12/13 | Summary of Topics III | |
| 12/18 | Final Exam |