Lecture Content (2024-25)

Section 1: Automata, Languages, Grammars

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

Section 2: Asymptotic Notation

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

Section 3: Graphs, Shortest Paths, Minimum Spanning Trees

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

Section 4: Arithmetic Algorithms

• Lecture 18/11: GCD, Exponentation. (Slides 1-30)
• Lecture 20/11: Fibonacci Numbers, Integer Multiplication. Short Tutorial session (Slides 31-55)

Section 5: Computability & Complexity

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

Section 6: Dynamic Programming

• Lecture 27/12: Introduction, Fibonacci Sequence, Shortest Path in DAG, Longest Increasing Subsequences, Edit Distance. Short Tutorial session (Slides 1-86)