Course Information

Emacs Reference Card (PDF)

Help Schedule

Lab 1: Getting Started

Lab 2: Writing Classes

Lab 3: Putting Classes Together

Lab 4: Inheritance and Interfaces

Lab 5: ADTs and Exceptions

Lab 6: ADT: Linked Lists

Project 2: ADTs: Arrays, Linked Lists and Trees

Sample Input Data

Lab 7: Android SDK and Eclipse

Lab 7: Download Android SDK (Windows)

Project2: Sample Solution

This page contains Java code for performing the experiments asked for in Project 2 and some plots of the output for comparisons.

  1. UnsortedArray.java
  2. SortedArray.java
  3. SortedLinkedList.java
  4. SortedBinaryTree.java
  5. driver.java

Experimental Results. All data points are the average of 500 operations.

Getting Data
Adding Data
UnsortedArray.java
// CS251 Project 2 Solution
// Author: Matthew Fricke
// Date: Fall 2012
// Email: mfricke@unm.edu. Please send bug reports to this email address.
// Description: A very simple class that acts as a wrapper for the unsorted array to be used in the experiments.
public class UnsortedArray
{
    private Student[] contents;
    private int data_size = 0;

    UnsortedArray( int size )
    {
	contents = new Student[size];
    }

    // Adds a student to the array in constant time since it is just appended to the end of the array.
    public void addData( int k, Student data )
    {
	contents[data_size++] = data;
    }

    // Search through all the elements in the array to see if any of them match the key we are looking for.
    // This takes linear time in the size of the array.
    public Student getData( int k )
    {
	// Dummy student to wrap the key so we can use the comparitor and keep track of the number of comparisons.
	Student key = new Student();
	key.setID(k);

	for( int i = 0; i < data_size; i++ )
	    {
		if ( key.compareTo( contents[i] ) == 0 )
		    {
			return contents[i];
		    }
	    }

	return null;
    }

    // Display the array for debugging purposes.
    public void displayArray()
    {
	for ( int i = 0; i < data_size; i++ )
	    System.out.print(" "+contents[i]);
    }

 }

SortedArray.java
// CS251 Project 2 Solution
// Author: Matthew Fricke
// Date: Fall 2012
// Email: mfricke@unm.edu. Please send bug reports to this email address.
// Description: A class to hold the sorted array we will be using in the experiments.
// Uses binarySearch to find and retrieve a Student in the array.

public class SortedArray
{
    private Student[] contents;
    private int data_size = 0;

    SortedArray( int size )
    {
	contents = new Student[size];
    }

    // Add a student to the array by iterating over the array until a student is found with an ID greater
    // than the ID of the student to be added. Move all the data elements from that point to the end of the array
    // up by one to make room to insert the new Student. Then add the student to the correct position. This
    // maintains the sorted property of the array. This method takes linear time in the size of the array.
    public void addData( int k, Student data )
    {
	Student key = new Student();
	key.setID(k);
	int i = 0;
       
	while( i < data_size && key.compareTo(contents[i]) > 0 )
	    {
		i++;
	    }

	for( int j = data_size+1; j > i; j-- )
	    {
		contents[j] = contents[j-1];
	    }

	contents[i] = data;
	data_size++;
    }

    // Display the array for debugging
    public void displayArray()
    {
	for ( int i = 0; i < data_size; i++ )
	    System.out.print(" "+contents[i].getID() );
	System.out.println();
    }

    // Wrapper method that calls binarySearch to retrieve a student matching the key "k" or returns null
    // if there is no such student.
    public Student getData( int k )
    {
	// Wrap the key in a dummy student object so we can use the student comparitor
	Student key = new Student();
	key.setID(k);
	return binarySearch( key, 0, data_size );
    }

