Programming Assignment #3 Solution

Filenames: authors.csv, BSTX.cpp, and BST2.h.




Format of authors.csv: author1_emai,author1_last_name,author1_first_name author2_email,author2_last_name,author2_first_name




#1 (40 points) I have written an extended version of the timetest.cpp from programming assignment #1, called timetest3.cpp. Both the source code, and PC executable are available in ~ssdavis/60/p3. I have also made the data files five times larger than in P1, i.e., 2.5 million operations instead of 500,000. For this question, you are to write an extensive paper (4-7 pages typed double spaced and no more, not including the tables) that compares the performance of eight new ADTs and SkipList for the four files, File1.dat, File2.dat, File3.dat, and File4.dat. You need to run each new ADT only once on each file. If an ADT does not finish within five minutes, then note that and kill the program. For BTree try M =




3 with L = 1; M = 3 with L = 200; M = 1000 with L = 2; and M = 1000 with L = 200. For the Quadratic Probing Hash try load factors of 2, 1, 0.5, 0.25, and 0.1. For the Separate Chaining Hash try load factors of 0.5, 1, 10, 100, and 1000. To set the load factor for hash tables in timetest3, you supply the size of the original table. For example, for File1.dat to have a load factor of 5 you would enter 2,500,000 / 5 = 500000 for the table size.




Each person must write and TYPE their own paper. There is to be NO group work on this paper. There are two ways to organize your paper. One way is by dealing with the results from each file separately: 1) File1.dat, 2) File2.dat,




File3.dat, 4) File4.dat, and 5) File2.dat vs. File3.dat. If there are differences between how a specific ADT performs on File2.dat and File3.dat explain the differences in the last section. The other way is to deal with each ADT separately.



In any case, make sure you compare the trees (including the BTree using M = 3 with L = 1) to each other and to skip list. For BTrees, explain the performance in terms of M and L. You should also compare the hash tables to each other somewhere in your paper. For the hashing ADTs, you should also discuss the affects of different load factors on their performance with each file. Compare the performance of the Quadratic Probing hash with QuadraticProbingPtr in a separate paragraph. You should determine the big-O’s for each ADT for each file; this should include five big-O values:




individual insertion; 2) individual deletion; 3) entire series of insertions; 4) entire series of deletions; and 5) entire file. Use table(s) to provide the run times and the big-O's.



Do not waste space saying what happened. The tables show that. Spend your time explaining what caused the times that were they were relative to each other. Always try to explain any anomalies you come upon. For example, for most ADTs, you should clearly explain why there are different times for the three deleting files. While a quick sentence explaining the source of a big-O is enough for ADT-File combinations that perform as expected, you should devote more space to the unexpected values.




Five points of your grade will be based on grammar and style. If you use Microsoft Word, go to the menu Tools:Options:Spelling &Grammar:Writing Style and set it to Formal. This setting will catch almost all errors, including the use of passive voice.




(1.5 hours, 10 points) Given the recursive nature of a binary tree, a good strategy for writing a C++ function that operates on a binary tree is often first to write a recursive definition of the task. For example, suppose that the task is to count the number of nodes in a binary tree. An appropriate recursive definition for the number of nodes C(T) of a binary tree T is:



0 if T is the empty tree

C(T) = C(left subtree of T) + C(right subtree of T) + 1 otherwise.




Given such a recursive definition, a C++ implementation is often straightforward.




Each team should implement the definitions in C++. For simplicity, assume that a tree data item is a single integer and that there are no duplicates. I've included two files in my p3 subdirectory that will provide you a starting point: BSTX.cpp, and BSTX.h. You should not need to change BSTX.h. You will need to add the appropriate functions definitions to the bottom of BSTX.cpp. You need to handin only BSTX.cpp.




I've included BSTXtest.cpp in the p3 subdirectory that will test your implementation.




Computer the height of a tree. int height() const
Find the sum of the elements. int sum() const



Determine whether one item is an ancestor of another (that is, whether one item is in the subtree rooted at the other item). bool isAncestor(const Object x, const Object possibleAncestor) const
Determine the height of the deepest level that is full or, equivalently, has the maximum number of nodes for that level. int highestFull() const.



Determine the depth of the deepest level that is full or, equivalently, has the maximum number of nodes for that level. int deepestFull() const.



[ssdavis@lect1 private]$ g++ -o BSTX.out BSTXtest.cpp [ssdavis@lect1 private]$ cat BSTXtest.cpp




#include <iostream




#include "BSTX.h"

using namespace std;




/*
The tree


















10












5


15








0
6
12
20
// full level
-5
2
8
14
16
22






4


18




24











26




*/




int main()




{

int i;

BinarySearchTreeX<int tree(-1);




for(i = 10; i <= 20; i += 5)




{

tree.insert(i);

tree.insert(15 - i);

}

for(i = 2; i < 28; i += 2)




if(i % 5 != 0)

tree.insert(i);




cout << "Height: " << tree.height() << endl;

cout << "Sum: " << tree.sum() << endl;




if(tree.isAncestor(4,5))

cout << "5 is an ancestor of 4\n";

else

cout << "5 is not an ancestor of 4\n";




if(tree.isAncestor(5,4))

cout << "4 is an ancestor of 5\n";

else

cout << "4 is not an ancestor of 5\n";




cout << "Highest Full: " << tree.highestFull() << endl; cout << "Deepest Full: " << tree.deepestFull() << endl; return 0;




} // main())




[ssdavis@lect1 private]$ BSTX.out

Height: 5

Sum: 197

5 is an ancestor of 4

4 is not an ancestor of 5




Highest Full: 3

Deepest Full: 2

[ssdavis@lect1 private]$