LE/EECS 2001: Introduction to the Theory of Computation, Winter 2024
Basic Information
Instructor: Aditya Potukuchi
Time: Tue (DB 001), Thr(DB 0016) 14:30-16:00,Â
Tutorial: F 14:30-16:00, CLH G
Office Hours: Thursday 11:00-12:00 or by appointment LAS 3052B
Schedule
Jan9 : Introductory remarks, math background; Reading: Sipser Ch 0.
Jan11: Intro to Finite Automata; Reading: Sipser Ch 1.1
Jan 16: Regular operators; Reading: Sipser Ch 1.1, The Regular Operators
Jan 18: Regular operators contd.., Intro to nondeterminism; Reading: Sipser Ch 1.1, Ch1.2
Jan 23: Nondeterminism; Reading: Sipser Ch 1.2
Jan 25: Regular Expressions; Reading: Sipser Ch 1.3
Jan 30: Practice problems
Feb 1: Introduction to non-regularity; Reading: Sipser Ch 1.4
Feb 6: Pumping lemma; Reading: Ch 1.4
Feb 8: Practice problems from Chapter 1
Feb 13: Intro to Computability; Reading: Sipser Ch 3
Feb 15: Review
Feb 27: Turing Machines, intro to countability; Reading: Sipser Ch 4.1
Feb 29: Decidable languages, countability of Rational numbers; Reading: Sipser Ch 4.2
Mar5: Uncountability of real numbers; Reading: Sipser Ch 4.2
Mar7: Undecidability of Halting problem; Reading: Sipser Ch 4.2
Mar12: More on undecidability and uncountability