Project #5 (Binary Search Trees)
Due Date: Friday Nov 4, 6:00 pm
Object-Oriented Programming II
Type of Homework: Closed
This homework has several objectives. Those objectives are:
Practice binary search trees and linked lists.
Practice writing test cases
Practice performance analysis
This homework is considered a closed homework. Make sure you read the Open/Closed policy before continuing working on this project.
For this project you will complete the following tasks:
Your project will be graded as follows:
Tests (65 %)
Public JUnit tests (32 %)
Release JUnit tests (33 %)
Performance Report (25 %)
Style (10 %)
For this project:
We encourage you to start working on this project as soon as possible as there are a lot of details that can not be completely specified in this description. You should address these doubts ahead of time during lab session, or office hours. We encourage you to work every day on this project (even for a couple of minutes). This will allow you to submit this project on time.
Even if you are not planning to work on the project for a while make sure that:
You can compile a simple class using the provided code distribution. If you have problems compiling a simple class, see your TA immediately.
Submit your project using the "Submit Project" option in Eclipse and verify your submission has been received in the submit server. It is important that you submit your project using the "Submit Project" option rather than uploading a jar file to the submit server. If you are having problems with this submission process, contact your TA or instructor immediately.
You must debug your code using the Eclipse debugger and should not use "System.out.println" as a debug tool. TAs in office hours will require you to use the debugger to show any problems you are experiencing.
To make sure that you are not "bypassing" some of the goals of the project, you must abide by the following restrictions in your project implementation. However you do NOT have to abide by these restrictions while writing your own test cases.
You may not use any form of looping construct for the implementation of Tree classes.
You may not use arrays.
You may not use any classes from Java.util, or similar collections classes.
You may not use instanceof.
You may not add any non-private methods or fields.
The TAs have been instructed not to help you debug your code unless you have written a test case that demonstrates that your project is malfunctioning. You should be writing and using your test cases WHILE you are implementing the project, not as an afterthought at the very end. Testing and software development go hand-in-hand.
Much of the documentation for this project is contained in "JavaDoc" in the project files themselves. This documentation can be found in the .java files or in Project JavaDoc.
For this project you will implement a "polymorphic" binary search tree. We say the binary search tree is polymorphic because there will be two types of Trees: EmptyTrees and NonEmptyTrees. An empty tree contains no fields. A non-empty tree has four fields:
Comparable key value
reference to left child (Tree)
reference to right child (Tree)
If a non-empty tree has no left or right child, then instead of having it's left/right reference refer to null, we will have them refer to an EmptyTree. So both the left and right references of a non-empty tree will always point to another tree -- it's just a question of whether or not that other tree is empty.
When you are implementing various methods, you will notice how convenient this polymorphism is -- you will simply call a method on the left/right child of the current node without having to distinguish whether or not the child is empty or non-empty.
If you think about it, all empty trees are alike. They have no data, so there is no way to distinguish one empty tree from another. For this reason, we will be employing the "Singleton Design Pattern" in our implementation of the empty tree class. This means that we will instantiate exactly one instance of the empty tree class. Anytime a non-empty tree has a missing left/right child, it will refer to this one copy of the empty tree.
Classes You Need to Implement
SinglyLinkedList - Implements a typical sorted singly linked list. This class must implement the SortedDataStructure interface. Implement this class without using polymorphic empty/non-empty nodes.
EmptyTree - Implements an empty tree. This class must implement the Tree interface.
NonEmptyTree - Implements a non-empty tree. This class must implement the Tree interface.
You must write a one or two page report comparing the performance of the binary search tree vs. the singly linked list. From lecture you already know the order (Big O notation) associated with each structure. By writing some tests and examining the CPU time each test takes, show that the binary search tree and the singly linked list behave as specified by the growth-rate function.
The following is additional information regarding the performance report:
As part of your tests you may need large data sets. One possibility is to use the data sets generated by the Moby Project. The "Moby Words" data set (represented by the file mwords.tar.Z) could be used to generate appropriate data sets for your tests. Keep in mind that you do not necessarily need to use all the words in the original set. IMPORTANT: Do not include your data sets in the final submission of your project as they could be really big.
Use the PerformanceExample class to learn how to determine the cpu time it takes to complete a task.
Your report must include a table where you compare the time it takes the binary search tree and the link list implementation to process different sets of data. Provide a description of the nature of each test and of each data set.
Write your tests in the performance package. Remember to remove any data sets these tests utilize.
Include your report in the performance package of your project (when you submit your project you will be submitting the report along with it). We will grade the report based on its contents (not on how nice it looks) so a word file or text file will be fine.
Name your report file "Report.txt" or "Report.doc".
In your report provide your machine configuration (e.g., processor type, processor speed, amount of main memory).
When you run experiments make sure that you are basically only running eclipse in your computer (no IM, games, web surfing, etc.).
Honor Section Requirements
In addition to the above requirements, you must satisfy the following requirements:
Submit your project using the submit project option associated with Eclipse.
Please make sure you read the academic integrity section of the syllabus so you understand what is permissible in our programming projects. We want to remind you that we check your project against other students' projects and any case of academic dishonesty will be referred to the University's Office of Judicial Program