LE/EECS 2001: Introduction to the Theory of Computation, Winter 2023

Basic Information

Instructor: Aditya Potukuchi

Time: Tue (CLH G), Thr(DB 0016) 14:30-16:00, LSB103

Tutorial: F 14:30-16:00, CLH G

Office Hours: Friday 16:30-17:30 or by appointment LAS 3030

Basic info handout

Problem set 1

Problem set 2

Schedule

Jan10 : Introductory remarks, math background; Reading: Sipser Ch 0.

Jan12: Math background contd., Definition of Finite Automata; Reading: Chapter 1.1: Finite Automata, Formal definition of a Finite Automata, Examples of Finite Automata

Jan17:  Regular operators; Reading: Chapter 1.1: Designing Finite Automata, The Regular Operators

Jan19: Regular operators contd., intro to nondeterminism; Reading: Chapter 1.1: The Regular Operators, Chapter 1.2: Nondeterminism

Jan24: Equivalence of NFAs and DFAs; Reading: Chapter 1.2: Equivalence of NFAs and DFAs, Closure under Regular Operators

Jan26: Regular Expressions; Reading: Chapter 1.3: Regular Expressions

Jan31: Practice; Reading: Problems 1.34, 1.36, 1.48

Feb2:  More Practice; Reading: Chapter 1 Problems and Exercises

Feb7: Intro to nonregular languages: Pumping Lemma; Reading Chapter 1.4: Nonregular languages

Feb9: Using Pumping Lemma; Reading: Chapter 1.4: Nonregular languages

Feb14: Quiz 1

Feb16: Regular languages wrap-up.

Feb21: No class: reading week

Feb23: No class: reading week

Feb28: Introduction to Turing machines; Reading: Chapter 3.1, this video

Mar2: Intro to T.Ms contd..; Reading: Chapter 3.1

Mar7:  Intro to pseudocode; Reading: Chapter 3.3: The definiton of algorithm

Mar9: Pseudocodes contd.., intro to decidability; Reading: Chapter 4.1: Deaciable languages

Mar14: Decidability contd.., intro to Halting Problem; Reading: Chapters 4.1: Decidable languages, Chapter 4.2: The Halting Problem

Mar16: Halting problem contd..; Reading: Chapter 4.2: The Halting Problem

Mar21: Halting problem is undecidable; Reading: Chapter 4.2: The Halting Problem