CPI 220 Word Play

Big Picture:

Write a Symbol Table (ST) client that examines the performance of the following symbol table (ST) implementations: sequential search, binary search, BST, and red black BST from the algs4 library. Several text files will be provided for testing. You will construct two STs, one with

(key, value) = (word, word length) and one with (word length, word)

You will output timing and other statistics about the symbol tables. Instructions are provided in the java file in the assignment. A summary of results will be recorded in a spreadsheet along with observations.

Homework Objectives:

• Write your own search client
• Test search/ST implementations
• Practice communicating your work
• Gain experience using APIs
• Practice debugging/critical thinking, planning

Specifications

Start with WordPlay.java. See comments in this file for more guidance on completing this homework. Do not delete the given print statements, as these will be used for grading. Add the code necessary for these print statements to work.

Compare the four ST implementations by running the given text files. Document the results in the Excel file provided, complete the additional columns in the Excel file, and summarize your findings in the Analysis area provided. You should make at least three observations, each of which should be written in a professional manner.

When reading a text file, you may read the strings and leave them as they are. In other words, you do not need to extract punctuation (commas, periods, etc.), but you are welcome to do this.

No command line input allowed. Output is directed to the console.

WordPlay.java

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Out;
import edu.princeton.cs.algs4.RedBlackBST;
import edu.princeton.cs.algs4.BST;
import edu.princeton.cs.algs4.BinarySearchST;
import edu.princeton.cs.algs4.SequentialSearchST;
import edu.princeton.cs.algs4.Stopwatch;
import edu.princeton.cs.algs4.Bag;

public class WordPlay {

// Do not instantiate.
private WordPlay() {
}

public static void main(String[] args) {
StdOut.println("Hello WordPlay!");

/*
* ************************************************************************
* Choose one input file
* *************************************************************************
*/
In inputFile = new In("quickFox.txt");
//In inputFile = new In("mobydick.txt");
//In inputFile = new In("aesop.txt");
//In inputFile = new In("dickens.txt");

// create a symbol table with key as string and value as integer
// (word, length) "WL" ST

// #1
SequentialSearchST< String, Integer > WLssST = new SequentialSearchST< String, Integer >();

// #2
BinarySearchST< String, Integer > WLbsST = new BinarySearchST< String, Integer >();

// #3
BST< String, Integer > WLbstST = new BST< String, Integer >();

// #4
RedBlackBST< String, Integer > WLrbST = new RedBlackBST< String, Integer >();

// *********************************************
// Choose one of the ST implementations to use
// Numbers indicated in ST declaration
// *********************************************
int activeST = 1;

StdOut.println("activeST = " + activeST);

if (activeST < 1 || activeST > 4) {
StdOut.println("ERROR: activeST must be set to 1 - 4. Setting to 1 ");
activeST = 1;
}

switch (activeST) {
case 1:
StdOut.println("ST Implemenation: Sequential Search");
break;
case 2:
StdOut.println("ST Implemenation: Binary Search");
break;
case 3:
StdOut.println("ST Implemenation: BST");
break;
case 4:
StdOut.println("ST Implemenation: Red Black BST");
break;
}

// set the min length of words to enter into the symbol table
int minlen = 5;

// number of words read from file
int words = 0

// number of words >= minlen
int wordsMin = 0;

StdOut.println("Create a ST of (key,value) = (word, length) where length >= " + minlen);

// start timer to measure time to build (word, length) ST

// Build the WL ST (You will need a switch statement )

// report on ST construction

// Report on (word, length) ST build
// replace "dummy" with your variables
StdOut.println("Number of words read from file: " + dummy);
StdOut.println("Number of words >= min length: " + dummy);
double p1 = 100.0 * ((float) dummy / (float) dummy);
StdOut.println("Percentage of words >= min length: " + p1 + " %");

StdOut.println("Number of unique words (#keys in ST): " + dummy);
double p2 = 100 * ((float) dummy / (float) dummy);
StdOut.println("Percentage of unique words: " + p2 + " %");

// Find the minimum and maximum word in the (word, length) ST
// Report min and max word result

/* ****************************** */
/* PART 2: Create a (length, word) ST using the words and lengths in the WL ST */
// (Do not compute the word length again)
/* Called "LW" ST
/* ****************************** */
// #1

// #2

// #3

// #4

// Build the LW ST

/* Get longest word from LW ST */

// report the longest word and its length
StdOut.println("Longest word = " + longestWord + " length = " + longestWordLength);
} // end main

} // end class