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)