11-711 Algorithms for NLP

Fall 2007


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. 28
Introduction to NLP (PDF) Lavie Allen: 1 (all);
Rich & Knight: 14.1-14.2, 15.1-15.2
--
Aug. 30
Introduction to Formal Language Theory (Notation, DFSA) (PDF) Lavie Hopcroft & Ullman: 1 (all), 2.1, 2.2
--
Sept. 4
Formal Language Theory (NDFSA) Lavie Hopcroft & Ullman: 2.3, 2.4
--
Sept. 5
Recitation #1 (Equivalence of Dual-Control FSAs and DFSAs) Hanneman Exercises (PDF); Notes and solutions (PDF)
--
Sept. 6
Formal Language Theory (NDFSA-epsilon) Lavie Hopcroft & Ullman: 2.5 Hand-in guidelines (PDF); Homework #1 (PDF) (TeX)
Sept. 11
Formal Language Theory (REs, FSA with Output) Lavie Hopcroft & Ullman: 3.1, 3.2
--
Sept. 13
Formal Language Theory (Pumping Lemma, Properties of Regular Languages) Lavie Hopcroft & Ullman: 4.1-4.3
--
Sept. 18
Formal Language Theory (Context-Free Grammars) Lavie Hopcroft & Ullman: 5.1, 5.2, 5.4
--
Sept. 19
Recitation #2 (Power Set Construction, Pumping Lemma, Equivalence of Regular Expressions and FSAs) Hanneman Exercises (PDF); Notes and solutions (PDF)
--
Sept. 20
Formal Language Theory (Pushdown Automata) Lavie Hopcroft & Ullman: 6.1-6.3 Homework #1 due; Solutions (PDF)
Sept. 25
Formal Language Theory (PDF) Lavie Hopcroft & Ullman: 6.1-6.3 Homework #2 (PDF)
Sept. 27
Formal Language Theory Lavie
--
--
Oct. 2
Search Techniques and Algorithms (PDF, PDF) Frederking Rich & Knight: 2 (all), 3 (pp. 63-79)
--
Oct. 3
Recitation #3 (Simulation of CFGs with PDAs) Hanneman Exercises (PDF); Notes and solutions (PDF)
--
Oct. 4
Lexical Analysis and Organization (PS) Frederking Allen: 2 (all), 3.7, 4.1-4.3, 9.2, 9.4
--
Oct. 9
Morphological Analysis (PPT) Lavie Jurafsky and Martin, Ch. 3
OPTIONAL: Kaplan & Kay; Oflazer; Karttunen et al.
Homework #2 due; Solutions (PDF)
Oct. 10
Recitation #4 (Analysis of Algorithms) (PDF) Hanneman Cormen, Leiserson & Rivest: 1 (all), 2 (all), 3.1
--
Oct. 11
Morphological Analysis Lavie Jurafsky and Martin, Ch. 3
OPTIONAL: Kaplan & Kay; Oflazer; Karttunen et al.
--
Oct. 16
Part-of-Speech Tagging (PDF) Lavie Allen: 7.1-7.4;
Manning & Shuetze: Ch 10.
Homework #3 (PDF)
Oct. 18
Part-of-Speech Tagging Lavie Allen: 7.1-7.4;
Manning & Shuetze: 10.
--
Oct. 22
Midterm Review Session
5–6:30 p.m. in Wean 4623
Lavie and Frederking
--
--
Oct. 23
MIDTERM EXAM
--
Sample midterm (PDF); Solutions (PDF); This year's solutions (PDF)
--
Oct. 25
Parsing CFLs: CYK Algorithm (PDF) Lavie Hopcroft, Motwani & Ullman: 7.4 (pp. 298-302)
--
Oct. 30
Parsing CFLs: Chart Parsing (PDF) Lavie Allen: 3.4
--
Oct. 31
Recitation #5 (Bigram Markov POS Tagging) Hanneman Exercises (PDF); Notes and solutions (PDF)
--
Nov. 1
Parsing CFLs: Earley Parsing Algorithm (PDF) Lavie Earley, An Efficient Context-Free Parsing Algorithm
--
Nov. 6
Parsing CFLs: LR Parsing (PDF) 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; Solutions (PDF);
Homework #4 (PDF)
Nov. 8
Parsing CFLs: LR Parsing 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
--
Nov. 13
Parsing CFLs: GLR Parsing (PDF) Lavie Tomita, An Efficient Augmented Context-Free Parsing Algorithm
--
Nov. 14
Recitation #6 (Chart Parsing) Hanneman Exercises (PDF); Notes and solutions (PDF)
--
Nov. 15
Parsing: Unification Grammars (PDF) Lavie Allen: 4 (all, 4.6 optional)
--
Nov. 20
Parsing: Statistical Parsing (PDF) Noah Smith Manning & Schuetze: 11, 12;
RECOMMENDED: Charniak, Statistical Techniques for Natural Language Parsing
--
Nov. 22
NO CLASS: Thanksgiving Break
--
--
--
Nov. 27
Ambiguity Resolution: Principle-Based Methods (PDF, PDF) Frederking Allen: 6 Homework #4 due; Solutions (PDF);
Homework #5 (PDF)
Nov. 28
Recitation #7 (Unification) Hanneman Notes and solutions (PDF)
--
Nov. 29
Semantic Processing I (PPT) Frederking Allen: 8
--
Dec. 4
Semantic Processing II (PPT) Frederking Allen: 8, Rich & Knight: 10.1, 10.2
--
Dec. 6
Hard problems in NLP Jaime Carbonell
--
--
Dec. 10
Final Review Session
5 p.m. in NSH 3305
Lavie and Frederking
--
Homework #5 due (no late submissions accepted!); Solutions (PDF)
Dec. 13
FINAL EXAM
1–4 p.m. in Margaret Morrison A14
--
Sample final (PDF)
GOOD LUCK!