Lab #8: Searching Performance & Project Progress

Part I: Project Progress

1. Generate Project 2 test sets (.in and .data) that test at least the 
   quit, load, near, and within commands.

2. Try to implement at least the load, quit, near, and within commands for 
   Project #2.  Use SimpleSet2D instead of QuadTree (unless, of course, 
   you already have the latter implemented).  Make sure you modify your
   Makefile to include util/SimpleSet2D in the compilation.  

3. You can generate output for your test cases with part 2.  How do you
   verify that the output is correct?   

Part II: Performance of Search Structures 

SpellCheck.java contains a testing harness for various implementations
of a search structure: an unsorted array, a sorted array, a
balanced-tree implementation, and a hash table.  Read SpellCheck.java 
(and SortedArrayList.java) to see what it is doing.

4. As the program initially stands, it computes for quite a while and
   produces an output like this:

    Spell checking for sorted dictionary: 
    Implementation java.util.ArrayList took 0.00 seconds for 5 repetitions.
    Implementation SortedArrayList took  0.00 seconds for 5 repetitions.
    Implementation java.util.TreeSet took  0.00 seconds for 5 repetitions.
    Implementation java.util.HashSet took  0.00 seconds for 5 repetitions.

    Spell checking for reversed dictionary: 
    Implementation java.util.ArrayList took 0.00 seconds for 5 repetitions.
    Implementation SortedArrayList took  0.00 seconds for 5 repetitions.
    Implementation java.util.TreeSet took  0.00 seconds for 5 repetitions.
    Implementation java.util.HashSet took  0.00 seconds for 5 repetitions.

    Spell checking for randomly ordered dictionary: 
    Implementation java.util.ArrayList took 0.00 seconds for 5 repetitions.
    Implementation SortedArrayList took  0.00 seconds for 5 repetitions.
    Implementation java.util.TreeSet took  0.00 seconds for 5 repetitions.
    Implementation java.util.HashSet took  0.00 seconds for 5 repetitions.

   Modify SpellCheck.test so that the timings are real.  I suggest
   browsing through java.lang.System to figure out how.  Use the files
   ~cs61b/lib/lab8/words for the dictionary file and
   ~cs61b/lib/lab8/check for the words to check.  [What do you do with
   these files?  Figure it out!  Do NOT, however, copy them into your
   directory (unless you are working at home and have no choice.)]

5. How can you check independently that the spell checkers are producing
   correct results?   Look at the Unix utilities comm and sort.