Homework 6: Binary Search Trees

Due November 18 @ 8:00pm on Autolab

1. Introduction

In this assignment, you’ll be writing the code for a binary search tree. It will be based on the tree that we construct and deal with in class. (So, it is ok to copy-and-paste code from our class demo code into your assignment.)

Download a pre-prepared Eclipse Project hw6.zip and import it into Eclipse using these instructions. You will make all of your changes inside of the Java files in this project.

2. Your Tasks

You have two main tasks.

  1. Finish the KeyValueBinarySearchTree implementation with all of the requested methods.
  2. Write the AnagramTree class that can be used to find anagrams from a dictionary.

2.1. Finishing KeyValueBinarySearchTree

Fill in all of the empty methods in KeyValueBinarySearchTree.java. They are documented inside of the file.

2.2. Building the AnagramTree

You’re going to write an anagram finder, AnagramTree. (If you don’t know what an anagram is, try Wikipedia on the subject.)

The AnagramTree will make use of the KeyValueBinarySearchTree class to store lists of anagrams. At a high-level, it will read in a file of words (one per line) and store them in a binary tree using their sorted letters as the search key. What does this mean? When you read a word from the file (a String), you must sort it (by creating another, sorted, String that has all the letters of the original word in sorted order) and then insert the original word into the tree using the sorted word as the key. The sorted word (a String) will be the search key for the binary search tree, and all the words that have the same sorted form (like “rats” and “tars” and “arts”) will all be stored in an ArrayList at the node with the sorted word key (in this case, with key “arst”).

The AnagramTree method loadWords takes a file name and maximum word size and builds a tree with all the words that are less than or equal to the length specified. To do this, you read words from a file one line at a time, and for each word if it is the correct length then construct its sorted form and add the original word into your tree, using the sorted form as the key. (Remember: The key finds the node, and the node contains an ArrayList of words that are anagrams of the sorted key.)

If you use the small file and a maximum word size of 7, you should have 16 words in 9 nodes in the tree. If you use the big file with a maximum word size of 7, you should have 51913 words in 41121 nodes. (Or, with a maximum word size of 8, 80314 words in 66538 nodes.)

We have provided some simple driver code in AnagramTester.java that should use your AnagramTree class. Your code must be compatible with this tester as provided.

3. Grading and Submission

There are multiple parts of the grading of this assignment:

  1. For the first 90 points, your submission will be auto-graded on Autolab based on your implementation of KeyValueBinarySearchTree and AnagramTree.
  2. For the next 5 points, your submission will be manually graded to check for good implementation methodologies. (Did you use a good approach to solving the problems?)
  3. For the next 5 points, your submission will be manually graded to check for good testcases that you include in the main method. (Do you have 2-3 basic testcases for each method, and do they all execute automatically?)
  4. Your code will also be checked for style. The parts of style that can be checked automatically (things like spacing, indentation, the use of CamelCase, etc.) are automatically checked by the autograder. Other parts of style, such as choosing good variable names, will be checked manually. Autograded style guide violations can result in, at most, -10 points. Manually checked style guide violations can result in, at most, -5 points.

You will submit your program to Autolab. Login to the system and you will see the homework.

For this homework you’ll need to submit a zip file containing your code. Lucky for you, however, Eclipse can create this zip file for you. Check out these instructions. On Autolab, you’ll submit that exported zip file. On the page that follows your submission you will see your live score (out of 90). It may take up to a few minutes for your score to appear, during that time just hit refresh in your browser. If you receive a lower score than you expect, you can click on the score to see the feedback from the autograder.

For this assignment you have 15 submissions. Use them wisely.

3.1. Testcases

In this homework we are not providing any testcases.

For KeyValueBinarySearchTree you need to provide at least three testcases for each of the new methods. At least one of those three must be non-basic. All of your testcases should be in the KeyValueBinarySearchTree class included with the skeleton code.

For AnagramTree you need to provide at least three complete testcases that demonstrate overall functionality. (And, of course, we expect that you will also be testing manually using the AnagramTester).

You must follow the model of our testcases (meaning you print when you start, print when you finish, etc.) Additionally, you must comment each testcase with a note describing what it tests.

When grading, in addition to counting testcases we will also look at the quality of what you are testing.

4. Restrictions

You may only use the following Java libraries in this assignment:

java.util.ArrayList
java.util.Scanner
java.io.FileReader
java.util.Arrays

5. Important Notes