Assignment Overview
Read Aragon and Seidel's paper on randomized search trees, (available online in PDF: https://faculty.washington.edu/aragon/pubs/rst96.pdf) . This assignment uses those concepts. You will find lecture notes and discussion sections helpful as well. In this assignment you will implement the basic functionality of the Randomized Search Tree (RST). Additionally, you will write a benchmark program to understand the performance of RST, BST, and Red Black Trees.
Grab the template code from the ieng6.ucsd.edu machine at the location /home/linux/ieng6/cs100f/public/handout/PA2_handout.tar. This will include the following files:
benchtree.cpp BST.hpp BSTIterator.hpp BSTNode.hpp countint.cpp countint.hpp Makefile RST.hpp test_RST.cpp
You will modify the RST.hpp file, providing
full definitions of member functions marked with // TODO,
and turn them in. In completing the implementation, you shouldn't remove
anything from those files (except the // TODO comments!).
If design considerations dictate it, you can add
additional functions or variables, but they should be in a
private: section, indicating that those additions are
part of the implementation, and not part of
the public or protected interface to these classes.
You will additionally modify benchtree.cpp to perform the appropriate benchmarking of RST, BST, and Red Black Trees.
Due Dates
October 22 @ 8:00 PM
This means your solution to the assignment must be turned in by the due deadline. It is highly recommended that you start this assignment immediately; terminals and tutors can get very busy at the last minute. The files that contain your solution to the assignment must be turned in by the due deadline. NO EXCEPTIONS! You may develop your code anywhere, but you must ensure it compiles and runs correctly on ieng6, because that’s where we’ll be testing it. The turn-in procedure is described below in the section Turning in your assignment. Please read it carefully.
In doing this assignment, it's your responsibility to understand the course rules for integrity of scholarship.
Acquiring the Starter Files
You must follow these steps to acquire the starter code and prepare for the assignment. Copy the files from /home/linux/ieng6/cs100f/public/handout/PA2_handout.tar (cp /home/linux/ieng6/cs100f/public/handout/PA2_handout.tar . to copy into current directory) and uncompress (tar -xf PA2_handout.tar) in the appropriate location. As a review of linux command line, you can change directories using "cd" and to build the code, you can type "make" in the appropriate directory.
rst.hpp
The rst.hpp file will be used to maintain the random search tree structure and functionality.
In this assignment, you will subclass the BST class template of the previous assignment to define a class template named RST,
which implements a randomized search tree. In the file rst.hpp, you will add to the following code. Your goal will be to implement the
rotateRight and rotateLeft, and insert (your implementation of insert should call rotateRight and rotateLeft).
Since rotateRight and rotateLeft are designed to be private helper functions, you may assume that they will always be called with
valid (non-NULL) input pointer parameters as described in their method declarations below. You may implement additional helper
functions as needed. You are also provided the methods BSTinsert and findAndRotate so you can test your implementation of rotateLeft
and rotateRight before fully implementing insert - DO NOT modify these methods as they will be used by our auto-grader.
(Note that the insert function is declared 'virtual' here, and in the parent class. This means that it can be overriden, and dynamic, polymorphic, virtual function binding can happen at runtime, even when accessing a child class object via a parent class type pointer.) Read more about virtual functions and polymorphism here: http://www.cplusplus.com/doc/tutorial/polymorphism/
Many improvements on ordinary BSTs, such as AVL trees, red-black trees, or randomized search trees, can be thought of as different kinds of BSTs; here we are explicitly setting up that "is-a" relationship with public class template derivation: the class template RST inherits from the existing BST class template.
Further, these more advanced kinds of BSTs usually require some additional information to be stored in each node; for example, randomized search trees require a random priority, which can be represented as an int value. For this assignment, you will need to change the BSTNode.hpp file from PA1 to include a public integer data member (called info or priority) in the BSTNode class, which is basically the priority field required by the RST for inserting elements into the tree. Note that since this data member will be public (not protected or private), you should be able to modify it from outside the BSTNode class without having to implement "get" or "set" access functions. Be sure that your constructor for your BSTNode does not require this field, as we do not want to break your BST implementation from last week. [As an aside, it is probably better design to subclass the BSTNode to create an RSTNode, but because this addition is so small we'll save you the overhead of creating a whole new class and just add the field directly to our BSTNode class. It won't hurt the functionality of the BST anyway.]
The basic idea of the insert operation for an RST is to first insert a new BSTNode using the usual BST insert algorithm,
assign to it a randomly generated priority, and then to rotate that node up, as needed, to restore the heap ordering
property governing the priorities in the tree. Random numbers can be generated in C++ using the rand() function from the <stdlib.h> header (C's standard library).
Take a look at this article for some examples on how to call it.
benchtree.cpp
Red-black trees (which are used to implement the C++ STL std::set structure) provide guaranteed O(log N) worst case performance for add, remove, and find operations, but the add and remove operations are challenging to code correctly. Aragon and Seidel claim that randomized search trees are approximately as efficient as highly optimized red-black trees (which are much better in the worst case than ordinary binary search trees), while being much easier to implement. Here, you will investigate these claims experimentally.
Write a C++ program benchtree that permits benchmarking the performance of a RST implementation, an ordinary BST implementation, and the C++ STL std::set structure (red-black tree). Interpret "performance" to mean "how many comparisons were required to do a successful find operation, in the average case". For this you may find it convenient to create your containers to hold instances of the countint class (provided to you in your handout), which can count comparisons done on them.
Your benchtree must take the following four command line arguments. We will only test it with valid arguments, but good coding style dictates that you should check for invalid arguments and notify the user appropriately.
- the first is a string which must be either "bst", "rst", or "set", and indicates whether benchmarking should be done using a BST, RST, or std::set (respectively).
- the second is a string which must be either "sorted" or "shuffled", and indicates whether the keys inserted in the structure are inserted in sorted order, or shuffled (randomized) order.
- the third is an integer which specifies the maximum size of the container to be built in the benchmarking. Trees should be built with sizes N that are a power of 2, minus 1, in the range 1 up through this maximum size (not inclusive). This permits comparing results to the 'best possible' binary tree with size N, a completely filled tree, which will always have a size that is a power of 2, minus 1.
- the last is an integer that specifies how many runs will be done, and averaged over, for each N. If "shuffled" is specified for insertion order, then the keys should be shuffled separately for each run (not once for all runs).
You will get good, interpretable results here if you have N, the number of keys in the structure, take on values that are a power of 2, minus 1, in a range from 1 up through the maximum specified. For each N, run the number of trials specified. In each trial, create a vector of N distinct keys, for example by
Note the vector filled that way holds keys in sorted order. If it is required to insert keys in shuffled order, randomize the vector:std::vector<countint> v; v.clear(); for(int i=0; i<N; ++i) { v.push_back(i); }
And insert the keys in the vector in an empty structure of the appropriate kind:std::random_shuffle(v.begin(),v.end());
Now, find how many comparisons it takes, on average, to successfully find a key in that structure, averaging over all the possible N successful finds:std::vector<countint>::iterator vit = v.begin(); std::vector<countint>::iterator ven = v.end(); for(vit = v.begin(); vit != ven; ++vit) { s.insert(*vit); }
Note that avgcomps here is just the average number of comparisons per successful find in a structure of size N, for one particular run. Since randomness may be involved (if the keys are randomly shuffled, and/or the structure is a randomized one), it will be useful to also average over several runs (the number of runs to average over is specified on the command line). Then it will also be useful to compute the standard deviation of the measurements taken over those runs. In statistics, an often used measurement of the dispersion of a set of observations is their empirical standard deviation, which is the square root of the empirical variance. Here's a way to compute the standard deviation: You are doing R runs for a particular N. For each run i, compute the average number of comparisons for a successful find as shown above; call this ti. Now Adding up all those R times, and dividing by R, will give the overall average number of comparisons for that N:countint::clearcount(); for(vit = v.begin(); vit != ven; ++vit) { s.find(*vit); } double avgcomps = countint::getcount()/(double)N;
might print to the screen data like./benchtree rst sorted 32768 5
# Benchmarking average number of comparisons for successful find # Data structure: rst # Data: sorted # N is powers of 2, minus 1, from 1 to 32768 # Averaging over 5 runs for each N # # N avgcomps stdev 1 2 0 3 3.33333 0.365148 7 4.77143 0.714857 15 6.08 0.243676 31 8.2129 0.44726 63 10.873 1.8052 127 12.8882 0.790504 255 14.6525 0.901901 511 16.5119 0.623989 1023 19.5752 1.28953 2047 21.4011 0.735492 4095 22.0275 0.75499 8191 24.7844 1.07525 16383 26.9748 1.29925 32767 28.8381 0.546904
Detecting Memory Leaks
Memory management bugs are a potential problem in C++ programs, and it can be hard to track them down. Fortunately, tools exist that can help with this.
Two tools available in the ieng6 environment, purify and valgrind, can automatically analyze a compiled C++ program for memory leaks and other bugs such as double deletes, unitialized variables, etc. purify is (arguably) more powerful, while valgrind is (arguably) easier to use. Manual pages and tutorials for these tools exist online. Here is just one easy way to use valgrind. Suppose you have a compiled C++ executable program foo in the current working directory. Then running
will run foo, printing the results of the checks valgrind did. If foo was compiled using the -g flag to g++, valgrind will be able to print the line numbers of statements that are involved in bugs that it has found. If want to see more detailed information about memory leaks, runvalgrind ./foo
The output from valgrind's analysis can be lengthy, and especially if the program foo is also printing to the terminal, it can be hard to read. Running it asvalgrind --leak-check=full ./foo
will write valgrind's output to the file out instead of to the terminal screen, and you can then read the file in an editor, or search in it with grep.valgrind --log-file=out ./foo
Testing
You are responsible for testing that your code is correct before the final deadline. We provide an example program, test_RST.cpp, that does some BARE BONES tests of RST::rotateLeft, RST::rotateRight, and RST::insert. You should extend these tests to be more comprehensive as will be sure to check all edge cases during grading. To compile the tester executable, run:
make tester
Reference implementation for the benchtree is available at /home/linux/ieng6/cs100f/public/bin/benchtree_gold . You can execute this specific reference binary to see if the format of the output matches your binary. The seed for the randomization is set to 0. You will need to see if the outputs differ between your binary and the reference binary. To save the stdout for a binary you can do "./benchtree > myresult.out" and for the reference "./benchtree_gold > reference.out". To diff the output, you can use "diff myresult.out reference.out".
Turning in your assignment
When you have completed the assignment, you must submit it. One thing you must add to identify yourself and who you worked with, you must have a file called student_numbers.txt that contains student numbers one per line with UNIX style endings. Now you will do this in two steps. We have created a turnin prep script that checks to make sure your code builds with our makefiles and passes some sanity checks.
- Execute the turnin prep script "python /home/linux/ieng6/cs100f/public/bin/PA2_turnin_prep.py" in the folder where your source files are. This will create a tar archive of your turnin files and also give you feedback on building and sanity checks. If there are any errors you will be notified.
- Actually turnin your code. Use the turnin command on the tar archive. e.g. turnin -c cs100f PA2_<username>.tar.
Some points to keep in mind:
- If you are submitting with a partner, only perform one submission with both of your student IDs in the student_numbers.txt file. Do not submit multiple turnins under different accounts with the same student identification numbers. If you do this accidentally, email Ming (miw023@ucsd.edu) immediately with the submission account name that you wish to have removed. Failure to do so can result in a 0 on the assignment. If you accidentally do this too often it will result in Ming being ridiculously grumpy which will likely also lower your grade.
Grading
There are 22 possible points on the assignment. If your solution files do not compile and link error-free, you will receive 0 points for this assignment. We will compile and test your program using the g++ compiler and runtime environment on ieng6.
Grading will occur twice. One will happen 2 days prior to the turnin deadline in order to give you an idea of the grade on your assignment. The final grading will occur directly after the submission deadline closes.