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 program’s 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 2
Time: 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 to
graph your data. Here is a sample,
https://docs.google.com/spreadsheet/ccc?key=0Ajv5LmqlazNHdC0xbkxtaEVGb
k01ZF8xMDBZakZIRXc
● 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 and
ElementType may be specified with different types.
● Run a function on words.txt only, this time counting how many words of each length
appear - 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 on
random.txt.
● For your report - Include a screenshot of the valgrind execution (without memory leaks)
of your program’s 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 Requirements
1. Submit a zip of your program to EEE Dropbox.
○ The zip file should consist of a directory named by your UCINetID containing all
your 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 program’s test & measure functions.
○ Part 3: Graphing the data
■ 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. ○ Part 4: Testing TreeNode and BinarySearchTree as a template
■ Include a screenshot of the valgrind execution (without memory leaks) of your program’s 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.