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!