    // Binary search return the student in logarithmic time in the size of the array.
    public Student binarySearch(Student key, int lowerbound, int upperbound )
    {
	// Choose a Student in the middle of the array
	int position = ( lowerbound + upperbound) / 2;
	
	// Check if the ID of the student is greater than, smaller than, or equal to the ID being sought.
	// If greater or equal then only consider the left side of the array and repeat.
	// If lesser then only consider the right side of the array and repeat.
	// If the upperbound is less than the lowerbound, i.e. the subarray we are left with is empty
	// then return null since no students in the array had the ID we were looking for. Otherwise return the
	// single element that's left since that is the element we are looking for.
	while( key.compareTo( contents[position] ) != 0 && lowerbound <= upperbound )
	    {
		if (key.compareTo(contents[position]) < 0 )            
		    {                                              
			upperbound = position - 1;   
		    }                                                             
		else                                                   
		    {                                                        
			lowerbound = position + 1;    
		    }

		position = (lowerbound + upperbound)/2;
	    }

	if (lowerbound <= upperbound)
	    {
		return contents[position];
	    }
	else
	    {
		return null;
	    }

    }
    
}

SortedLinkedList.java
// CS251 Project 2 Solution
// Author: Matthew Fricke
// Date: Fall 2012
// Email: mfricke@unm.edu. Please send bug reports to this email address.
// Description: A singly-linked list that maintains the sorted property on the 
// addData and getData operations.
// This list is just for Project 2 so it only requires an addData method
// and a getData method. 
public class SortedLinkedList
{
    private Node head = null;

    // Display the List for debugging.
    public void displayList()
    {
	Node current = head;
	while( current != null )
	    {
		System.out.print( " " + current.getData().getID() );
		current = current.getNext();
	    }      
	System.out.println();
    }

    // Add a Student to the linked list.
    // Precondition: The Students in the list are in sorted order with the 
    // Student at the head of the list having the least ID, or the list is empty.
    // Precondtion: The list is null terminated.
    // Postcondition: The Student is added to the list. The list is still
    // in sorted order and is still null terminated.
    public void addData( int k, Student data )
    {
	// Create a dummy student with the ID set to k so that
	// we can use the Student.compareTo( Student ) method which
	// makes it easy to count the number of comparisons.
	Student key = new Student();
	key.setID(k);

	// Handle the case where this is the first element in the list
	if ( head == null )
	    {
		head = new Node( data );
		return;
	    }
	
	// If this Student has ID less than the Student at the head of the list
	// then add the Student to the head of the list.
	if ( key.compareTo( head.getData() ) < 0 )
	    {
		Node temp = head;
		head = new Node( data );
		head.setNext(temp);
		return;
	    }

	// Iterate through the list until a Student is found with ID greater
	// than the new Student's ID. Insert the new Student into the list
	// just before the Student with the larger ID.
	Node current = head.getNext();
	Node predecessor = head;
	while ( current != null )
	    {
		if ( key.compareTo( current.getData() ) < 0 )
		    {
			predecessor.setNext( new Node( data ) );
			predecessor.getNext().setNext( current );
			return;
		    }

		predecessor = current;
		current = current.getNext();
	    }	

	predecessor.setNext( new Node( data ) );
    }

    // Return the Student that matches the key k. If no Student matches
    // the key then return null. 
    public Student getData( int k )
    {
	// Create a dummy student so that the Student's comparator method
	// can be used. The comparator can keep track of how many comparisons
	// occur for the experiments.
	Student key = new Student();
	key.setID(k);

	// Start at the head and iterate through the list until either:
	// 1) A student is found with an ID equal to the search key. Return that
	//    student.
	// 2) A student is found with an ID greater than the search key.
	//    Since the list is sorted the search key cannot match any students
	//    further down the list. So return.
	// 3) The end of the list of the list. Then no student in the list
	//    had matched the search key.
	
	Node current = head;
	while( current != null )
	    {
		if ( key.compareTo( current.getData() ) == 0 )
		    {
			return current.getData();
		    }
		else if ( key.compareTo( current.getData() ) < 0 )
		    {
			return null;
		    }

		current = current.getNext();
	    }

	return null;
    }

