COURSE SCHEDULE

Changes due to COVID-19 are explained under the "Course Information" tab.

Schedule:

Week Date Topic Readings Posted Materials
1Jan. 6 Course Overview Review Chapter 0 Slides
Jan. 8 Finite Automata Section 1.1, pages 31-40 Notes, homework answers
Jan. 10 Definition of Regular Languages Section 1.1, pages 40-44 Notes, homework answers
2Jan. 13 Properties of Regular Languages Section 1.1, pages 44-47 Notes, homework answers
Jan. 15 Nondeterminism Section 1.2, pages 47-54 Notes, delta star, homework answers
Jan. 17 Relation Between NFAs and DFAs Section 1.2, pages 54-63 Notes, homework answers
3Jan. 20 Martin Luther King Jr. Birthday
Jan. 22 Regular Expressions Section 1.3, pages 63-66 Notes, Example 1.53 (page 65), homework answers
Jan. 24 Regular expressions describe regular languages Section 1.3, pages 66-69 Notes, if and only if, regular expression to NFA, homework answers
4Jan. 27 Regular languages can be described by regular expressions Section 1.3, pages 69-76 Notes, homework answers
Jan. 29 Nonregular Languages Section 1.4, pages 77-82 Notes, homework answers
Jan. 31 Pumping Lemma Examples No new readings Notes, homework answers
5Feb. 3 More Pumping Lemma Examples No new readings sample answers to extra problems
Feb. 5 Context-Free Languages Section 2.1, pages 102-107 Slides, notes, homework answers
Feb. 7 Exam 1 Regular Languages, Chapter 1 Review, essay questions, answers, 2019 exam, answers, exam, answers
6Feb. 10 Go Over Exam
Feb. 12 Ambiguity in Grammars and More Examples Section 2.1, pages 107-108 Notes, homework answers
Feb. 14 Chomsky Normal Form Section 2.1, pages 108-111 Notes, homework answers, Noam Chomsky and Chomsky hierarchy via Wikipedia
7Feb. 17 President's Day
Feb. 19 Push Down Automata Section 2.2, pages 111-116 Notes, notes with sample asnwers, homework answers
Feb. 21 Equivalence of Non-deterministic PDA and Context-Free Grammars Section 2.2, pages 117-121 Notes, homework answers
8Feb. 24 Pumping Lemma for Context-Free Languages Section 2.3, pages 125-129 Notes, notes with sample answers, homework answers
Feb. 26 More Pumping Lemma for Context-Free Languages No new readings Homework answers
Feb. 28 Deterministic Context-Free Languages Section 2.4, pages 130-135 Notes, homework answers
9March 2 Deterministic Context-Free Grammars Section 2.4, pages 135-146 Notes
March 4 Relationship of DPDAs and DCFGs Section 2.4, pages 146-154
March 6 Turing Machines Section 3.1, pages 165-170 Notes, homework answers, The Imitation Game, Turing's Bombe machine
10March 9 More Practice Defining Turing Machines Section 3.1, pages 170-175 Notes, sample answers
March 11 Exam 2 - moved to Friday, March 6th Chapters 1 and 2 Review, essay question, answers, 2019 exam, answers, exam, answers
March 13 Variations of Turing Machines Section 3.2, pages 176 Notes, homework answers


Spring Break, March 16-20

11March 23 Multitape Turing Machines Section 3.2, pages 176-178 Notes, lecture, homework, answers
March 25 Nondeterministic Turing Machine Section 3.2, pages 178-180 Notes, homework, answers
March 27 Algorithms Section 3.3, pages 182-187 Notes, homework, answers
12March 30 Decidability: Problems Concerning Finite Automaton Section 4.1, pages 193-197 Notes, sample answers, homework, answers
April 1 Decidability: Problems Concerning Context Free Languages Section 4.1, pages 198-201 Homework, answers
April 3 Undecidability Section 4.2, pages 201-202 Notes
13April 6 Cantor's Diagonalizaion Section 4.2, pages 202-209 Notes, homework, answers, overview
April 8 Example Undecidable Language and Turing-Unrecognizable Language Section 4.2, pages 209-210 Notes, homework, answers
April 10 Mini Spring Break
14April 13 Measuring Complexity / Polynomial Time Section 7.1, pages 275-284 / Section 7.2, pages 284-291 Notes, homework, answers
notes, homework, answers
April 15 Nondeterministic Polynomial Time / NP-Completeness Section 7.3, pages 292-298 / Section 7.4, pages 299-304 Notes, homework, answers
April 17 Cook Levin Theorem Section 7.4, pages 304-311 Notes
15April 20 Nondeterministic Polynomial Time Section 7.3, pages 292-298
April 22 NP-Completeness Section 7.4, pages 299-304
April 24 Cook Levin Theorem Section 7.4, pages 304-311
April 30 23 Final Exam, Thursday, 3:00pm-5:00pm (6:00pm if needed) Review, essay questions, 2019 exam, answers
EXAM: exam, answers