CS:3330:001 Algorithms Project 2: Due 3/7/2019

Computer Science is both a theoretic and experimental science. Theoretic analysis tells us whether an algorithm is efficient or not in theory. Experiments can help us to identify whether an idea is useful or not in practice. To conduct an experiment, we may learn from how a clinical trial is conducted. Basically, you need to use random examples, not to choose examples in your favour, and compare different ideas in the same environment.

In this project, we will study binary search trees. To help you get started, we provide the following java code bst.zip which contains the implementations of normal binary search tree (treeNode.java), AVL tree (avltree.java), red-black tree (redblacktree.java), and splay tree (splaytree.java). Study these codes and have them run on your computer is the first step of your project.

You are asked to complete the following tasks:

For both tasks, please give a summary of your experiments and draw conclusions from the experimental data.

Submit everything in the ICON dropbox for Project 2 before the deadline.

Thank you!