CMSC751/ENEE759K Programming Homework 1 - Revised
Due: April 23, 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

The following files are provided:
http://www.glue.umd.edu/~balkanay/mem_map.h                                     
http://www.glue.umd.edu/~balkanay/mem_map.bin 

Please examine the mem_map.h for the global variables that you can
use. The mem_map.bin file contains the portion of the memory, where
these global variables reside. Please do not change these files. The
variables are initialized to the following values:
                                                                                
int gen_array[10000];          // an array of 10000 elements
int gen_array_length;          // 10000
int gen_aux_array[10000];      // all elements are 0
int gen_aux_array_length;      // 10000
int gen_temp_array[10000];     // all elements are 0
int gen_temp_array_length;     // 10000
int gen_pointer;               // 0
int gen_randomNumbers[500];    // an array of random numbers
int gen_randomNumbers_length;  // 500
                                                                                
Your input array is "gen_array". You have an auxiliary array
"gen_aux_array" and a temporary array "gen_temp_array" of the same
length at your disposal. You also have an array of randomly generated
numbers in "gen_randomNumbers". You can use the "gen_pointer" to keep
track of the last random number you picked from the list.

You may need to rename the binary files, in order to make them
compatible to the simulator.

For trying your program, you can use smaller input arrays. A smaller
input set (8-element input array) for trying your algorithm is
available here:
                                                                                
http://www.glue.umd.edu/~balkanay/mem_map_8.h                                   
http://www.glue.umd.edu/~balkanay/mem_map_8.bin  


Issues:

- 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.

- Please try to write your program within the main() function only. Do
  not use any other functions.

- Print out the following information about 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 responding each of the
  above queries.

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

REMARKS ABOUT PROGRAMMING

1. Use spawn(reg1,reg2) instead of spawn reg1,reg2 (ANSI C style).

2. Use ps(reg1,reg2) instead of ps reg1,reg2

3. Use

spawn(.)
{
.
.
.
}

instead of

spawn(.)
{
.
.
.
}
join

join is implied. It is not written explicitely anymore.


4. Do NOT use the reserved words spawn,spawni,ps,psm & fork as part of your
variables names.