CScD-543/443 (Spring 2009) — Java Threads Programming

Thread programming assignment:    Trapezoid integration exercise, specifically the Java part of it

Parallel_435     Link to a web page for CScD-435 (Programming Languages) on parallel processing.

Java Threads    Link to the simple programs from Oaks and Wong's Java Threads

Monte Carlo integration example:  fire a shotgun at the function and count the holes under the function.
LnSeq.java        Sequential program to calculate a natural log (integration of dt/t) — in  Java    LnSeq.txt
LnCalc.java       Java threads implementation — file also includes the class LnThread    LnCalc.txt    LnCalc.rtf    LnCalc.exe

Histogram example:  given a vector of random data, generate the histogram.
Histogram.java  Java program taking advantage of Java threads to compute the histogram   Histogram.txt
RunLogs.rtf        Specimen execution of the Java and the C++ programs (see "Fork-based parallel files").
Histogram.rtf     Word-processor file giving the C++ and Java programs in two-column landscape format

2007 Java threads programming assignment
This will be using threads to optimize another wrong-headed sorting algorithm:

/**
 * sort     Rearrange x so that no element is out of order
 *
 * @param   x  Array to be sorted
 */
public static void sort ( Comparable[] x )
{  do  shuffle(x);  while ( ! sorted(x) );  }

// Random number generator used by shuffle
private static java.util.Random gen = new java.util.Random();
/**
 * shuffle  Randomize position of all array elements
 *
 * @param   x  Array to be shuffled
 */
private static void shuffle ( Object[] x )
{  for ( int n = x.length ; n > 1 ; )
  {  int    k = gen.nextInt(n--);  // Note post-decrement
     Object temp = x[k];

     x[k] = x[n];
     x[n] = temp;
  }
}

/**
 * sorted    Determine whether the array is sorted.
 *
 * @param    x  Array to be tested
 * @return   false if any element in x is out of order, else true
 */
private static boolean sorted ( Comparable[] x )
{  for ( int j = 1; j < x.length; j++ )
     if ( x[j-1].compareTo ( x[j] ) > 0 )    // I.e., comes AFTER
        return false;
  return true;      // NOTHING was out of place
}

The approach will be borrowed from the N-Queens algorithm discussed here:  Las Vegas Solution to N-Queens.

The compute-engine will be an inner class to your program so that your program has access to its private parts.  Within the class is a "solution" array which will be null until one of the compute engine objects discovers a sorted configuration.  At that point the object with the solution will set the solution array to the sorted array.  As in the N-Queens, there is a small change to the while condition:
while ( ! ( solution != null || sorted(x) ) )
On loop exit you will set solution to the sorted vector x if solution == null; that is, if you exit the loop because sorted(x) is true.  This will cause all other compute engine objects to end, since solution != null becomes true.

Instructor's Solutions:
ShuffleThread.java   This version creates new Thread objects for each data configuration
ShuffleBarrier.java   This version creates just one set of Thread objects, which then compute different problems.
ShuffleBarrier.rtf      Formatted for printing as two sides of two-column text.