Fall 2010

Back to the main course website

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

Monday Dec. 6 1-4 pm GHC 4301 |
FINAL EXAM |
Sample final (PDF) |