CPSC250A Assignment 1110 - Measuring A-B Tree Performance

Due Wednesday November 9


For this assignment create a table that compares the execution time of the Contains function of a 2-3 tree and an a-b tree, optimized for memory page size, for trees of various sizes. You should write a program that adds n random elements to an a-b tree, repeatedly calls the Contains function, and prints the total ammount of execution time for all of the Contains function calls. Run this program with both a 2-3 tree and an a-b tree, where a is specified such that a node of the a-b tree is the same number of bytes as a page of memory. Also run this program with five different tree sizes. One tree size that is approximately equivalent to the swap space, two trees that are larger than the swap space, and two that are smaller than the swap space. The size of these five trees should be equally spaced from each other.
In order to write the program and generate the test cases you will need the following:

The file size_ex.cc contains a program that demonstrates all of the above.
Submit your code and a text file that contains the ten runtimes for your program. You do not need to test your code on the cs server for this assignment.

Extra Credit

Write a java program that draws a line graph of your run-time tables.


Tar your code in a file that contains your name and submit it on course Inquire site.