CPSC250A Assignment 1110 - Measuring A-B Tree Performance

Due Wednesday November 9

Details

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:

• In order to get the ram and swap size in bytes on linux, include sys/sysinfo.h and use sysinfo.
• In order to get the size of a primitive data type in C++, use sizeof(type).
• In order to get the memory page size on Linux, include unistd.h and use getpagesize().
• In order to get execution time on Linux, include time.h and use clock_gettime. Note in order to link a program that uses this function you need to add the option -lrt to the end of your g++ link command.

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.

Submission

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