Objective

This homework has several objectives.  Those objectives are:

• Practice binary search trees and linked lists.

• Practice polymorphism

• Practice writing test cases

• Practice performance analysis

• Practice recursion

This homework is considered a closed homework.  Make sure you read the Open/Closed policy before continuing working on this project.

Overview

For this project you will complete the following tasks:

• Implement a class named SinglyLinkedList which implements a sorted singly linked list.
• Implement two classes named EmptyTree and NonEmptyTree which implement a binary search tree.
• Complete a performance comparison report that compares the performance of a singly linked list implementation vs. the binary search tree implementation.

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.

• There are two tokens for release testing.
• The project's code distribution is available by checking out the project named p5. The code distribution provides you with the following:
  • A folder named src - In this folder you will find the packages bst, list, sortedDataStructure, performance and tests.
  • A package named bst - In this package you will implement the EmptyTree and NonEmptyTree classes.  This package contains an interface named Tree, which must be implemented by the previous two classes.  We have left a class called BinarySearchTree which makes use of the EmptyTree and NonEmptyTree classes in order to implement the binary search tree functionality.  Notice that you cannot modify this class.  In addition to the above classes, we have left a class called BSTDriverExample that illustrates how we can use the binary search tree class.
  • A package named list - You must implement the SinglyLinkedList class in this package.We have left a class called  ListDriverExample that illustrates how we can use the singly linked list.
  • A package named sortedDataStructure - We have left an interface named SortedDataStructure in this package.  This interface is implemented by both the BinarySearchTree and the SinglyLinkedList class.
  • A package named performance - We have left a class named PerformanceExample that illustrates how you can obtain the CPU time for a particular task.
  • A package named tests - You will find the JUnit public tests we provided in this package. 

Specifications

Important Restrictions

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.

Documentation

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.

Polymorphism

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

• data Object

• 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.

Singleton Design Pattern

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.

Performance Report

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.).

Style Requirements

• You must avoid code duplication.  For example, if several methods in your class share the same code fragment place that fragment in a private method.
• You must follow Java conventions for identifiers.  For example, class/interface names must start with capitals.
• You must use meaningful variable names.
• You must indent your code using three or four spaces or by using the Eclipse "Correct Indentation" option.
• You must use the same style for blocks of curly brackets ({ }) throughout your code. 

Honor Section Requirements

In addition to the above requirements, you must satisfy the following requirements:

• Implement a second version of the binary search tree class that does not use polymorphic empty nodes. This version explicitly checks whether a subtree represents an empty node (i.e., if left equals null or right equals null).
• Compare the non-polymorphic binary search tree implementation with the polymorphic one.

Submission

Submit your project using the submit project option associated with Eclipse. 

Academic Integrity

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