COURSE SCHEDULE

Schedule:

>Sections 5.1, pages 216-217
Week Date Topic Readings Posted Materials
1Jan. 10 Course Overview Review Chapter 0 Slides
Jan. 12 Finite Automata Section 1.1, pages 31-40 Notes, exercises, answers
Jan. 14 Definition of Regular Languages Section 1.1, pages 40-44 Notes, delta*, exercises, answers
2Jan. 17 Martin Luther King Jr. Birthday
Jan. 19 Properties of Regular Languages Section 1.1, pages 44-47 Notes, exercises, answers
Jan. 21 Nondeterminism Section 1.2, pages 47-54 Notes, exercises, answers, quiz 1, answers
3Jan. 24 Relation Between NFAs and DFAs Section 1.2, pages 54-63 Notes, exercises, answers, closure under concatenation and Kleene closure
Jan. 26 Regular Expressions Section 1.3, pages 63-66 Notes, example 1.53 (page 65), exercises, answers, quiz 2, answers
Jan. 28 Regular Expressions Describe Regular Languages Section 1.3, pages 66-69 Notes, exercises, answers, Regular Expressions to NFA
4Jan. 31 Regular Languages can be Described by Regular Expressions Section 1.3, pages 69-76 Notes, exercises, answers, quiz 3, answers
Feb. 2 Nonregular Languages Section 1.4, pages 77-82 Notes, recording, exercises, answers
Feb. 4 Pumping Lemma Examples No new readings Notes, exercises, answers, quiz 4, answers
5Feb. 7 More Pumping Lemma Examples No new readings What is known about regular langauges, exercises, answers
Feb. 9 Context-Free Languages Section 2.1, pages 102-107 Notes, slides, exercises, answers
Feb. 11 Exam 1 moved to Monday Regular Languages, Chapter 1 Review 2021 exam, answers
Essay questions, sample answers, exam, sample answers
6Feb. 14 Right Linear Grammars and Regular languages No new readings
Feb. 16 Ambiguity in Grammars and More Examples Section 2.1, pages 107-108 Notes, exercises, answers
Feb. 18 Chomsky Normal Form Section 2.1, pages 108-111 Notes, Noam Chomsky and Chomsky hierarchy via Wikipedia, exercises, answers
7Feb. 21 President's Day
Feb. 23 Push Down Automata Section 2.2, pages 111-116 Notes, recording, exercises, answers
Feb. 25 Context-Free Grammar to a Non-deterministic PDA Section 2.2, pages 117-125 Notes, recursive descent parser from programming languages, recording, exercises, answers
8Feb. 28 Non-deterministic PDA to a Context-Free Grammars Section 2.2, pages 121-125 Notes, exercises, answers
March 2 Pumping Lemma for Context-Free Languages Section 2.3, pages 125-129 Notes , exercises, answers
March 4 More Pumping Lemma examples for Context-Free Languages No new readings Exercises, answers
9March 7 Deterministic Context-Free Languages Section 2.4, pages 130-135
March 9 Deterministic Context-Free Grammars and the Relationship of DPDAs and DCFGs Section 2.4, pages 135-154
March 11 Exam 2 Chapters 1 and 2 Review 2021 exam, answers
Essay questions, sample answers, exam, sample answers


Spring Break, March 14-18
10March 21 Turing Machines Section 3.1, pages 165-170 Notes, The Imitation Game, Turing's Bombe machine, exercises, answers
March 23 More Practice Defining Turing Machines Section 3.1, pages 170-175 Exercises, sample answers
March 25 Variations of Turing Machines Section 3.2, pages 176 Notes, exercises, answers
11March 28 Multitape Turing Machines Section 3.2, pages 176-178 Notes, exercises, answers
March 30 Nondeterministic Turing Machine Section 3.2, pages 178-180 Notes, recording, exercises, answers
April 1 Algorithms Section 3.3, pages 182-187 Notes, recording, exercises, answers
12April 4 Decidability: Problems Concerning Finite Automaton Section 4.1, pages 193-197 Exercises, sample answers
April 6 Decidability: Problems Concerning Context Free Languages Section 4.1, pages 198-201 Exercises, sample answers
April 8 Undecidability Section 4.2, pages 201-202 Notes, exercises, sample answers
13April 11 Cantor's Diagonalizaion Section 4.2, pages 202-209 Notes, exercises, sample answers
April 13 Exam 3 Chapters 1, 2, 3 and 4, pages 193-197 Review, 2021 exam, answers
Essay questions, exam, answers
April 15 Mini Spring Break
14April 18 Example Undecidable Language and Turing-Unrecognizable Language Section 4.2, pages 209-210
April 20 Halting Problem
April 22 Measuring Complexity and the Relationships amoung Complexity Models
Sections 7.1, pages 275-286 Notes, exercises, answers
15April 25 The Class P Section 7.2, pages 284-291 Notes, exercises, answers
April 27 Nondeterministic Polynomial Time Section 7.3, pages 292-298 Slides, notes, exercises, answers
April 29 NP-Completeness and the Cook Levin Theory Section 7.4, pages 299-311
May 5 Final Exam, Thursday, 3:00pm-5:00pm (6:00pm if needed) Review, 2021 final, answers
Essay questions