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

Basic info handout

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