Exam 2: Algorithms and Recursion

To find the smallest difference between any two 
  different numbers in a collection ...
Set estimate to ``infinity''
For each value, v, in the collection
  For each value, u, not equal to v
    If |u-v| < estimate then
      Set estimate to |u-v|
Return estimate

To find the greatest difference between any two 
  different numbers in a collection ...
Set estimate to 0
For each value, v, in the collection
  For each value, u, not equal to v
    If |u-v| > estimate then
      Set estimate to |u-v|
Return estimate

/**
 * Utilities for finding interesting facts about arrays of integers.
 *
 * @author Samuel A. Rebelsky
 * @author Carla Caffeinated
 * @author Carl Caffeinated
 * @version 1.0 of October 1999
 */
public class DifferenceComputer {
  /**
   * Determine the greatest difference between any pair of values
   * in the an array of integers.
   * Pre: The array is nonempty.
   * Pre: The greatest difference is less than the maximum integer.
   * Post: Returns the largest |values[i]-values[j]|.
   */
  public int greatestDifference(int[] values) {
    int estimate = 0;
    int difference;
    // For each value, values[i], in the collection
    for (int i = 0; i < values.length; ++i) {
      // For each value, values[j], in the collection
      for (int j = 0; j < values.length; ++j) {
        // Determine the difference between the two values
        difference = Math.abs(values[i]-values[j]) ;
        // If it's bigger than the biggest difference so far then
        if (difference > estimate) {
          // Update our estimate of the biggest difference
          estimate = difference;
        }
      } // for j
    } // for i
    return estimate;
  } // greatestDifference(int[] values)
  
  /**
   * Determine the greatest difference between any pair of values
   * in the an array of integers.
   * Pre: The array is nonempty.
   * Pre: The greatest difference is less than the maximum integer.
   * Post: Returns the largest |values[i]-values[j]|.
   */
  public int leastDifference(int[] values) {
    int estimate = Integer.MAX_VALUE;
    int difference;
    // For each value, values[i], in the collection
    for (int i = 0; i < values.length; ++i) {
      // For each value, values[j], in the collection
      for (int j = 0; j < values.length; ++j) {
        // If the two values are not the same
        if (values[i] != values[j]) {
          // Determine the difference between the two values
          difference = Math.abs(values[i]-values[j]) ;
          // If it's smaller than the least difference so far then
          if (difference < estimate) {
            // Update our estimate of the least difference
            estimate = difference;
          }
        } // if the two values are different
      } // for j
    } // for i
    return estimate;
  } // leastDifference(int[] values)
} // class DifferenceComputer

import SimpleOutput;

/**
 * Test our amazing and clearly marketable difference computer.  Thanks
 * to our beloved teacher, Sam Rebelsky, for giving us the initiative
 * to create such a great product.
 *
 * Usage:
 *   ji TestDC value1 value2 ... valuen
 *
 * @author Carl "Creative Code" Caffeinated
 * @author Carla "Clearly Clever" Caffeinated
 * @version 1.0 of October 1999
 */
public class TestDC {
  public static void main(String[] args) {
    // Prepare for output.
    SimpleOutput out = new SimpleOutput();
    // The array of integers.
    int[] values = new int[args.length];
    // An index into that array;
    int numValues = 0;
    // Did the user screw up?  Assume not.
    boolean badInput = false;
    // Create something that can compute differences.
    DifferenceComputer computer = new DifferenceComputer();
    // Convert each value to an integer.  Let the user know if (s)he
    // screwed up.
    for (int i = 0; i < args.length; ++i) {
      try {
        values[numValues++] = Integer.parseInt(args[i]);
      }
      catch (NumberFormatException nfe) {
        out.println("'" + args[i] + "' is not a number");
        badInput = true;
      }
    } // for
    // If the user gave bad input, we need to update the array
    if (badInput) {
      int[] tmp = values;
      values = new int[numValues];
      for (int i = 0; i < numValues; i++) {
        values[i] = tmp[i];
      } // for
    } // if (badInput)
    // Find the biggest difference
    out.print("The greatest difference between values is: ");
    out.println(computer.greatestDifference(values));
    // And the least.
    out.print("The least difference between values is: ");
    out.println(computer.leastDifference(values));
  } // main(String[])
} // class TestDC

import Array;
import Comparator;
import IncomparableException;
import Sortable;

/**
 * Arrays that can be sorted using the amazing Quicksort routine.  Note
 * that we violate Java's method naming conventions because Quicksort is
 * a proper name.
 *
 * @author Samuel A. Rebelsky (general structure)
 * @author Mable Mathemagician
 * @author Myron Mathemagician
 * @version 1.1 of October 1999
 */
