Difference between revisions of "CISC220 F2014 Project1"

Latest revision as of 10:25, 18 January 2017

1. Binary Search Tree (BST) implementation

Write two versions of a templatized binary search tree class BSTree_Fast and BSTree_Slow (details below). For each version you should define the following THREE member functions: insert(), contains(), and findMax(). Both classes will use the templatized class BSTNode to store an inserted element. When an element (aka key) is inserted more than once, there should not be multiple BSTNodes created, but rather the number member variable of the original BSTNode should be incremented.

Starter code is provided here

• BSTree_Fast
  • Implement the BST using a traditional pointer-based linked structure as detailed in Chap. 6.2 of the textbook. BSTree_Fast should also keep track of its maximum depth; make sure to update this with every insert().
  • Write a member function print() which does the following:
    • Prints to cout every key from smallest to largest, with the number of occurrences of each also printed, using a recursive, in-order traversal of the BST
    • Prints a count of how many unique words there are
    • Prints how many words total there are
    • Prints the maximum depth of the tree.
• BSTree_Slow
  • Implement the BST using an unordered STL vector of pointers to BSTNodes (the left and right pointer variables of each node will be NULL and unused). Do not attempt to keep things organized: contains() should be a simple loop through the vector, insert() should just be push_back() if this is the first occurrence of the key, and so on. Note that this NOT the same as representing a binary tree's structure with an array as described in lecture and Chap. 6.2 of the textbook.
  • Write a member function print() which does the same as above, except the words should just be printed in the order they are stored in the vector, and there is no depth to print.

2. BST testing and comparison

Write a driver function which creates and fills a separate BSTree_Fast and BSTree_Slow of C++ strings for each of the following files by reading from them word-by-word and calling insert() repeatedly. Note that all of these files have been "cleaned" (punctuation removed, all lower-case).

• DOI (about 1K total words)
• BTS (~14K words)
• GE (~185K words)

In your README PDF, answer the following questions for each file using the information from print() or your own custom functions. Your BSTree_Fast and BSTree_Slow should give the same answers for the first three questions

• How many unique words are there?
• How many different words total are there?
• What is the alphabetically last word?
• What is the maximum depth of the BSTree_Fast generated?

How long does it takes for BSTree_Fast vs. BSTree_Slow to carry out the following FIVE operations for each of the three input files? (To get precise timing under Unix, use the gettimeofday() function. There is a code snippet under the Unix, Linux and Mac section here that should help.)

• Create the BST
• Search for each of these words with contains():
  • love
  • death
  • tyranny
• Find the alphabetically last word with findMax()

3. Submission

• Include a PDF file <Your Name>_README.pdf which contains:
  • Answers to the questions above. Do NOT include the full listing from your print() functions. However, a call to print() for both versions of the BST should be in your driver code.
  • The timing measurements requested, in a nicely-formatted table, as well as comments on why you think the timings vary for the different (1) BST implementations, (2) operations being performed, and (3) files from which the BSTs were created.
• Rename your code directory <Your Last Name>_Project1 and create a single tar/zip/rar file out of it named <Your Last Name>_Project1.tar (or .zip or .rar, etc.).
• Submit it in Sakai by midnight at the end of Thursday, October 2