Week | Date | Topic | Readings | Posted Materials | |
---|---|---|---|---|---|
1 | Jan. 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 | ||
2 | Jan. 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 | ||
3 | Jan. 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 | ||
4 | Jan. 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 | ||
5 | Feb. 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 |
||
6 | Feb. 14 |
|
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 | ||
7 | Feb. 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 |
8 | Feb. 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 | ||
9 | March 7 | ||||
March 9 | |||||
March 11 | Exam 2 | Chapters 1 and 2 |
Review
2021 exam,
answers
Essay questions, sample answers, exam, sample answers |
||
Spring Break, March 14-18 |
|||||
10 | March 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 | ||
11 | March 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 | ||
12 | April 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 | ||
13 | April 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 | ||||
14 | April 18 |
|
|||
April 20 | >Sections 5.1, pages 216-217 | ||||
April 22 | Measuring Complexity and the Relationships amoung Complexity Models | Sections 7.1, pages 275-286 | Notes, exercises, answers | ||
15 | April 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 |