public class Quicksortable
  extends Array
  implements Sortable
{
  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+
  
  /**
   * Build a new sortable array of a particular size.
   */
  public Quicksortable(int n) {
    super(n);
  } // Quicksortable(int)
  
  /**
   * Build a new sortable array with a particular set of elements. 
   */
  public Quicksortable(Object[] elements) {
    super(elements);
  } // Quicksortable(Object[])
  
  // +-----------------------+-----------------------------------
  // | Methods from Sortable |
  // +-----------------------+
  
  /**
   * Sort an array using Quicksort.  
   * Pre: All elements in the array can be compared to each other.
   * Post: The array is sorted (using the standard meaning).
   */
  public void sort(Comparator compare) 
    throws IncomparableException
  {
    sort(compare, null);
  } // sort(Object[])

  /**
   * Sort an array using Quicksort.  If observer is non-null,
   * prints out pithy notes about the sorting.
   * Pre: All elements in the array can be compared to each other.
   * Post: The array is sorted (using the standard meaning).
   */
  public void sort(Comparator compare, SimpleOutput observer) 
    throws IncomparableException
  {
    Quicksort(0, size()-1, compare, observer);
  } // sort(Object[])

  // +----------------+------------------------------------------
  // | Helper Methods |
  // +----------------+
  
  /**
   * Sort part of an array using Quicksort.
   * Pre: All elements in the subarray can be compared to each other.
   * Pre: 0 <= lb <= ub < size()
   * Post: The array is sorted (using the standard meaning).
   */
  protected void Quicksort(int lb, int ub, 
                           Comparator compare,
                           SimpleOutput observer) 
    throws IncomparableException
  {
    if (observer != null) {
      observer.println("lb = " + lb + "; ub = " + ub);
    }
    // Variables
    Object pivot;	// The pivot we select.  Must be part of the subarray.
    int mid;		// The position of the pivot
    // Base case: size one arrays are sorted.
    if (lb == ub) return;
    // Pick a pivot and put it at the front of the array.
    swap(lb,pickPivot(lb,ub));
    // Determine the position of the pivot, while rearranging the array.
    mid = partition(lb,ub,compare);
    // Recurse on nonempty subarrays.
    if (lb<=mid-1) Quicksort(lb,mid-1, compare, observer);
    if (mid+1<=ub) Quicksort(mid+1,ub, compare, observer);
  } // Quicksort
  
  /**
   * Split the subarray given by [lb .. ub] into ``smaller'' and
   * ``larger'' elements, where smaller and larger are defined by
   * their relationship to a pivot.  Return the index of the pivot 
   * between those parts.  Uses the first element of the array 
   * as the pivot.
   * Pre: All the elements in the subarray can be compared.
   * Post: Returns n such that for all i between lb and n inclusive
   *   and j between n+1 and ub inclusive, get(i) <= pivot < get(j).
   */
  protected int partition(int lb, int ub, Comparator compare) 
    throws IncomparableException
  {
    // STUB.  Can you figure it out?
    return lb;
  } // partition(int, int, Comparator)
  
  /**
   * Pick a pivot in a subarray.
   * Pre: 0 <= lb <= ub < size()
   * Post: returns the index of the pivot (a value between lb and ub inclusive).
   */
  protected int pickPivot(int lb, int ub) {
    // Simple implementation: pick the last element.  Might be extended
    // to do something more interesting, such as pick a random element
    // in the subarray.
    return ub;
  } // pickPivot(int,int)
} // Quicksortable

import IncomparableException;
import StringComparator;
import Quicksortable;
import SimpleOutput;

/**
 * A test of the Quicksortable class.  Sorts the strings on the command
 * line and then prints them out.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of October 1999
 */
public class TestQS {
  /** Do the testing. 
   *
   * @exception IncomparableException
   *   Never, since StringComparator never throws one, but it's
   *   easier to claim that we might throw one since it seems that
   *   the sort method might.
   */
  public static void main(String[] args)
    throws IncomparableException
  {
    // Prepare for output.
    SimpleOutput out = new SimpleOutput();
    // Build the array for sorting.
    Quicksortable stuff = new Quicksortable(args);
    // Sort!
    stuff.sort(new StringComparator(),out);
    // And print it out.
    for (int i = 0; i < stuff.size(); ++i) {
      out.println(i + ": " + stuff.get(i));
    } // for
  } // main(String[])
} // class TestQS

import Comparator;

/**
 * Utilities for searching in arrays.
 *
 * @author Carl Caffeinated
 * @author Carla Caffeinated
 */
public class Searcher {
  /** 
   * Determine if a value is in the array.
   */
  public boolean search(Object lookForMe, Object[] lookHere, Comparator compare)
    throws IncomparableException
  {
    return search(lookForMe, lookHere, 0, lookHere.length-1, compare);
  } // search(Object, Object[])
  
  /**
   * Determine if a value is in a subarray.
   */
  protected boolean search(Object lookForMe, Object[] lookHere, 
                           int lb, int ub,
                           Comparator compare) 
    throws IncomparableException
  {
    // Is the subarray empty?  If so, the object can't be there.
    if (ub < lb) return false;
    // Otherwise, it must be in the middle, left half, or right half.
    int mid = (lb + ub) / 2;
    return ( compare.equals(lookForMe, lookHere[mid]) ||
             search(lookForMe, lookHere, lb, mid-1, compare) ||
             search(lookForMe, lookHere, mid+1, ub, compare) );
  } // search(Object, Object[], int, int)
} // class Searcher