    // The list nodes that contain the Students
    private class Node 
    {
	private Node next = null;
	private Student data = null;

	Node( Student d )
	{
	    data = d;
	}

	public Student getData()
	{
	    return data;
	}

	public void setData( Student d )
	{
	    data = d;
	}

	public Node getNext()
	{
	    return next;
	}

	public void setNext( Node node )
	{
	    next = node;
	}
    }
}

SortedBinaryTree.java
// CS251 Project 2 Solution
// Author: Matthew Fricke
// Date: Fall 2012
// Description: A binary tree that maintains the recursive sorted property that 
// all data elements in the right subtree have keys that are greater than the root's key
// and all data elements in the left subtree have keys less than the root's key.
// Assume that Student IDs which are used as the keys are unique.
class SortedBinaryTree
{
    private Node root = null;

    // This code taken from Prof Kelley's website so I can see what is going on when I build the tree
    // Begin Prof Kelley's code
    public void displayTreeSide()
    {
	displayTreeSide( root, "", "", "" );
    }

    private void displayTreeSide( Node n, String leftPre, String rootPre, String rightPre ) {
	
	if(n == null) return;
	String label =  String.valueOf(n.getData().getLastName()) + "(" + n.getData().getID() + ")";
	String rootSpaces = String.format("%" + label.length() + "s", "");
	leftPre += rootSpaces;
	rightPre += rootSpaces;
	
	displayTreeSide( n.left, leftPre + "    ", leftPre + " ,-- ", leftPre + " |  " );
	System.out.println( rootPre + label );
	displayTreeSide( n.right, rightPre + " |  ", rightPre + " `-- ", rightPre + "    "); 
    }
    // End Prof Kelley's code
    
    // Wrapper function to getData that specifies to start at the root of the tree
    // Return the Student with ID equal to the key or null if no such student is found
    // Input: An integer key corresponding to the ID of the student to be returned
    // Output: A student object with ID equal to "key" or null if no such student exists in the tree
    public Student getData( int key )
    {
	// Create a dummy student with ID equal to the key being sought so that the Student comparitor
	// can be used. The comparitor keeps track of the number of comparisons for the experiments.
	Student s = new Student();
	s.setID( key );
	return getData( s, root );
    }
    
    // Recursive method used to retrieve the student object from the tree that matched the ID of the
    // student passed in as an argument. Returns null if there is no such student in the tree. Assumes
    // that Student IDs are unique so that at most one Student will match.
    public Student getData( Student key, Node parent )
    {
	Student parent_data = parent.getData();	 
	
	if (Global.debug) System.out.println("Considering " + parent_data.getID() );
	
	int compare = key.compareTo( parent_data );
	
	// Return the student in the parent node if the ID matches otherwise call getData()
	// recursively on the right or left subtree depending on whether the ID being sought is
	// less than or greater than the ID of the parent's student.
	if ( compare == 0 )
	    {
		if (Global.debug) System.out.println( "Found Key" );
		return parent_data;
	    }
	else if ( parent.getLeftChild()!=null & compare < 0  ) 
	    {	
		return getData( key, parent.getLeftChild() );
		
	    }
	else if ( parent.getRightChild()!=null & compare > 0 ) 
	    {
		return getData( key, parent.getRightChild() );
	    }
	
	// Should not reach this code since the if statement above ought to cover all cases.
	if (Global.debug) System.out.println("Error " + parent_data.getID() );
	return null;
    }
    
    // Wrapper to the recursive addData() method. Handles the case where this student is the first student
    // to be added to the tree. 
    public boolean addData( int key, Student data )
    {
	// Dummy student to wrap the key so we can use the student class's comparitor method and keep
	// track of how many comparisons have been performed
	Student student_key = new Student();
	student_key.setID(key);
	
	if ( root == null )
	    {
		root = new Node( data );
	    }
	else
	    {
		addNode( root, student_key, data );
	    }

	return true;
    }

