CMPE 250

Project 3

Due Date: 6th August

ANAGRAM AND CONNECTION FINDER

In this project you are to design an application that is capable of finding the anagrams of a given word, and that is also capable of finding a connection between two given words. This project is an implementation of Dijkstra’s algorithm for a specific task.

Project Description:

Your program will make use of an English word list, which can be found here, or can be directly downloaded from http://www.bookcase.com/library/software/msdos.education.linguistics.html in four parts. At the start the program will prompt the user for an initial letter, and the number of letters in the word. For instance, if the user inputs ‘S’ and ‘5’ your program will read only the words that start with letter S and have 5 letters from the dictionary. The program will then construct a graph from these words. Nodes of the graph will be single words and the cost of a given path will be a measure of closeness of the two words connected by the path. This closeness is defined as number of different letters of these two words. Namely, if all the letters are the same (but their order is different, like SHARE and SHEAR) the path has zero (0) cost, and both words are anagrams. If they have just one letter that is not common then this cost is one (1). For two different letters the cost is five (5) and for three different letters the cost is fifteen (15). If more letters are different, there is no path in between. The anagram finder will list all the anagrams of a given word, i.e. all the nodes that can be reached with zero cost from the given word. The connection finder will prompt for two words, and will check for the minimal cost connection between these words. If a path is found, the generated intermediate words and their costs along with the total cost will be displayed.

For example (SHARE – SHORT)

SHARE – 1 – SHORE – 1 – SHORT;

Total cost: 2

You will design a simple GUI that will do the above using simple java window components.

The initial letter is given only due to memory and time restrictions. The wordlist contains more than 100,000 words. Try your project without setting the initial letter (read all 5-letter words, not just the ones starting with S, for instance). If it is still fast enough you may also submit that.

For project report and code the same rules will be used as in the former projects. Note that you don’t have much time, therefore start this project quickly.