Section outline

    • Section 1: Automata, Languages, Grammars

      • Lecture 03/10: Introduction, Finite Automata, Deterministic Automata (DFA). (Slides 1-19)
      • Lecture 08/10: Non-deterministic Automata (NFA, NFAε), NFA and DFA Equivalence, NFA to DFA Conversion. (Slides 20-36)
      • Lecture 10/10: NFAε to DFA Conversion, DFA Minimization, State Distinguishability and Equivalence, Formal Languages and Formal Grammars. (Slides 37-62)
      • Lecture 15/10: Chomsky Hierarchy, Regular Grammars, Regular Expressions, Equivalence of Regular Expressions and Finite Automata, Product of Automata. (Slides 63-81)
      • Lecture 17/10: Pumping Lemma, Context-Free Grammars, Parse Trees. (Slides 82-98)
      • Lecture 22/10: Pushdown Automata (PDA), Context-Sensitive Grammars, Linear Bounded Automata (LBA), General Grammars, Turing Machines. (Slides 99-118)
      • Tutorial Session 24/10: NFA, DFA, NFA to DFA Conversion, Product of Automata, DFA Minimization, Regular Expressions.
      • Tutorial Session 31/10: Pumping Lemma, Context-Free Grammars.

      Section 2: Asymptotic Notation

      • Lecture 05/11: Asymptotic Notation. (Slides 1-19)

      Section 3: Graphs, Shortest Paths, Minimum Spanning Trees

      • Lecture 07/11: Shortest Paths, Dijkstra's algorithm. (Slides 1-42)
      • Lecture 12/11: Correctness of Dijkstra's algorithm, Bellman-Ford algorithm, MST, Prim, Kruskal, Boruvka algorithms. (Slides 43-87)

      Section 4: Arithmetic Algorithms

      • Lecture 14/11: GCD, Exponentation. (Slides 1-30)
      • Lecture 19/11: Fibonacci Numbers, Integer Multiplication. (Slides 31-55)

      Section 5: Computability & Complexity

      • Lecture 21/11: Computational Problems, Halting Problem, Complexity of Computational Problems, P =? NP, TSP Problem, Complexity Classes. (Slides 1-50)