LE/EECS 2001: Introduction to the Theory of Computation, Fall 2024

Basic Information

Instructor: Aditya Potukuchi

Time: Tue + Thr 11:30-13:00, LSB106

Tutorial: Fri 11:30-13:00, LSB105

Office Hours: Tue 14:00-15:00 or by appointment LAS 3052B

Basic info handout 

Schedule

Sep 5: Basic admin stuff

Sep 10: Intro to finite automata; Reading: Ch 1.1

Sep 12: Finite automata contd.., regular operators; Reading: Ch 1.1

Sep 17: Regular operators contd.., intro to nondeterminism; Reading: Ch 1.1

Sep 19: Nondeterministic Finite Automata; Reading: Ch 1.2

Sep 24: NFAs contd..; Reading: Ch 1.2

Sep 26: NFAs contd..; Reading: Ch 1.2

Oct 1: Regular expressions; Reading: Ch 1.3

Oct 3: Regular expressions contd..; Reading: Ch 1.3

Oct 8: Practice session

Oct 10: Practice session

Oct 15,17: No class, reading week

Oct 22: Non-regular languages; Reading: Ch 1.4 (full thing, specifically Theorem 1.70 and the following discussion)

Oct 24: Non-regular languages contd.; Reading: Ch 1.4

Oct 29: Review

Oct 31: Review

Nov 5: Introduction to Turing Machines, decidability; Reading: Ch 3.1

Nov 7: Decidability, countability, contd..; Reading: Ch 4.1

Nov 12: Countability and uncountability recap; Reading: Ch 4.2

Nov 14: Undecidability and the Halting problem; Reading: Ch 4.2

Nov 19: Practice problems for decidability

Nov 21: Halting problem is undecidable; Reading: Ch 5.1

Nov 26: Undecidability contd.; Reading: Ch 5.1

Nov 28: Context free intro.; Reading: Ch 2.1

Dec 3: Final tutorial