## Course Schedule, CSCE A351

MS = Automata Textbook (Maheshwair & Smid)
CLRS = Algorithms Textbook (Cormen, Leiserson, Rivest, Stein)

 Date Topic Reading Wk Additional Reading Notes TR Jan 12,14 Introduction and Motivation Mathematical Notation Regular Languages: DFA MS: Chap 1 1 Intro: ppt, pdf Finite Automata: ppt, pdf Video: Lecture 1, Lecture 2 TR Jan 19,21 Mon, Jan 18: MLK Holiday Regular Languages: DFA MS: Chap 2.1-2.3 2 DFAs Video: Lecture 3, Lecture 4 TR Jan 26,28 NFA's Regular Expressions MS: Chap 2.4-2.7 3 Regular Expressions: ppt, pdf Unix/Java RegEx: pdf, RegExprTest.java Video: Lecture 5, Lecture 6 TR Feb 2,4 Pumping Lemma I Context-Free Grammars MS: Chap 2.8-2.9, 3.1-3.2 4 Non-regular langs: pdf, ppt Context-Free Grammars: pdf, ppt Video: Lecture 7, Lecture 8 TR Feb 9,11 Pushdown Automata Pumping Lemma II MS: Chap 3.3-3.8 5 Pushdown automata: pdf, ppt Video: Lecture 9, Lecture 10 TR Feb 16,18 Turing Machines MS: Chap 4 6 Pumping Lemma II: pdf, ppt Turing Machines: pdf, ppt Video: Lecture 11, Lecture 12 TR Feb 23,25 Turing Machines, Decidability Decidability Reducibility MS: Chap 5 7 Video: Lecture 13, Lecture 14 P/NP TR Mar 1,3 Time Complexity, P/NP Midterm, Thursday, Mar. 3 MS: Chap 6, CLRS: Chap 34 8 No Lecture 15 TR Mar 8,10 Complexity, Algorithm Basics, Notation 9 P/NP: pdf, ppt Video: Lecture 16, Lecture 17 TR Mar 15,17 Spring Break CLRS: Chap 1-3 10 . TR Mar 22,24 Recurrence Relations CLRS: Chap 4 11 Video: Lecture 18, Lecture 19 TR Mar 29,31 Selection, Sorting CLRS: Chap 6-9 12 Video: Lecture 20, Lecture 21 TR Apr 5,7 Graphs, Shortest Path CLRS: Chap 22-24,26 13 Graphs/Greedy: pdf, pptx Video: Lecture 22, Lecture 23 TR Apr 12,14 Dynamic Programming CLRS: Chap 15, 25 14 Max Flow: pdf, ppt Dynamic Programming: pdf, Word Video: Lecture 24, No Lecture 25 TR Apr 19,21 String Matching, Other Topics? Voronoi Diagrams? CLRS: Chap 32 15 Video: Lecture 26, Lecture 27 T Apr 26 Final Exam Week (normal classes scheduled on Monday) . Finals Week Final Exam Tuesday 10:00-12:45