CMSC751/ENEE759K Programming Homework 1
Due: March 17, 2004.

The objective of this homework is to use the XMT paradigm in order to
program a parallel variant of the serial randomized algorithm for
selection in expected linear time. The (serial) algorithm appears in
chapter 9.2 of the book Introduction to Algorithms, by Cormen,
Leiserson, Rivest and Stein. 

The project requires writing both a serial and a parallel version,
run both on the XMT simulator and compare running times and the total number
of operations.

Before starting programming derive an iterative variant of the serial
algorithm in a text form.
The expected number of iterations should be O(log n).
The expected amount of work should be linear.
The expected parallel time should be O(log ^2 n).

Derive two implementations (programs) from the iterative variant:
- a parallel one.
- a serial one.

Provide the results on an input of size n=10000, available at:
http://www.glue.umd.edu/~balkanay/array.h

For trying your program, you can use smaller input arrays (say n=8).


Issues:

- A set of random numbers (generated off-line) is available at:
  http://www.glue.umd.edu/~balkanay/randomNumbers.h
  The random numbers provided here are between 0 and 32768 (2^15). You can use the modulo
  operation ('%' operator in C) to generate a random number within a desired
  range: Using the random number n from this file, "n % r" will give you a
  random number between 0 and r-1. 

- Unless you absolutely have to, please do not use the same random
  number in the file more than once.

- Produce (and print out) the following results relative to the given 10000 
element array:
  * the minimum element (1st smallest element)
  * the maximum element (10000th smallest element)
  * the 5000th smallest element
  * the 2004th smallest element

- Print out the number of simulated cycles, while producing each of the
  above results, for both the parallel and serial code.

- In addition to the code and information about its execution, your
  submitted homework should include the text variant and an explanation
  (not necessarily a full formal proof) of its complexity analysis.