We discussed in class that different implementations of an abstract data type may

result in very different performance. You will test three symbol table

implementations taught $($or will be taught$)$ in the class by writing a program $($i$.$e$.,$

java class$)$ called TimeSymbolTables in the package ds$2.$ This program should

create three symbol tables, each of a different implementation. Each symbol table

will contain as the key a word read from the input file and as the value the

number of times that word occurs. For each symbol table object, the program will

fill it with the word counts and keeps track of how long that takes using

the algs$4.$Stopwatch class $($see page $174$ of the book for how to use the class$).$

After filling each table, the program should print out the time elapsed as

determined by the algs$4.$Stopwatch.

The program should consist of the following steps:

$1.$ Create a String array of the words read from a file $($details will be given

later$).$

$2.$ Create three symbol table objects using the following classes found in the

algs$4$ package:

$$ SequentialSearchST $($this is the implementation of linked$-$list$-$based

symbol table$)$

$$ BinarySearchST $($this is the implementation of the symbol table

based on doing a binary search on ordered arrays$)$

$$ BST $($this is the implementation of the symbol table based on binary

search trees; you may not have learned it yet but this doesn$$t prevent

you from finishing this assignment as it supports the same methods

as the previous two$)$

$3.$ Write a loop for each of the symbol table objects in which the code iterates

through the String array created in Step $1,$ adding to and updating the word

counts in the symbol table. Just before each loop, create

a Stopwatch object. Just after the bottom of each loop, use

the elapsedTime$()$ method to get and print the amount of time the loop

takes.

$4.$ Output the times that the word $$it$$ occurs in the file, i$.$e$.,$ output the

frequency of the word $$it$$ as recorded in an arbitrary one of the three

symbol tables $($the frequencies in all the three symbol tables should be the

same$).$

You should format the output like the following:

SequentialSearchST: X seconds

BinarySearchST: Y seconds

BST: Z seconds

The word $\text{'}$it$\text{'}$ occurs W times

Reading input from file

The words should be read from a file and the file name is specified as an

argument from the command line. For example, in order to read the words from a

file named $$data$/$tinyTale$.$txt$,$ one may run your program from command line as

follows:

java ds$2.$Balanced data$/$tinyTale$.$txt

To read the words from the file, you should add the following two lines at the

start of your main function:

In in $=$ new In$($args$[0])$;

String$[]$ a $=$ in$.$readAllStrings$()$;

After that, you will go over each string in the array and do as specified.

Notice: On D$2$L$,$ there is a document $($Contents $->$ Misc $->$ Eclipse$-$programarguments$)$ about running your program from Eclipse while also specifying a file

path. This way, you can use the debugging features $($e$.$g$.,$ set breakpoints and

inspect variables$)$ provided by Eclipse.

Additional tips

$$ You can test your program on the text files such as data$/$tinyTale$.$txt

or data$/$tale$.$txt already provided. You should see differences in the times.

Notice that when grading your program, a similar but different text file will

be used.

Submission instructions

$$ Make sure that the program is in the ds$2$ package and that your name appears

in comments at the top of the program. Submit only the

TimeSymbolTables.java file into the D$2$L slot provided.

$$ You must use the algs$4.$In class in for input and the algs$4.$StdOut class for

output. Do NOT use the Scanner or File Java classes for input. Do NOT use

System.out for output.