CS-2852 Data Structures
Exercise: Wordsearch revisited

In this lab, you will modify the Java code of your Wordsearch application (from lab 6) to use the JCF binary tree and hashtable classes (TreeSet and HashSet) to store the dictionary, and examine the time taken by your application when using these data structures.
 
Details
  1. In the WordSearchApp.java file, make the necessary modifications such that the dictionary is loaded into a TreeSet. Note: it is not necessary to change the type of container that is used to hold the found words.

    If you previously called any List methods through the dictionary reference, you'll have to modify this code, since List methods are not supported by TreeSet or HashSet. Consult your instructor if you encounter difficulties.

    When you complete this change, run the program and record the time taken for the following cases:

  1. Next, change the type declaration such that the dictionary is declared to be a HashSet. Repeat the tests and record the times for the following cases:
    • the time to do a 4-way search on the 8x8 grid using a HashSet to store the words in the dictionary
    • the time to do a 8-way search on the 4x4 grid using a HashSet to store the words in the dictionary

Demonstration

You must demonstrate and submit your modified Word Search application before the end of lab.

Note: Performing a 4-way search on a 4x4 grid requires 27, 396 iterations if you limit word size to 3 to 15 characters. An 8-way search, on the other hand, requires 11,686,356 iterations. A 4-way search on an 8x8 grid requires about 30,508,688 iterations. On my PC, it takes about 35 seconds to perform this many recursive iterations without doing the actual searching.

After final exams are over and you have the entire summer to think about how smart you've become after taking CS2852 (be sure to remind your parents of this), you may want to try putting your computer to work doing an 8-way search on the 8x8 grid. Be aware that, in this case, it takes about 653,533,924,480 iterations.

Submit your java files containing the modifications from part 2 to Blackboard.