Prerona Chatterjee

                    Contact Teaching Talks Research Home

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.

Week 8: Recap and Doubt Clearing for Mid-sem.

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