    // Recursive method that adds a student to the sorted binary tree in the correct location.
    // Input: The parent node that is the root of this subtree. The key of the data element to add.
    // The Student to be added. 
    // Output: A boolean value indicating success or failure.
    public boolean addNode( Node parent, Student key, Student data )
    {  
	// There are four cases. Either the key of the student to be added is greater than the key of the root
	// or less.
	// If less then look at the left subtree, if greater look at the right subtree. 
	// If the subtree being looked at is null then add the student there, else call getData recursively on
	// the root of the subtree. Since Student IDs are unique there will always be a location to which the 
	// Student can be added.
	if ( key.compareTo( parent.getData() ) < 0 ) 
	    {
		if ( parent.getLeftChild() == null )
		    {
			parent.setLeftChild( new Node( data ) );
		    }
		else
		    {
			addNode( parent.getLeftChild(), key, data );
		    }
	    }
	else
	    {
		if ( parent.getRightChild() == null )
		    {
			parent.setRightChild( new Node( data ) );
		    }
		else
		    {
			addNode( parent.getRightChild(), key, data );
		    }
	    }

	// Always return true. Makes it possible to add error checks if the tree is someday extended to handle
	// non-unique IDs.
	return true;
    }

    // The node class that is used as building blocks to make the binary tree 
    // and which holds the student data elements.
    private class Node
    {
	public Student data = null;
	public Node left = null;
	public Node right = null;

	Node( Student d )
	{
	    data = d;
	}

	public Student getData()
	{
	    return data;
	}

	public boolean setData( Student d )
	{
	    data = d;
	    return true;
	}

	public Node getLeftChild()
	{
	    return left;
	}

	public Node getRightChild()
	{
	    return right;
	}

	public boolean setLeftChild( Node n )
	{
	    if ( left == null )
		{
		    left = n;
		    return true;
		}
	    
	    return false;
	} 

	public boolean setRightChild( Node n )
	{
	    if ( right == null )
		{
		    right = n;
		    return true;
		}
	    
	    return false;
	} 

    }

}


driver.java
// CS251 Project 2 Solution
// Author: Matthew Fricke
// Date: Fall 2012
// Email: mfricke@unm.edu. Please send bug reports to this email address.
// This driver creates a sorted array, an unsorted array, a sorted list, and a sorted binary tree to hold Student objects, and performs some efficiency experiments on the datastructures.

import java.util.Arrays; // For sorting arrays
import java.util.Collections; // For shuffling arrays
import java.text.DecimalFormat; // For formating the output to some precision

class driver
{
    // Print correct usage and exit
    public static void usage()
    {
	System.out.println("Usage: driver [(un)sorted array|list|tree] [number of data items to insert] [number of gets to perform]");
	System.exit(1);
    }



