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):
- Lecture 17 (September 6, 2024):
- Lecture 18 (September 9, 2024):
Week 7: No classes, since I will be away.
Week 8: Recap and Doubt Clearing.
Week 9: Reducibility, Time Complexity.
Week 10: The classes P and NP, NP completeness.
Week 11: Space Complexity, The class PSPACE.
Week 12: The classes L and NL.
Week 13: Hierarchy Theorems, Circuits.
Week 14: Random and Quantum models of Computation..