CSE105 - Fall 2015: Schedule and Readings

Chapter pointers refer to the course textbook, M. Sipser, Introduction to the Theory of Computation. Reading assignments for future lectures are tentative, and they are provided in case you want to read ahead. In addition to the lecture notes and reading assignments from the textbook posted on this page, you should read also the lecture notes posted on the course main page

Date Topic Reading/Notes
Fri, Sep 25 Introduction Ch. 0
Mon, Sep 28 DFAs Ch. 1.1, notes on DFA
Wed, Sep 30 Computations Ch. 1.1
Fri, Oct 2 Closure properties Ch. 1.2
Mon, Oct 5 NFAs Ch. 1.2, notes on NFA
Wed, Oct 7 Regular Operations Ch. 1.2
Fri, Oct 9 Regular Expressions Ch. 1.3
Mon, Oct 12 Equivalence of DFA and Regex Ch. 1.3
Wed, Oct 14 Nonregular languages notes on Diagonalization
Fri, Oct 16 Pumping Lemma Ch. 1.4
Mon, Oct 19 Review Midterm 1 (7pm)
Wed, Oct 22 Proving nonregular languages All of Ch. 1
Fri, Oct 23 Finite State Transducers notes on (N)FST
Mon, Oct 26 Nondeterministic FST NFST
Wed, Oct 28 Context Free Grammars Ch. 2.1
Fri, Oct 30 Review
Mon, Nov 2 More CFGs and ambiguity Ch. 2.1
Wed, Nov 4 Non Context Free Languages Ch. 2.3 and Diagonalization
Fri, Nov 6 Push Down Automata Ch. 2.2
Mon, Nov 9 Turing Machines Ch. 3
Fri, Nov 13 Review Midterm 2 (5pm)
Mon, Nov 16 More on TM and Reductions FST and mapping reductions
Wed, Nov 18 Mapping reductions Ch. 4.2, Ch. 5.3
Fri, Nov 20 Decidable Languages Ch. 4.1
Mon, Nov 23 Undecidable Problems Ch. 5.1
Wed, Nov 25 More undecidable Problems Ch. 5.2
Mon, Nov 30 More undecidable Problems
Wed, Dec 2 Review Ch 1-5
Fri, Dec 4 What’s next? Ch. 7-8
Wed, Dec 9 Final Exam (7:00p-9:50p)