CSC 427: Data Structures and Algorithm Analysis
Fall 2010

HW1: Prefix Matching


Many Web sites have search boxes where the user can enter a phrase and then search a collection of items (e.g., database entries, Web pages, user names) that match that name. Some of these search boxes are proactive, displaying potential matches as soon as the user starts typing. For example, if the first letter the user types is "a", then all items that start with "a" are immediately displayed. If the user then types "s", then the display list is reduced to those items that start with "as". Each subsequent character typed reduces the displayed matches. For example, the following screen shot shows a search box from Facebook, which displays the top matches for a prefix entered by the user.

For this assignment, you are to write a Java program that reads in a collection of phrases from a file and stores them in a sorted list. Then, the user should be able to enter a prefix and view all phrases that start with that prefix. You may test your program on small files, but it should run reasonably fast on potentially huge collections of phrases. To accomplish this, it should utilize two binary searches: the first to find the first phrase from the file that matches the prefix, and the second to find the last phrase. Then, all phrases between should be displayed, one per line. Matches should be case-insensitive, meaning phrases should match the prefix regardless of capitalization.

In designing your solution, you should strive to follow good object-oriented design principles. That is, each class should be highly cohesive, and interacting classes should be loosely coupled. You must demonstrate good programming style when completing this assignment, including the appropriate use of Javadoc-style comments for all classes and methods. The interface for your program is entirely up to you. It need not be fancy, but it must at least allow the user to repeatedly enter a prefix and view all matches. You may choose to use the GUI builder that comes with NetBeans if you wish.