    // main() expects three arguments
    public static void main( String[] args )
    {

	// Do some input checks
	// Check that the user passed the correct number of arguments
	if ( args.length != 3 ) usage();

	// Get the datastructure argument and make sure it is a valid choice
	String datastructure = args[0]; 
	
	if ( !Arrays.asList("unsorted array", "sorted_array", "list", "tree").contains(datastructure) ) usage(); 
	

	// Set the number of items to add to the datastructure 
	// and the number of gets to perform in the experiments
	int num_adds = 0; 
	int num_gets = 0; 
	
	// Check the arguments passed in by the user to make sure they are integers
	try 
	    {
		num_adds = Integer.parseInt(args[1]);
		num_gets = Integer.parseInt(args[2]);
	    }
	// Catch the exception if arguments are not integers and exit
	catch ( Exception e )
	    {
		usage();
	    }
	
	double total_time_taken = 0;

	// Create an unsorted and sorted array twice the size of the number
	// of items we want to add so we have room to pay with adding more items
	UnsortedArray ua = new UnsortedArray( 2*num_adds );
	SortedArray sa = new SortedArray( 2*num_adds );

	// Create a sorted linked list and a sorted binary tree
	SortedBinaryTree bst = new SortedBinaryTree();
	SortedLinkedList sl = new SortedLinkedList();
	
	// create the data items to add and give them some silly names
	Student[] students = new Student[num_adds];
	for ( int i = 0; i < num_adds; i++ )
	    {
		String suffix = "";
		switch ( i % 10 )
		{
		case 1: suffix = "st"; break;
		case 2: suffix = "nd"; break;
		case 3: suffix = "rd"; break;
		default: suffix = "th"; 
		}	

		String first_name = "Bill";
		String last_name = "Frankenfurter the " + i + suffix;
		students[i] = new Student( i*2, first_name, last_name );
	    }
	

	// Randomly reorder the students just created so our tree
	// doesn't turn into a linked list and so adding items to the sorted list
	// doesn't always add items to the end or to the front.
	Collections.shuffle(Arrays.asList(students));

	// Add the students one by one to the datastructure specified by the user.
	// Time how long each addition takes and count how many comparisons occur.
	for ( int i = 0; i < num_adds; i++ )
	    {
	        if (Global.debug) System.out.println("Adding: " + students[i].getID() );
		double start = System.nanoTime();
		int key = students[i].getID();
		if ( datastructure.equals("tree") ) bst.addData(key, students[i]);
		else if ( datastructure.equals("list") ) sl.addData(key, students[i]); 
		else if (datastructure.equals("sorted_array")) sa.addData( key, students[i] );
		else if (datastructure.equals("unsorted_array")) ua.addData( key, students[i] );

		total_time_taken += System.nanoTime() - start;
	    }

	double comparison_average_for_add = Student.getComparisonCount()/num_adds;
	double time_average_for_add = total_time_taken/num_adds;

	// Reshuffle the students and perform some specified number of get operations.
	Collections.shuffle(Arrays.asList(students));

	// Do one get on the tree to prime the cache. The first get takes much
	// longer than the others. This could be because of prefetching? Mystery.
	if (datastructure.equals("tree")) bst.getData( students[0].getID() );

	// Initialize the time and counter variables
	Student.resetComparisonCount();
	total_time_taken = 0;

	for ( int i = 0; i < num_gets; i++ )
	    { 
		if (Global.debug) System.out.println("Getting: " + students[i%num_adds].getID() );
		int key = students[i%num_adds].getID();
		
		double start_time = System.nanoTime();
		Student s = null;
		if (datastructure.equals("tree")) s = bst.getData( key );
		else if (datastructure.equals("list")) s = sl.getData( key );
		else if (datastructure.equals("array")) s = sa.getData( key );
		else if (datastructure.equals("sorted_array")) s = sa.getData( key );
		else if (datastructure.equals("unsorted_array")) s = ua.getData( key );		    	

		total_time_taken += System.nanoTime() - start_time;

		if (Global.debug)
		    { 
			if ( s == null ) System.out.println( key + " not found"); 
			else System.out.println( s.getLastName() );
		    }
	    }
       
	// If the debug flag is set print out the datastructures
	if (Global.debug) bst.displayTreeSide();
	if (Global.debug) sl.displayList();
	if (Global.debug) sa.displayArray();
	if (Global.debug) ua.displayArray();
	
	// Format the output values to one decimal place
	DecimalFormat df = new DecimalFormat("#.#");
	
	// Compute the averages
	double comparison_average_for_get = Student.getComparisonCount()/num_gets;
	double time_average_for_get = total_time_taken/num_gets;

	// Print the results to standard out
	System.out.println( df.format( comparison_average_for_add ) + " " 
			    + df.format( time_average_for_add ) + " "
			    + df.format( comparison_average_for_get ) + " " 
			    + df.format( time_average_for_get ) );
    }
}