This project is due Sunday, October 29th at 2359

• Max Grade: 70% (optional before doing a higher max grade)
  • Complete an O(n) or greater Map data structure (e.g., a BST) and use it complete Board.java
• Max Grade: 90% (required before doing a higher max grade)
  • Complete an O(log n) AVL implementation of a Map and use it complete Board.java
• Max Grade: 100%
  • Use another data structure (e.g., an HashTable or something else!) implementation of a Map and use it to complete Board.java. You must describe your datastructure solution in your README file

Partial credit and deductions will be provided based on quality of work. If you complete the AVL, you do not need to use another O(n) performance Map, to receive credit in the AVL category; however, before moving on an attempting another data structure, you must have completed the AVL first. And, of course, you must fully complete the interface with all methods working as expected

Generally, the following grading criteria will be applied:

• Accuracy: E.g., Are all set keys present and return consistent answers?
• Performance: E.g., How fast does get and set run?

Speed competition between students:

• +2 Points: Fastest submission in your section (plus a mystery prize!)
• +3 Points: Fastest submission across all sections (plus a double mystery prize!)

Speed competion with instructors:

• +3 Points: Submission is faster than Dr. Aviv's AVL solution!
• +2 Points: Submission is faster than Dr. Aviv's fastest solution!

It is possible to not be the fastest in your section (or across sections) and still produce a solution faster than Dr. Aviv's.

You can run Dr. Aviv's solution for the java OnePlayer 0 execution on a lab machine with the following commands.

~aviv/ic312-proj/avl

~aviv/ic312-proj/fastest

As a guide for improving your code, you should try running your code with -Xprof option, e.g.,

java -Xprof OnePlayer

which will print out performance statistics about which part of your code is the slowest.

All starter code for this project can be obtained via the ~aviv/bin/ic312-up and submission will occur via ~aviv/bin/ic312-submit.

You must submit the following edited file(s):

• Board.java
• ic312/AVL.java
• README : Containing any attributions or notes for grading

For your additional data structure, place this in the ic312 package directory properly labeled. You must describe your data structure in your README.

DO NOT submit non-compiling code.

You Board.java Submission should include the fastest implementation you developed. Non-compiling Board.java files will not be graded.

The following files will be provided for you to complete the project and you should not edit them:

• output0.txt : sample run of java OnePlayer 0
• output10.txt : sample run of java OnePlayer 10
• american-english : english language dictionary file
• TwoPlayer.java : Two player Boggle game
• OnePlayer.java : Single player Boggle game

The following ic312 data structure package files are also provided for you and should not need to edit them:

• ic312/List.java
• ic312/Queue.java
• ic312/Stack.java
• ic312/Map.java
• ic312/LinkedList.java
• ic312/ArrayList.java
• ic312/CircularArrayList.java
• ic312/Pair.java

You will be required to complete an AVL datastructure that implements the Map inteface, as defined in ic312/Map.java. Once completed, you may implement a second data structure, to be placed in the base directory of the submission.

The follow files are provided for you to use and retrievable via ic312-up:

• american-english
• Board.java
• TwoPlayers.java
• OnePlayer.java

american-english is a text file consisting of every word in the English dictionary which uses the standard 26 letters (no accented letters). There are 64,117 words in this document.

Board.java is where a lot of the magic happens. Places that need your attention are labeled with TODO.

• A Board instance has three class variables; a 2-dimensional char array (for encoding the dice rolls), an instance of a Map<String,Boolean> data structure englishWords (for holding every word in the English dictionary), and a random number generator (for rolling the dice before you start).
• There are two constructors, one of which takes a seed for the random number generator, and one which does not. The one that accepts a seed makes debugging easier, as you'll get the same Boggle board every time as long as you use the same seed. Both constructors call two functions to set up the game:
• initDictionary() reads every word from the file american-english and adds it to englishWords. You have one line to repair so it builds your data structure.
• initBoard() handles the rolling and placement of the dice, based on the actual dice that come with a game of Boggle. When it is done running, the field board is filled with chars. You don't have to do anything for this.
• toString() is a toString. It's used when printing the Board, and uses fancy unicode characters to draw a box around it. You don't have to do anything for this.
• static countPoints(List<String> l) takes a List full of Strings, and returns the number of points that word list gets in Boggle. You don't have to do anything for this.
• List<String> allWords() returns a List full of all words that appear in this game of Boggle. It requires a lot of work. First, it creates a 2-D boolean array called used. Remember how a given word may only use each die once? This array encodes which die have been used. It starts as all false. Second, you'll build an instance of your data structure called foundWords to hold all the words that you find. Then, for each possible row and column combination, you'll call the recursive helper method.
• void allWords(String sofar, int row, int col, boolean[][] used, Map<String,Boolean> foundWords) is the recursive helper method to do the heavy lifting. The String is the word as built so far. row and col are the row and column we're currently on. used encodes which dice have been used already, and foundWords is there to get filled when we encounter actual English words. Obviously you'll want to change the type of foundWords to be your data structure. In order to speed things up, go ahead and assume no words exist longer than 8 letters. If your final product is fast enough, perhaps you'll be able to take that restriction off (my solution doesn't have it).

TwoPlayers.java is already written to allow you to play against the computer; you just have to set the type of your data at one or two spots. This is fun when you've finished, to see how badly you're beaten by the computer (very badly).

OnePlayer.java is a main method used to see what words the program found in the board. This also does the timing that we'll use for the contest.

Please thoroughly comment your data structure, so it is easy for me to understand. Additionally, please comment the method allWords() in Board.java.

In attacking this project, I recommend starting with a BST, even if you have grander designs. So, make the BST, and make sure the methods it needs have work. Then work on the Boggle algorithm. Once that works with a BST, then you can swap in different data structures.

Don't forget that Q is automatically followed by a 'U.'

The project must be written in Java.

If you find yourself getting a StackOverflowError, there are two possible reasons for this. One, you have infinite recursion taking place. Two, your data structure isn't great, and it's just gotten too tall. You can increase the size of the stack allowed by Java by using the -Xss flag. The following runs OnePlayer with 2MB of stack space:

java -Xss2m OnePlayer