Instructor: Nikhil Balaji (nbalaji)
TAs: Prashant Agrawal (csz188011), Nikhil Ayyadevara (cs1170330), Indrajit Banerjee (csy207569)
Vijay Bhardwaj (mcs202476), Shivansh Juyal (mcs202471), Bikram Mondal (mcs212127)
Slot: H (Mon, Wed - 11:00 - 12:00, Thu: 12:00 - 13:00)
COL202 or MTL180 or an equivalent course. Specifically, the following topics:
Proof techniques - construction, contradiction, induction, counting techniques.
Sets and set operations, relations
Functions -- injections, surjections, and bijections; cardinality
Countability and uncountability, diagonalization
Equivalence relations, partial orders
If you haven't done either but would like to attend the course, email me.
Finite state machines and finite automata, nondeterminism, regular languages and their properties, regular expressions, pumping lemma for regular languages, Myhill-Nerode theorem, minimal automata
Grammars, ambiguity, context-free languages and their properties, pumping lemma for context-free languages, pushdown automata
Turing machines, deciders, multi-tape and non-deterministic Turing machines, Turing-recognizability and decidability, enumerators
Undecidability and un-recognizability, mapping reductions, Rice's theorem, connections to problems in mathematical logic
Other topics (Streaming algorithms, Kolmogorov complexity, Weighted automata, etc..)
Introduction to the Theory of Computation by Michael Sipser
Elements of the Theory of Computation by Harry Lewis and Christos Papadimitriou
Automata and Computability by Dexter Kozen
Homeworks - 30%
Quizzes - 30%
Major exam - 40%
30% marks necessary for a passing grade.
Microsoft Teams for live lectures (check the 'Lectures' channel)
Gradescope for exams
Jan 3: Intro to the course, logistics, motivation. Reading: Sipser Chapter 0
Jan 5, 6: Recap, languages, decision problems, finite state machines, DFA examples, formal definitions. Reading: Sipser section 1.1, Kozen lectures 2,3.
Jan 10,12,13: NFA examples, formal definition, closure properties of regular languages, Subset construction, epsilon-NFAs. Reading: Sipser section 1.2.
Jan 17,19,20: Exponential lower bound for subset construction, Regular expressions, Equivalence with DFA, NFA, non-regular languages.Reading: Sipser section 1.3, Kozen lectures 7-9.
Jan 24, 27, 29: Non-regular languages, Pumping lemma and its applications, Myhill-Nerode relations. Reading: Kozen lectures 11-12, 15. Sipser section 1.4.
Jan 31, Feb 2, 3: Myhill-Nerode theorem, DFA minimization, 2DFAs intro. Reading: Kozen lectures 13, 14, 16, 17.
Feb 7, 9, 10: 2DFAs and regular sets, streaming algorithms, discussion of other related models, Pushdown Automata. Reading: Kozen lectures 17, 18, lecture notes on streaming algorithms by Luca Trevisan.
Feb 14-17: Minor week.
Feb 21, 23, 24: Pushdown Automata- definition, examples; Context-free Grammars -definitions, examples, ambiguity, parse trees, CFG to PDA. Reading: Sipser section 2.1, 2.2, Kozen lectures 19, 21, 23
Feb 26 - Mar 1: Break.
Mar 2, 3: PDA to CFG, Pumping lemma for CFGs, Pumping lemma examples. Reading: Sipser section 2.2, 2.3, Kozen chapters 22,25
Mar 7, 9, 10: Turing machines and computability - definition, examples, variants, Church-Turing Thesis. Reading: Sipser chapter 3, Kozen chapters 28, 29, 30.
Mar 14, 16, 17: Undecidability, Reductions, examples of undecidable problems, LBA, PCP. Reading: Sipser chapter 4, parts of 5, Kozen chapters 31, 32, 33.
Mar 21, 23, 24: Undecidability of PCP, Rice's theorem and applications, Advanced topics - Recursion theorem. Reading: Sipser chapter 5, section 6.1, Kozen chapters 34.
Mar 28, 30, 31: Kolmogorov Complexity, Turing reduction/degrees, Efficient computation. Reading: Sipser sections 6.2, 6.3, 7.2