15-200 Fall 2006

Homework Assignment 7

Anagrams

Program Due: Monday Nov. 20, 2006 at 11:59pm


Overview:

An anagram is a word or phrase formed by reordering the letters of another word or phrase, such as beard to bread. Here is a list of words such that the words on each line are anagrams of each other:

bared beard bread debar debra
abel able bale bela elba
bares baser bears braes saber
abets baste bates beast beats
caster caters crates reacts recast traces
caret cater crate react recta trace

In this program you will get a word from the user, and search a given dictionary to list all possible anagrams of the user entry. If there are no corresponding anagrams, an appropriate message is displayed.


Objectives:


Part I Instructions:

In order to find all possible anagrams, you convert the user input word and every dictionary word into a Word object. The Word object contains its standard representation, as well as a sorted representation. For example, the user word star will be made into a Word object that contains the standard representation star as well as its sorted representation, arst.

The algorithm for this problem is to take every dictionary word, convert it into a Word object and insert it into a binary tree. The dictionary is a binary tree of all the sorted representations of the words in the dictionary. The node for each element in the binary tree will have its sorted representation, and a list all words in the dictionary that have that sorted representation, i.e. anagrams. You can use any collection classes of Java's API for storing anagrams in the node.

You are to implement

Part II Instructions:

In this section of the lab, you will get all anagrams of length >1 for your given word. That is, as you traverse down the tree, you will return the anagrams at each node all the way from the level one below the root to the given word. Unlike some data structures where this would involve deleting extraneous information, the unique invariant of BSTs (that anything to the left of a node is less than it and anything to the right is greater than it) means that as long as you traverse the tree correctly, you will never encounter incorrect information

Part III (Extra Credit) Instructions:

Like linked lists, binary search trees are unidirectional data structures. However, as with doubly linked lists, there is a way to make BSTs that can go up the tree as well as down. This can be accomplished by adding an additional pointer to each node that points up to the parent of the current node. In this extra credit, you will implement a method to traverse and print a path between one node and another node using a bi-directional tree.

The way to go about this is as follows: traverse the standard BST down to the first given node. Once at that node, print the word value (the sorted word). Then, determine the correct direction to move: left, right, or up. It is important to remember that the value of the parent node will be greater or less than the current node depending on whether you are to the right or left of the parent. If you are to the left of the parent, the right child of the current node will be greater in value than the current node and less than the parent node. Thus if the value to be found is between the current node value and the value of the parent, traverse right, but if it is greater than the value of the parent, traverse up. Obviously if you are on the left and the value to find is less than the current value, traverse left as normal. Do the opposite thing if you are to the right of the parent. (Left or right can be determined by comparing the parent and current node values)

For example, in this tree (rotated 90 degrees):
     dog
   cat
     boo
bat
     az
   as
     aa
To go from aa -> boo, traverse down to aa and print 'aa'. Compare 'aa' to 'as' so you are in a left subtree, and compare 'as' to 'boo'. Since 'boo' is greater than 'as', traverse up. Print 'as'. Compare 'as' to 'bat' so find the subtree and compare 'bat' to 'boo'. 'boo' is greater than 'bat', so traverse up. Print 'bat'. See that 'bat' is the root of the tree, so compare 'boo' to 'bat' and traverse right. Print 'cat'. Compare 'boo' to 'cat' and traverse left. Print 'boo' and exit.

Output: aa as bat cat boo

If you plan to do the extra credit, you should use the commented out constructor for the tree node class rather than the default constructor. If you are not sure whether you will do the extra credit, it is recommended that you build your tree with parent nodes from the start. That way, your code will function the same if you choose not to do the extra credit, and if you do choose to do it, you only have to write the method rather than redoing your tree.
NOTE: If one or both of the words are not in the tree, you should not print anything (that is, do not print in-method) since you will not know if the second node exists until you reach it.


What You'll Need:

Create a private directory for your work, download the file lab.zip into it, and then unzip it. You should see the following files:


Grading:

Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether requirements were satisfied, as well as judge the overall style of your code. Programs will be graded both on correctness as well as the style. Points will be deducted for poor design decisions and un-commented, or un-readable code as determined by your TA.

Here is the point breakdown:


Handing in your Solution:

FTP your implementation to /afs/andrew.cmu.edu/course/15/200/www/handin