CS 378

CS 378

Natural Language Processing
Fall, 2003

Homework 2

Due Tuesday, Sept. 16 at 3:30

You are welcome (in fact encouraged) to work in teams to solve these problems. But each person should write up his/her solutions separately.

1) Trace the operation of the Boyer Moore string search algorithm on the following data:

Pattern to be found: corporation

Text to be searched: This nation has witnessed the rise and then the fall of some of the greatest corporations in history.

2) J & M problem 2.1, parts d, e, and f.

3) J & M problem 2.4.

4) J & M problem 3.4.

5) J & M problem 3.6 presents the Soundex algorithm, which defines an equivalence relation on the set of names. Try your name and several of your friends' names. What equivalence classes does the algorithm induce?