CS201: Theory of Computation
- Class Timings: Mondays and Wednesdays from 17:30 to 18:25; Fridays from 15:30 to 16:25.
- Location: Room M3 at NISER Bhubaneswar
References
Grading
- Assignment 0 (take-home, due in ~3 days from release) - 0%
- Weekly Revision Problems (take-home, due in ~2 days from release) - 10%
- Assignment 1 (take-home, due in ~10 days from release) - 10%
- Mid-sem (in-class) - 30%
- Assignment 2 (take-home, due in ~10 days from release) - 10%
- End-sem (in-class) - 40%
Problem Sets
Lecture Summary
Week 0: Administrative details and overview of the course, Basic Mathematical Tools.
- Lecture 0 (Aug 01, 2024): Administrative details and overview of the course.
Week 1: Finite Automata, Regular Operations, Non-Determinism, Equivalence of NFAs and DFAs, Closure Properties.
- Lecture 1 (Aug 05, 2024): Graphs, Strings and Languages (basic definitions), Definition of Finite Automata, Language recognised by a given DFA.
- Lecture 2 (Aug 07, 2024): Constructing a DFA for a given language, Regular Operations, Closure of regular languages under Union and Intersection.
- Lectures 3 and 4 (Aug 09, 2024): Definition of NFAs, Equivalence of NFAs and DFAs, Closure of regular languages under Concatenation and Star operation.
Week 2: Regular Expressions, Equivalence of Finite Automata and Regular Expressions, Pumping Lemma.
- Lecture 5 (August 12, 2024): Constructing DFAs for a given NFA, Regular Expressions, Constructing NFAs for a given Regular Expressions.
- Lecture 6 (August 14, 2024): Constructing Regular Expressions for a given NFA.
- Lectures 7 and 8 (August 16, 2024): Pumping Lemma, Using Pumping Lemma to prove Non-regularity.
Week 3: Context-Free Grammars, Push-Down Automata, Pumping Lemma.
- Lecture 9 (August 19, 2024): Context Free Grammars, Constructing a CFG for a given language, Chomsky Normal Form.
- Lecture 10 (August 21, 2024): Push Down Automata, Constructing PDAs for a given language.
- Lectures 11 and 12 (August 23, 2024): Pumping Lemma, Using Pumping Lemma to prove that a language is not Context-Free.
Weeks 4, 5, 6: Turing Machine and it's variants, Definition of an Algorithm, Decidability.
- Lectures 13 and 14 (August 30, 2024): Definition and Examples of Turing Machines, Definition of an algorithm.
- Lecture 15 (September 2, 2024): Multi-Tape Turing Machines, Non- Deterministic Turing Machines, Enumerators.
- Lecture 16 (September 4, 2024): Encoding Objects as Strings, Simulating other computational models using a Turing Machine.
- Lecture 17 (September 6, 2024): Examples of Decidable Languages.
- Lecture 18 (September 9, 2024): Undecidability.
Week 7: No classes, since I will be away for Dagstuhl.
Week 8: Recap and Doubt Clearing for Mid-sem.
Week 9: No classes, since I will be away for IndiCS.
Week 10: Reducibility, Time Complexity.
- Lecture 19 (October 21, 2024): Examples of Undecidable Languages.
- Lecture 20 (October 23, 2024): Mapping Reducibility, Rice's Theorem.
- Lecture 21 (October 25, 2024): Introduction to Complexity Theory, Definition of Time Complexity.
Week 11: The classes P and NP, NP completeness.
- Lecture 22 (October 28, 2024): The class P.
- Lecture 23 (October 30, 2024): Every context-free language is in P, Definition of NP.
- Lecture 24 and 25 (November 1, 2024): Revisiting the definition of NP, Defining CIRCUIT-SAT, Defining NP-Completeness.
Week 12: NP Completeness of SAT, CIRCUIT-SAT.
- Lecture 26 (November 4, 2024): NP-Completeness of CIRCUIT-SAT.
- Lecture 27 (November 6, 2024): Defining 3-SAT, NP-Completeness of 3-SAT.
Week 13: Alternate Definition of NP via Non-Deterministic TMs, More NP Complete Problems.
- Lecture 28 (November 13, 2024): Alternate Definition of NP via Non-Deterministic TMs, Proof of "NP contained in EXP".
- Lectures 29 and 30 (November 15, 2024): NP-Completeness of VERTEX-COVER and SUBSET-SUM
Week 14: Recap and Doubt Clearing for End-sem.