Fall'23: Undergraduate Computability and Complexity Theory (CS 452)

Monday: 15:50-17:00
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).


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.


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
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