COURSE SCHEDULE

Schedule:

Week Date Topic Readings Posted Materials
1Jan. 4 Course Overview Review Chapter 0 Slides, recording (.mp4)
Jan. 6 Finite Automata Section 1.1, pages 31-40 Notes, exercises, answers
Jan. 8 Definition of Regular Languages Section 1.1, pages 40-44 Notes, exercises, answers
2Jan. 11 Properties of Regular Languages Section 1.1, pages 44-47 Notes, exercises, answers
Jan. 13 Nondeterminism Section 1.2, pages 47-54 Notes, exercises, answers, recording, learning check, answers
Jan. 15 Relation Between NFAs and DFAs Section 1.2, pages 54-63 Notes, exercises, answers, recording, learning check, answers
3Jan. 18 Martin Luther King Jr. Birthday
Jan. 20 Regular Expressions Section 1.3, pages 63-66 Notes, Example 1.53 (page 65), exercises, answers, recording, review
Jan. 22 Regular expressions describe regular languages Section 1.3, pages 66-69 Notes, Regular Expressions to NFA, exercises, answers
4Jan. 25 Regular languages can be described by regular expressions Section 1.3, pages 69-76
Jan. 27 Nonregular Languages Section 1.4, pages 77-82 Notes, recording, exercises, answers
Jan. 29 Exam 1 Regular Languages, Chapter 1, pages 31-76 Review, 2020 exam, answers, exam, answers
5Feb. 1 Pumping Lemma Examples No new readings Notes, recording, exercises, answers
Feb. 3 More Pumping Lemma Examples No new readings What is known about regular langauges, recording, exercises, answers
Feb. 5 Context-Free Languages Section 2.1, pages 102-107 Notes, slides, recording, exercises, answers, learning check #3, answers
6Feb. 8 Ambiguity in Grammars and More Examples Section 2.1, pages 107-108 Notes, recording, exercises, answers
Feb. 10 Chomsky Normal Form Section 2.1, pages 108-111 Notes, Noam Chomsky and Chomsky hierarchy via Wikipedia, recording, exercises, answers, learning check #4, answers
Feb. 12 Push Down Automata Section 2.2, pages 111-116 Notes, recording, exercises, answers, 2nd set of exercises, answers
7Feb. 15 President's Day
Feb. 17 Equivalence of Non-deterministic PDA and Context-Free Grammars Section 2.2, pages 117-121 Notes, recording, recursive descent parser from programming languages, exercises, answers
Feb. 19 Pumping Lemma for Context-Free Languages Section 2.3, pages 125-129 Notes, recording, exercises, answers
8Feb. 22 More Pumping Lemma for Context-Free Languages No new readings Recording, exercises, answers
Feb. 24 Deterministic Context-Free Languages Section 2.4, pages 130-135 Notes, exercises, answers
Feb. 26 Exam 2 Chapters 1 and 2 Review, 2020 exam, answers, exam, answers
9March 1 Deterministic Context-Free Grammars Section 2.4, pages 135-146
March 3 Relationship of DPDAs and DCFGs Section 2.4, pages 146-154
March 5 Turing Machines Section 3.1, pages 165-170 Notes, The Imitation Game, Turing's Bombe machine, recording, exercises, answers, video of selected answers
10March 8 More Practice Defining Turing Machines Section 3.1, pages 170-175 Recording, exercises, answers, video of answers
March 10 Variations of Turing Machines Section 3.2, pages 176 Recording, exercises, answers
March 12 Multitape Turing Machines Section 3.2, pages 176-178 Notes, recording, homework, answers, lecture from 2018
11March 15 Nondeterministic Turing Machine Section 3.2, pages 178-180 Notes, recording, homework, answers
March 17 Algorithms Section 3.3, pages 182-187 Notes, recording, homework, answers, learning check #5, answers
March 19 Decidability: Problems Concerning Finite Automaton Section 4.1, pages 193-197 Recording, homework, answers, learning check #6, answers
12March 22 Decidability: Problems Concerning Context Free Languages Section 4.1, pages 198-201 Homework, answers
March 24 Undecidability Section 4.2, pages 201-202 Notes, homework, answers
March 26 Exam 3 Chapters 1, 2, 3 and 4, pages 193-197 Review, practice grid, answers, 2020 final, answers
Exam, answers, essay questions, answers
13March 29 Cantor's Diagonalizaion Section 4.2, pages 202-209 Notes, recording, homework, answers
March 31 Example Undecidable Language and Turing-Unrecognizable Language Section 4.2, pages 209-210 Notes, recording, homework, answers
April 2 Mini Spring Break
14April 5 Measuring Complexity and the Relationships amoung Complexity Models
Also, "Godel's Incompleteness Theorem" by Burak Adam.
Sections 7.1, pages 275-286 Notes, homework, answers
April 7 "Magic:The Gathering is Turing Complete" by Xaavan Dolence."
April 9 The Class P Section 7.2, pages 284-291
15April 12 Nondeterministic Polynomial Time Section 7.3, pages 292-298
April 14 NP-Completeness Section 7.4, pages 299-304
April 16 Cook Levin Theorem Section 7.4, pages 304-311 Notes, recording
April 22 Final Exam, Thursday, 3:00pm-5:00pm (6:00pm if needed) Review, 2019 final, answers
exam, answers