CSCI 438, Spring 2020

Week | Date | Topic | Readings | Posted Materials |
---|---|---|---|---|

1 | Jan. 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 | |

2 | Jan. 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 | |

3 | Jan. 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 | |

4 | Jan. 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 | |

5 | Feb. 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 | |

6 | Feb. 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 | |

7 | Feb. 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 | |

8 | Feb. 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 | |

9 | March 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 | |

10 | March 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 |
||||

11 | March 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 | |

12 | March 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 | |

13 | April 6 | Cantor's Diagonalizaion | Section 4.2, pages 202-209 | Notes, homework, overview |

April 8 | Example Undecidable Language and Turing-Unrecognizable Language | Section 4.2, pages 209-210 | Notes, homework | |

April 10 | Mini Spring Break | |||

14 | April 13 | Measuring Complexity / Polynomial Time | Section 7.1, pages 275-284 / Section 7.2, pages 284-291 | |

April 15 | Nondeterministic Polynomial Time / NP-Completeness | Section 7.3, pages 292-298 / Section 7.4, pages 299-304 | ||

April 17 | Cook Levin Theorem | Section 7.4, pages 304-311 | ||

April |
Final Exam, Thursday, 3:00pm-5:00pm (6:00pm if needed) |