Algorithm Behavior Measurement:
Searching in a Sorted Linked List
Due:  Wednesday, 22 October
Javadoc Documentation
Required

This is available as a word processor file in RTF format (six pages)

We joked in class about doing a binary search within a sorted linked list:  traverse half-way through the linked list before examining a data item; based on that, traverse a quarter-way through one of the two sublists, etc., etc.  This is actually an algorithm that has some promise, as strange as it seems.

Like the array-based binary search, this algorithm will only perform about log2(n) comparisons.  As to the list traversal portion, that isn’t as wasteful as it might seem.  If each time we traverse, it’s only by half as much as the last time, then the total traversals will have the form of n(1/2 + 1/4 + 1/8 + 1/16 +...), meaning in the end that we only have to traverse n nodes, exactly the number we would have to traverse for a linear search.  Of course, the linear search of a sorted list will end as soon as something larger than the sought value is found, so there is an early exit available and on average you only need to traverse half the list even on failure.

Either in your own implementation of a linked list of sorted data, or in a stripped-down version with only the bare necessities, insert the following two methods:  public Comparable linearSearch(Comparable sought) and public Comparable binarySearch(Comparable sought).  Develop your program so that you can capture the number of comparisons performed, either by including the logic within the search methods themselves or by using the class MyComparable developed in the lectures.  You will be able to capture time through System.nanoTime().

Linear Search Algorithm

Given sought as the value desired, you can find it by doing a simple traversal of the sorted list:  at each step, capture the value returned by compareTo() regarding the item sought and the data field of the list node — just call compareTo() once and retain the value.  If the value shows that the item sought comes earlier in the list, it must not in fact be in the list so return the failure message, a null reference.  If the value is zero, return the data field of the list node since you’ve found it.  Otherwise continue the traversal.  If you get to the end without finding it, return the same failure message, a null reference.

Binary Search Algorithm

The public Comparable binarySearch(Comparable sought) method can use a private recursive method to do all the work:
private Comparable binarySearch(Node left, int size, Comparable sought)

The Node passed is the left-most node in a portion of the linked list, which is considered to contain size nodes.  Hence the public method would simply be this (assuming that the linked list implementation has fields head and size):
public Comparable binarySearch(Comparable sought)
{  return binarySearch(head, size, sought); } // or maybe binarySearch(head.next, size, sought)

The Recursive Method

If the size of the linked list segment is zero, return the null failure indication.  If the size of the linked list segment is exactly one, perform the appropriate check and return either the failure indication or the left node’s data field.  Otherwise compute the size of the left sublist (as size/2) and the size of the right sublist (as size minus the size of the left sublist).  Generate a Node right = left, then move it to the front of the right sublist — you know exactly how many steps that will take.  As in the linear search algorithm, capture the value returned by compareTo() regarding the item sought and the data field of the right list node.  If the value indicates that the item sought is in the left sublist, make a recursive call passing left and the computed length of that sublist.  If the value indicates that the item sought is in the right sublist, make a recursive call passing right.next and the computed length of that sublist minus one, since you have effectively discarded the node at right.  Otherwise you’ve found the item sought; return right.data.

Alternative to the Recursive Method

For the student that wants a challenge:  you don’t need a recursive method.  Do some reading about “tail recursion” and consider what it means in the context of the above recursive algorithm.

Driving Main

If you wish, you may include the exercising main function as Sahni does, or you can have it as a separate class.  It is to allow for but not require a command-line argument.  Following the statement “System.out.print("Size: )”, determine whether there is a command line argument (that is, if args.length > 0).  If so, parse args[0] as an integer, then complete the line on the screen by printing out that size.  If there is no command line argument, accept the size from the System.in.

Generate a linked list containing even Integer objects from 2 up through 2*size (or MyComparable wrapper objects with those Integer objects).  The list will be the basis for your determining average algorithm performance for both the linear search algorithm and the binary search algorithm.  You will determine both the average number of comparisons required and the average time required in microseconds (you will be using System.nanoTime()).

To determine the total comparisons and time to find, do each search on each of the even numbers from 2 up through 2*size.  For the averages, divide those numbers (as doubles) by size.  Within the loop, insure that the value returned by the search is correct, that is, that the search succeeded and the correct value is returned.  If you are using MyComparable objects, do not compare them directly as you check for correctness, but compare the objects returned by getValue().  Alternatively, use the freeCompare() method rather than the compareTo() method.

To determine the total comparisons and time to fail, do each search on each of the odd numbers from 1 up through (2*size+1).  For the averages, divide those numbers (as doubles) by (size+1).  Within the loop, insure that the value returned by the search is correct, that is, that the search failed.

Hint:  to collect your data, capture the current time before you start the loop and insure that the comparison count is zero.  After you exit the loop, capture the current time and the comparison count.

You are free to format your output in any fashion, provided that it is easy to read.  The instructor’s implementation generates the following output.

Linear search with early exit, 4096 items
65.477 microseconds to find, with 2048.500 cmp
63.242 microseconds to fail, with 2049.000 cmp

Binary search, 4096 items
17.085 microseconds to find, with 11.000 cmp
19.008 microseconds to fail, with 11.997 cmp

Once your program is working correctly, capture in a text file the results of running your program for the linked lists sizes 2048, 4096, 8192, and 16384.  After that output, write a brief description of what you have observed.

Extra credit option (25 points):

In your main, also generate a java.util.LinkedList with the same data and then capture the behavior of java.util.Collections.binarySearch() as well as your own linear search and binary search.  You will have to use the MyComparable class to capture the number of comparisons in this case.

To Turn In:

This assignment must be submitted in working order by midnight Wednesday, 22 October.  Submit a jar file with:

  1. your source file or files
  2. your text file as described above.
  3. IMPORTANT:  instructions on how to compile your program from the command line, noting specifically which file contains the driver.  

The grader should be able to open your jar file, compile your code, and run your program from the command line using javac and java version 1.5 or greater (so make sure you try this yourself before you submit).  The grader will be testing both the command-line specification of the list size and the user-dialog specification.