This page contains link to the lectures I give throughout the semester. Clicking the title of the week’s lecture will go to the Github directory () containing all the lecture notes, embedded in the user’s browser, as will the bottom right link. The bottom right link will take you to the youtube lecture videos, where you can find the appropriate lecture for the week based on the topic.

  • Week 1
    tl;dr: Introduction to the course, DFAs, Regular Languages, Regular operations, Closure under union   
  • Week 2
    tl;dr: NFAs, Equivalence of DFAs and NFAs, Closure properties, regular expressions, Equivalence of Regular expressions and DFAs.   
  • Week 3
    tl;dr: Pumping Lemma for regular languages, Myhill-Nerode Theorem, Context-free grammars   
  • Week 4
    tl;dr: Chomsky Normal Form, CYK Algorithm, Closure properties of CFLs, Pushdown Automata   
  • Week 5
    tl;dr: Equivalence of PDAs and CFGs, Pumping Lemma for CFLs, Introduction to Turing machines   
  • Week 6
    tl;dr: Decidable (recursive) languages, Turing-Recognizable (recursively enumerable) languages, Multi-tape TMs, NTMs, Church Turing thesis   
  • Week 7
    tl;dr: Decidable languages from regular and context-free languages, Countable and uncountable sets, Halting Problem and undecidability.   
  • Week 8
    tl;dr: Reductions. Decidable and undecidable languages using reductions. Rice’s theorem. Computation Histories.   
  • Week 9
    tl;dr: Post Correspondence Problem (PCP) is undecidable, Introduction to Complexity Theory. Asymptotic notation, Classes P and NP.   
  • Week 10
    tl;dr: Verifier model for NP, Polynomial Time reductions, NP Completeness, Cook-Levin Theorem   
  • Week 11
    tl;dr: NP Complete problems like Vertex Cover, Hamiltonian Path, Subset Sum, ILP   
  • Week 12
    tl;dr: Space Complexity, Relation with time bounded complexity classes, introduction to classes like L, NL, PSPACE and overview of results in space complexity