|
Fall'25: Introduction to Computability and Complexity Theory for Master Students (CS 508)
Wednesday: 15:50-19:00
Pharmacy - Room 111
Instructor: Karthik C. S. (Office hours at CoRE Building, Room 308: Monday, 17:30-18:30)
Grader: Songhua He
Homework
All homework submission must be typeset in Latex.
Homework 1 Part A is due on 09/14. Homework 1 Part B is due on 09/28.
Homework 2 Part A is due on 10/19. Homework 2 Part B is due on 11/02.
Homework 3 Part A is due on 11/16. Homework 3 Part B is due on 12/12.
You are free to discuss about the questions in the homework with other students and even take help from AI (at your own risk), but must write the solutions in your own words.
You will receive feedback on your homework only if it is submitted by the deadlines above. The homework does not contribute to your final grade.
Grading
Your grade is computed out of 1000 points.
Midterm I is 275 points, Midterm II is assigned 325 points, and the final exam is assigned 400 points.
Most of the questions in Midterm I (respectively Midterm II and final exam) will closely follow the problems in Homework I (respectively Homework II and Homework III).
Your grade will be computed solely based on the points acquired through midterms and final exam. There are no other extra credits activities for the course. No exceptions.
Your total points accumulated is Midterm I + Midterm II + Finals.
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.
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 60 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 60 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.
Tentative Topics and Schedule
| Lecture # | When | Topic |
| Lecture 1 | 09/03 | Diagonalization, Gödel's Incompleteness Theorems and Finite Automata |
| Lecture 2 | 09/10 | Regular Operators, NFA, and Regular Expressions |
| Lecture 3 | 09/17 | Equivalence of NFA, DFA, and Regular Expressions |
| Lecture 4 | 09/24 | Pumping Lemma for Regular Languages and Push Down Automata |
| | 10/01 | Midterm I based on Lectures 1-4
|
| Lecture 5 | 10/08 | Context Free Grammar, Ambiguity, and Chomsky Normal Form, Equivalence of CF Grammars and PDA |
| Lecture 6 | 10/15 | Pumping Lemma for Context Free Languages, Turing Machines and Push Down Automata with 2 stacks |
| Lecture 7 | 10/22 | Decidability, Undecidable Problems, Halting Problem and Rice's Theorem |
| Lecture 8 | 10/29 | Complexity Theory: Formalism, P, NP, NP-Completeness |
| | 11/05 | Midterm II based on Lectures 4-7 |
| Lecture 9 | 11/12 | Cook-Levin Theorem |
| Lecture 10 | 11/19 | Natural NP-Complete Problems |
| Lecture 11 | 12/03 | Hardness of Approximation |
| Lecture 12 | 12/10 | Fine-Grained Complexity |
| | 12/xx | Final Exam based on Lectures 8-12 |
|