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 ds2. 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 algs4.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 algs4.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 algs4 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 'it' 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 ds2.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 D2L, 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.