Spring'25: Undergraduate Computability and Complexity Theory (CS 452)

Monday: 15:50-17:10
Wednesday: 15:50-17:10
Beck Hall - Room 253

Instructor: Karthik C. S. (Office hours at Core Building, Room 308: Monday, 14:00-15:00)

Recitations: Mursalin Habib (Beck Hall - Room 253 on Wednesdays from 17:40-18:35).

Homework

All homework must be typeset in Latex. Otherwise the homework will not be evaluated.
Every homework has 1 point for presentation. If your homework is very hard to read this point will be deducted.

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 400 points from homework. Midterm I is 150 points, Midterm II is assigned 200 points, and the final exam is assigned 250 points.

Your grade will be computed solely based on the sum of all the points acquired through homework, midterms, and final exam. There are no other extra credits activities for the course. No exceptions. There is no curve: you must earn a minimum of 90% of the total points for an A (900 points), 85% for a B+ (850 points), 80% for a B (800 points), 75% for a C+ (750 points), 70% for a C (700 points),
and 60% for a D (600 points). You will fail the course if you earn less than 60% points (600 points).
The cutoffs are strictly followed for each letter grade. A computed grade of 74.99% is a C not a C+. There are no other extra credits activities for the course. No exceptions.
There will be 3 homeworks each assigned 150 points that you may accumulate.
For all the 3 exams the following scaling policy will be applied. If the total points that can be accumulated through a specific exam is X and if the 70 percentile score obtained on the exam is x which is in the interval [1,0.9X],
then everyone’s score will be scaled by a multiplicative factor of (9X)/(10x). For example, if the 70 percentile score obtained on the exam across all students is 100 out of 150 points, then every single student’s score will be multiplied by a factor of 1.35.
Therefore, if you obtained 80 points, then it will be scaled up, and your new score will be 108 points (because 80 × 1.35 = 108). These bonus points are given to counter if the exam is too hard.

Topics and schedule

Lecture #	When	Topic
Lecture 1	01/22	Cantor's Diagonalization Argument
Lecture 2	01/27	Gödel's Incompleteness Theorems
Lecture 3	01/29	Finite Automata and Regular Languages
Lecture 4	02/03	Regular Operators and NFA
Lecture 5	02/05	Equivalence of NFA and DFA
Lecture 6	02/10	Regular Expressions
Lecture 7	02/12	Pumping Lemma for Regular Languages
Lecture 8	02/17	Summary of Topics I
	02/19	Midterm I Parts 1 and 2
Lecture 9	02/24	Context Free Grammar
Lecture 10	02/26	Ambiguity and Chomsky Normal Form
Lecture 11	03/03	Push Down Automata
Lecture 12	03/05	Equivalence of CF Grammars and PDA
Lecture 13	03/10	Pumping Lemma for Context Free Languages
Lecture 14	03/12	Turing Machines and Decidability
Lecture 15	03/24	Undecidable Problems
Lecture 16	03/26	Halting Problem and Rice's Theorem
Lecture 17	03/31	Summary of Topics II
	04/02	Midterm II Parts 1 and 2
Lecture 18	04/07	Complexity Theory: Formalism
Lecture 19	04/09	P, NP, NP-Completeness
Lecture 20	04/14	Cook-Levin Theorem I
Lecture 21	04/16	Cook-Levin Theorem II
Lecture 22	04/21	Natural NP-Complete Problems I
Lecture 23	04/23	Natural NP-Complete Problems II
Lecture 24	04/28	Fine-Grained Complexity I
Lecture 25	04/30	Fine-Grained Complexity II
Lecture 26	05/05	Summary of Topics III
	05/*	Final Exam