You will write a program that given some English word finds other valid English words that have exactly the same letters. For example given the word cat the program finds the word act which is another word with the same letters. The program relies on an English dictionary to verify whether or not a string is a valid English word.

Part 1: You plan to make a set of all the words in the dictionary (all converted to lowercase). Then, given a word, you plan to make words from all the combinations of the letters and check whether each is in the set. If yes, it is a valid English word and you add it to the result. For example, for the word cat, the combinations are act, atc, cat, cta, tac, tca. act is in the dictionary and thus valid.

Analyze the runtime and memory footprint of this algorithm and give the big O. Write your brief and clear answer in the report. No code to write at all.

Part 2: After some thinking you realize that if you could somehow group dictionary words having the same letters into separate groups, then you could find all the matching words for a given word by only searching through that word's group. This approach reminds you very much of the way a hash table using separate chaining is implemented and you decide to implement this solution. The only Java API data structures you can use are arrays and java.util.LinkedList.

Hints:

Make sure you understand the problem and your approach really well before you write even

one line of code. Start by looking at the given test code. The algorithm and code you will write is not complicated, but can get complicated really fast if you are not clear about what you are doing. Make sure you understand the concept of hashing and how separate chaining was implemented.

A common problem when performing a mod operation (e.g. h % size) is when h is negative. You can handle negative results by adding size.

Test code has been given to you. Start first with some simple tests and, as you gain confidence that your code works, run all the functional tests and then the stress tests to ensure your solution is efficient.

code:

import java.util.LinkedList;

import java.util.List;

import java.util.Scanner;

/**

*

* @author ********* YOUR NAME HERE ***************

*

*/

public class Project6 {

/*

* ******************************** Part 2 ******************************

*/

// ****************** Your code here **********************

/**

* Constructs a word matcher based on the given dictionary.

*

* @param filename The dictionary file name

*/

public Project6(String filename) {

// ****************** Your code here **********************

}

/**

* Return a list of dictionary words that have the same letters as the given word.

* Differences in letter cases are ignored.

*

* @param word The word to find matches for. May or may not be in the dictionary.

*

* @return The list of matching words from the dictionary, all in lower case.

* The word itself is not included in the returned list.

* e.g.: NAME -> [amen, mane, mean]

*/

public List getMatches(String word) {

// ****************** Your code here **********************

return null;

}

public static void main(String[] args) {

/*

* You can test your methods here but I will not grade the main

*

*/

Project6 matcher = new Project6("words.txt");

// test code for functionality

String[] words = { "act", "hug", "cafe", "node", "canoe", "dusty",

"friend", "silent", "meteor", "markers", "aStewSir",

"dirtyRoom", "stampStore", "moonStarers", "theClassroom",

"accordNotInIt" };

for (String word : words) {

System.out.println(word + " -> " + matcher.getMatches(word));

}

// Stress the application to ensure it runs efficiently under load.

// All runs below should complete practically in an instant.

final int RUNS = 100000;

for (int i = 0; i <= RUNS; i++) {

matcher.getMatches("noMoreStars");

if (i % 1000 == 0) {

System.out.print(".");

}

}

System.out.println();

System.out.println("noMoreStars" + " -> "

+ matcher.getMatches("noMoreStars"));

}

}

words.txt ......file

A A's AA's AB's ABM's AC's ACTH's AI's AIDS's AM's AOL AOL's ASCII's ASL's ATM's ATP's AWOL's AZ's AZT's Aachen Aaliyah Aaliyah's Aaron Abbas Abbasid Abbott Abbott's Abby Abby's Abdul Abdul's Abe Abe's Abel Abel's Abelard Abelson Abelson's