CS 395 Assignments, Fall 2002

Assigned Friday 10/4/02. Due on paper at class time Wednesday 10/9/02.

• Create a small lexicon and a small context-free grammar containing at least the words in the sentence "Time flies like an arrow." The lexicon and grammar should support at least three different interpretations of this sentence.
• By hand, run the Earley algorithm on this sentence. Use the Peter Hellwig example from the handout as a model.
• Your completed parsing chart should contain several end points. For each end point, draw the corresponding parse tree and explain the meaning of the sentence for each tree.

Assigned Friday 10/4/02. Due Wednesday 10/16/02. Hand in via HSP.

Implement the Earley algorithm. Your implementation should accept two text files and a string as input. The text files will contain a grammar and a lexicon, respectively. The string will be a sentence to be parsed. For each valid interpretation of the sentence in the given grammar, your program will print out a parse tree, and the sentence tagged by part of speech (e.g. "They [n] study [vt] fish [n] in [prep] cans [n]").

I will specify the structure of the lexicon and grammar files in class on 10/7/02.

Assigned sometime, due by Wednesday 10/30/02. Find some sort of interesting NLP tool and prepare a 10-minute presentation about it. Examples: WordNet, the XTAG parser, the START question-answering system, etc. If possible, you should demonstrate the tool you're talking about, and describe its internal workings. Try to keep your presentation to 10 minutes or less.

Assigned Wednesday 10/30/02. Read one of the following papers:

• Pronunciation Modeling for Improved Spelling Correction, by Kristina Toutanova and Robert C. Moore.
• Similarity-based Word Sense Disambiguation, by Yael Karov and Shimon Edelman.

Come to class Monday 11/4/02 prepared to discuss the paper in detail. Proper preparation includes compiling a list of questions, working through some concrete examples by hand if relevant, thinking about the connections between this paper and larger NLP tasks, being ready to answer the questions "what is this paper about?" and "what problems does it try to solve?", etc. We will spend about half of Monday's class on each paper.

If you print these papers, please use 2-up to save paper.

Assigned Monday 10/28/02. Final project proposals due on paper or similar tangible medium, Friday 11/1/02. Ten-minute presentations will occur during our final exam period, 3:30-6:00 Saturday, 11/23/02. Source code and supporting documents will be due 11/23/02 as well.

Your final project should involve the development of some sort of NLP tool written either from scratch or by combining existing tools with your own code. We have discussed the nature of the projects in some detail in class, so I will not give examples here.

Your proposal should describe in detail what software you plan to write. If you will be using existing tools as a part of your project, identify those tools. If you have questions for me about your project, you may include them in your proposal. Your proposal should, of course, include the names of all the people who will be working on the project together (teams of up to 3 people are fine).

What you hand in will depend on your particular project, but you should certainly include source code, some sort of readme file describing your project's intent and status (what's working, what's not, what's neat, what would be good to add...), and any necessary data files. If you have collected data, provide the data and some analysis of it/them.

Have fun.