11-711 Algorithms for NLP

Fall 2009

Detailed Class Schedule

(Posted material is subject to change; announcement will be made during the class)

Back to the main course website

Date Topic Instructor Reading Homework
Aug. 25
 Introduction to NLP (2009 Notes) Lavie Allen: 1 (all);
Rich & Knight: 14.1-14.2, 15.1-15.2
--
Aug. 27
 Introduction to Analysis of Algorithms (2009 Notes) Phillips
--
--
Sept. 1
 Search Techniques and Algorithms (2009 Part I, 2009 Part II) Frederking Rich & Knight: 2 (all), 3 (pp. 63-79)
--
Sept. 3
 Introduction to Formal Language Theory (Notation, DFSA) (2009 Notes) Lavie Hopcroft & Ullman: 1 (all), 2.1, 2.2
--
Sept. 4
 Recitation (Search) Phillips
--
--
Sept. 8
 Formal Language Theory (NDFSA) Lavie Hopcroft & Ullman: 2.3, 2.4
--
Sept. 10
 Formal Language Theory (NDFSA-epsilon) Lavie Hopcroft & Ullman: 2.5 Hand-in guidelines (PDF); Homework #1 (PDF)
Sept. 11
 Recitation (Equivalence of Dual-Control FSAs and DFSAs) Phillips
--
 Exercises (PDF); Notes and solutions (PDF)
Sept. 15
 Formal Language Theory (REs, FSA with Output) Lavie Hopcroft & Ullman: 3.1, 3.2
--
Sept. 17
 Formal Language Theory (Pumping Lemma, Properties of Regular Languages) Lavie Hopcroft & Ullman: 4.1-4.2
--
Sept. 18
 Recitation (Power-Set Construction and the Pumping Lemma) Phillips
--
 Exercises (PDF); Notes and solutions (PDF)
Sept. 22
 Formal Language Theory (Decision Problems for Regular Languages) Lavie Hopcroft & Ullman: 4.3
--
Sept. 24
 Formal Language Theory (Context-Free Grammars) Lavie Hopcroft & Ullman: 5.1, 5.2, 5.4 Homework #1 due; Homework #2 (PDF)
Sept. 29
 Formal Language Theory (Pushdown Automata) Lavie Hopcroft & Ullman: 6.1-6.3
--
Oct. 1
 Formal Language Theory (Pushdown Automata) Lavie Hopcroft & Ullman: 6.1-6.3
--
Oct. 2
 Recitation (Simulation of CFGs with PDAs & Homework #1 Solutions)
2-3pm in GHC 4405		 Phillips
--
 Exercises (PDF); Notes and solutions (PDF); Homework #1 Solutions (PDF)
Oct. 6
 Morphological Analysis (2009 Notes) Lavie Jurafsky and Martin, Ch. 3
OPTIONAL: Kaplan & Kay; Oflazer; Karttunen et al.
--
Oct. 8
 Lexical Analysis and Organization (2009 Notes) Frederking Allen: 2 (all), 3.7, 4.1-4.3, 9.2, 9.4 Homework #2 due; Extra Exercises (PDF)
Oct. 9
 Recitation (Equivalence of PDA acceptance by final state and empty state) Phillips
--
 Notes and solutions (PDF); Homework #2 Solutions (PDF); Solutions to Extra Exercises (PDF)
Oct. 13
 Part-of-Speech Tagging (2009 Notes) Lavie Allen: 7.1-7.4;
Manning & Shuetze: Ch 10.		 2002 Midterm (PDF); 2002 Midterm Solutions (PDF)
Oct. 15
 Part-of-Speech Tagging Lavie
--
--
Oct. 19
 Midterm Review
4-5pm in GHC 4405
Lavie, Frederking, Phillips
--
--
Oct. 20
 MIDTERM EXAM
--
--
 Homework #3 (PDF, Sample Code)
Oct. 22
 Parsing CFLs: CYK Algorithm (2009 Notes) Lavie Hopcroft, Motwani & Ullman: 7.4 (pp. 298-302)
--
Oct. 23
 Recitation (Markov POS Tagging) Phillips
--
 Notes and solutions (PDF)
Oct. 27
 Parsing CFLs: Chart Parsing (2009 Notes) Lavie Allen: 3.4
--
Oct. 29
 Parsing CFLs: Earley Parsing Algorithm (2009 Notes) Lavie Earley, An Efficient Context-Free Parsing Algorithm
--
Oct. 30
 Recitation (Chart Parsing) Phillips
--
 Notes and solutions (PDF)
Nov. 3
 Parsing CFLs: LR Parsing (2009 Notes) Lavie Hopcroft & Ullman: 10.6-10.7 (pp. 248-256) Note: Only appears in old edition of the book.
OPTIONAL: Aho, Sethi, & Ullman, 4.7		 Homework #3 due;
Homework #4 (PDF, Sample Code)
Nov. 5
 Parsing CFLs: GLR Parsing (2008 Notes) Lavie Tomita, An Efficient Augmented Context-Free Parsing Algorithm Homework #3 Solutions (PDF)
Nov. 5
 Recitation (GLR Parsing) Phillips
--
--
Nov. 10
 Parsing: Unification Grammars (2008 Notes) Lavie Allen: 4 (all, 4.6 optional)
--
Nov. 12
 Parsing: Statistical Parsing (2009 Notes) Noah Smith Manning & Schuetze: 11, 12;
RECOMMENDED: Charniak, Statistical Techniques for Natural Language Parsing
--
Nov. 17
 Ambiguity Resolution: Principle-Based Methods (2008 Part I, 2008 Part II) Frederking Allen: 6 Homework #4 due; Homework #5 (PDF)
Nov. 19
 Semantic Processing I (2008 Notes) Frederking Allen: 8 Homework #4 Solutions (PDF)
Nov. 20
 Recitation Phillips
--
--
Nov. 24
 Semantic Processing II (2009 Notes) Frederking Allen: 8, Rich & Knight: 10.1, 10.2
--
Nov. 26
 NO CLASS: Thanksgiving Break
--
--
--
Dec. 1
 Natural Language Generation (2008 Notes) Lavie Reiter & Dale Homework #5 due
Dec. 3
 Hard Problems in NLP Carbonell
--
 Homework #5 Solutions (PDF)
Dec. 9
 Midterm Review
4-5pm in GHC 6501
Lavie, Frederking, Phillips
--
--
Dec. 11
 FINAL EXAM
1–4 p.m. in PH A18A
--
GOOD LUCK!
 Sample final (PDF)