| Date | Topic | Instructor | Reading | Homework |
| Introduction to NLP (slides) | Lavie | Allen: 1 (all); Rich & Knight: 14.1-14.2, 15.1-15.2 |
||
| Introduction to Formal Language Theory (Notation, DFSA) (Notes) | Lavie | Hopcroft & Ullman: 1 (all), 2.1, 2.2 | ||
| Formal Language Theory (NDFSA) | Lavie | Hopcroft & Ullman: 2.3, 2.4 | ||
Formal Language Theory  ) |
Lavie | Hopcroft & Ullman: 2.5 | Hand-in guidelines; Homework 1 | |
| Recitation (Equivalence of Dual-Control FSAs and DFSAs) | Heafield | Exercises; Notes and solutions | ||
| Formal Language Theory (REs, FSA with Output) | Lavie | Hopcroft & Ullman: 3.1, 3.2 | ||
| Formal Language Theory (Pumping Lemma, Properties of Regular Languages) | Lavie | Hopcroft & Ullman: 4.1-4.3 | ||
| Formal Language Theory (Context-Free Grammars) | Lavie | Hopcroft & Ullman: 5.1, 5.2, 5.4 | ||
| Formal Language Theory (Pushdown Automata) | Lavie | Hopcroft & Ullman: 6.1-6.3 | ||
| Recitation (Power-Set Construction and the Pumping Lemma) | Heafield | Exercises; Notes and solutions | ||
| Introduction to Analysis of Algorithms Slides 2009 slides | Heafield | Homework 1 due: solutions. Homework 2 out. | ||
| Formal Language Theory | Lavie | |||
| Formal Language Theory: PDAs | Lavie | |||
| Lexical Analysis and Organization Notes | Frederking | Allen: 2 (all), 3.7, 4.1-4.3, 9.2, 9.4 | ||
| Recitation | Heafield | Exercises Solutions | ||
| Search Techniques and Algorithms 2009 Part I | Frederking | Rich & Knight: 2 (all), 3 (pp. 63-79) | Homework 2 due. Solutions | |
| Morphology Notes | Lavie | Jurafsky and Martin, Ch. 3 OPTIONAL: Kaplan & Kay; Oflazer; Karttunen et al. |
||
| Recitation: equivalence of empty stack and final state | Heafield | Exercises Solutions | ||
| More morpology | Lavie | |||
| Part-of-Speech Tagging 2009 Notes | Lavie | Allen: 7.1-7.4; Manning & Shuetze: Ch 10. |
||
| Midterm Review | 2002 Midterm Solutions | |||
| MIDTERM EXAM | ||||
| Search 2009 Part II; Parsing CFLs: CYK Algorithm 2009 Notes | Frederking and Lavie | Hopcroft, Motwani & Ullman: 7.4 (pp. 298-302) | Homework 3 Optional code | |
| Recitation | Heafield | Solutions | ||
| Parsing CFLs: Chart Parsing (2009 Notes) | Lavie | Allen: 3.4 | ||
| Parsing CFLs: Earley Parsing Algorithm (2009 Notes) | Lavie | Earley, An Efficient Context-Free Parsing Algorithm | ||
| Parsing CFLs: LR Parsing (2009 Notes) | Hanneman | Hopcroft & Ullman: 10.6-10.7 (pp. 248-256) Note: Only appears
in old edition of the book. OPTIONAL: Aho, Sethi, & Ullman, 4.7 |
Handout | |
| Parsing: Statistical Parsing (2009 Notes) | Smith | Manning & Schuetze: 11, 12; RECOMMENDED: Charniak, Statistical Techniques for Natural Language Parsing |
Homework 3 due. Solutions | |
| Parsing CFLs: GLR Parsing (2008 Notes) | Lavie | Tomita, An Efficient Augmented Context-Free Parsing Algorithm | Homework 4 and code | |
| Parsing: Unification Grammars (2008 Notes) | Lavie | Allen: 4 (all, 4.6 optional) | ||
| Recitation | Heafield | Earley parsing lecture | ||
| Ambiguity Resolution: Principle-Based Methods (2008 Part I, 2008 Part II) | Frederking | Allen: Section 6 except 6.2 | ||
| Semantic Processing I (2008 Notes) | Frederking | Allen: 8 | ||
| Semantic Processing II (2009 Notes) | Frederking | Allen: 8, Rich & Knight: 10.1, 10.2 | Homework 4 due Solutions; Homework 5 | |
| NO CLASS: Thanksgiving Break | ||||
| Natural Language Generation (2008 Notes) | Lavie | Reiter & Dale | ||
| Final lecture: Hard Problems in NLP | Carbonell | Homework 5 due. Solutions | ||
| Final Review | Lavie, Frederking, and Heafield | |||
| FINAL EXAM | Sample final (PDF) |