[SOLVED] graph ICS 46

ICS 46
Homework Assignment EX ( Replaces Lowest HW Score ) No Late Submissions
Programming Assignment
This programming assignment will consist of 4 parts:
1. Implement a self-balancing BinarySearchTree
2. Test and measure the performance of your BinarySearchTree
3. Graph the data from part 2.
4. Convert BinarySearchTree i nto a template.
1. (30 points) Implement either one of the following self-balancing binary
search trees: WAVL, AVL, Red-Black trees. Note, find will stay the same, but
insert and remove will change.
For your report Copy/Paste your code for the functions below with their O(N) (and
T(N), if not recursive) time complexities.
WAVL/AVL/Red-BlackBinarySearchTree::insert(string s,int count)
WAVL/AVL/Red-BlackBinarySearchTree::find(string s)
WAVL/AVL/Red-BlackBinarySearchTree::remove(string s)
TreeNode::insert()
int & WAVL/AVL/Red-BlackBinarySearchTree::operator[] (string s)
2. (20 points) Test and measure the performance of BinarySearchTree
Similar to Homework 5 & 6, test your BinarySearchTree implementation by testing on
two files of words.
Note: we will use both random.txt and words.txt since the tree is self-balancing,
degenerate behvaior that occurs from inserting sorted inputs should not occur, and
we would like to observe this behavior.
To test, write plain functions (not methods) (which must remove them one at a time by
making a loop over each word in the appropriate input file and calling
BinarySearchTree::remove(string)).
Execute your program, results of measuring T(N) over 10 partitions of the data for each
of your three XAllWords functions (which stands for insertAllWords, findAllWords, and
removeAllWords).
You can do this by passing in a counter, N, to XAllWords which indicates how many
words to insert, find, or remove. That function will insert, find, or remove only the first N words from random.txt/words.txt. Where you call XAllWords, you will place it in a loop with the loop control variable ranging from 1 to 10 and you will set this N parameter by multiplying the loop control variable times 1/10th of the large N which is 45,293. 1/10th of this big N is 4,529. Here is a sketch of how each will work:
Psuedocode:
For each file random.txt and words.txt:
For each partition consisting of 1/10th, 2/10,up to the full 10/10 file: Measure and report the time for:
insertAllWords findAllWords removeAllWords
Example skeleton code:

void insertAllWords(BinarySearchTree & T, int partition, char *fileName) {
// open the file, start a timer,
// insert the first partition*N/10 words into T,
// stop the timer, close the file, report the time by printing to console/cout
}
void measureAll(char *fileName) {
for (int i=1; i<=10; ++i) {BinarySearchTree T; // important to start with an empty Tree here insertAllWords(T, i, fileName);findAllWords(T, i, fileName);removeAllWords(T, i, fileName);} } You may reuse your code from the previous Homework 5 & 6 assignment if you find it helpful. However, you may not use someone else’s code or any code you find in a book or on the Internet or in my lecture slides. For your report – Include a screenshot of the valgrind execution (without memory leaks) of your programs test & measure functions. Example: File: Random.txt. Partition: 1/10. Function: insertAllWords.50s File: Random.txt. Partition: 1/10. Function: findAllWords.60s File: Random.txt. Partition: 1/10. Function: removeAllWords.40s File: Random.txt. Partition: 2/10. Function: insertAllWords.50s …3. (30 points) Graph the results of Part 2Time: Time: Time: Time: (30 pts) Graph the results of measuring T(N) over 10 partitions of the data for each of your three XAllWords functions (which stands for insertAllWords, findAllWords, and removeAllWords). Your graph should have N on the X axis and T(N) on the Y axis. Use Google Docs spreadsheet program or MS Excel or some similar program tograph your data. Here is a sample,https://docs.google.com/spreadsheet/ccc?key=0Ajv5LmqlazNHdC0xbkxtaEVGbk01ZF8xMDBZakZIRXc For your report – Include two (2) graphs for the T(N) of the XAllWords functions over the partitioned files. Do 1 graph for random.txt, and 1 graph for words.txt. Note: we will use both random.txt and words.txt – since the tree is self-balancing, degenerate behvaior that occurs from inserting sorted inputs should not occur, and we would like to observe this behavior. Example from the Google Docs spreadsheet (missing findAllWords):4. (20 points) Convert TreeNode a nd BinarySearchTree i nto a template. Convert TreeNode a nd BinarySearchTree into a template so that KeyType andElementType may be specified with different types. Run a function on words.txt only, this time counting how many words of each lengthappear – e.g., for all length of words that appear in the file. Note: The difference from Homework 6 is that we run on words.txt, and not onrandom.txt. For your report – Include a screenshot of the valgrind execution (without memory leaks)of your programs function outputting the number of words for each length. Example output: Words in words.txt of: length 1: 20 words length 2: 50 words etc…Submission Requirements1. Submit a zip of your program to EEE Dropbox. The zip file should consist of a directory named by your UCINetID containing allyour program files and a Makefile to build them.2. Submit a pdf report to Gradescope with the following format: Part 1: Code Implementation & O(N) Time complexity Analysis Five points off for each error in time complexity and for each incorrect method or function up to the maximum. Copy/Paste your code for the functions below with their O(N) (and T(N), if not recursive) time complexities. WAVL/AVL/Red-BlackBinarySearchTree::insert(string s,int count) WAVL/AVL/Red-BlackBinarySearchTree::find(string s) WAVL/AVL/Red-BlackBinarySearchTree::remove(string s) TreeNode::insert() int & WAVL/AVL/Red-BlackBinarySearchTree::operator[](string s) Part 2: Testing BST under valgrind with no memory leaks Include a screenshot of the valgrind execution (without memory leaks) of your programs test & measure functions. Part 3: Graphing the data Include two (2) graphs for the T(N) of the XAllWords functions over thepartitioned files. Do 1 graph for random.txt, and 1 graph for words.txt. Part 4: Testing TreeNode and BinarySearchTree as a template Include a screenshot of the valgrind execution (without memory leaks) of your programs functions outputting the number of words for each length. Example output: Words in words.txt of: length 1: 20 words length 2: 50 words,Homeworks that are not formatted nicely will not be accepted. Pay careful attention to memory management. Do not share memory across objects. Obvious code copying, from a textbook, from another student, or within your own program, will be down-graded (write everything once (perhaps by writing auxillary functions), then call the function or method each time that operation is required). Feel free to add additional functions or methods, but please use the data members outlined in the homework.