CPSC250A Extra Credit Assignment 1111 - Measuring Splay Tree Performance

Due Friday November 11

This is an extra credit assignemnt with two ways of comparing the performance of a splay tree to an AVL tree. You can complete either version, or both, for extra credit.

Average Case Comparison Details

For this assignment create a table that compares the execution time of the Contains function of an AVL tree and a splay tree, in the average case. Begin by creating a splay tree class. Next, create a program that that adds n random elements to a 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 an AVL tree and a splay tree, with five different tree sizes.

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.

Application Comparison Details

For this assignment compare the execution time of a spell-check application that uses an AVL tree and a splay tree to store words. Begin by creating a splay tree class. Next, create a program that reads a list of words from the text file words.txt into a tree and checks if every word in another text file is in the tree. Printing to the command line is a relatively slow operation. So, instead of printing out all of the misspelled words, the program should only print the execution time of the program at the end. Run this program on a large text file with both an AVL tree and a splay three.

Submit your code and a text file that contains the two runtimes for your program. You do not need to test your code on the cs server for this assignment.

Submission

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