Assignment 1 (due Sunday, 16 July, 10 pm)

In this assignment, you will implement merge sort using the multiprogramming paradigm. This assignment can be done either individually or in groups of two. Assignments submitted with more than two group members will not be accepted. This assignment can be done either in JAVA or in C.

You are free to choose either option.

What to do?

Java:

As you know, merge sort is an algorithm where the array of numbers is split into two halves, each half is sorted recursively using merge sort, and the sorted halves are merged. For this assignment, you will use the java thread package. You will use a thread to run every recursive call of merge sort i.e., at each stage you will create two threads to merge sort the two halves. When the two threads finish sorting, the parent thread merges the two halves by itself.

You will also measure a couple of important parameters of this program. In particular, you will measure the time taken to sort the entire array, and the number of threads that were used to do so. You must vary the size of the array to obtain the values for time taken and number of threads. You should be able to find out the optimal number of threads that the system can support efficiently.

In the second part of this assignment, you would port the same program to UNIX OS. Since java is machine independent, you should not have any problems in porting the program to UNIX. You would carry out the same measurements in UNIX.

For a tutorial on how to use threads see online java tutorial .

C:

As you know, merge sort is an algorithm where the array of numbers is split into two halves, each half is sorted recursively using merge sort, and the sorted halves are merged. For this assignment, you will use the fork system call in UNIX. You will spawn a process to run every recursive call of merge sort i.e., at each stage you will create two processes to merge sort the two halves. When the two processes finish sorting, the parent process merges the two halves by itself. You could use the wait system call to wait for the child processes to finish.

You would also need some form of inter process communication mechanism in order to get the sorted halves of the array from the child processes. We suggest you use shared memory for this. For the details about fork and wait system calls and shared memory, please refer to the book “UNIX Network Programming” by Richard Stevens.

What to submit?

You should submit the following things as a part of this assignment.

1. The java/C program or programs used to implement merge sort.

2. A file called README.txt where you give a tutorial on how to compile and run a program. This file should also contain the names, netids and cornellids of all the individuals in the group.

3. A file called RESULT.txt where you give the analysis of your experiment (only for thread implementation).

How will you be graded?

The following will play a crucial role in your grades for this assignment.

1. Correctness of the java/C programs written to implement merge sort.

2. Rigorousness of the experiment and analysis of results (only for thread implementation).

3. Clarity of the java/C programs (comments!!!).

4. Ease of using the README to test your programs and results.

What is a rigorous analysis?

The quantities of study here are the array size and therefore the number of threads and the time elapsed. A rigorous analysis would include testing for different values of array size (therefore number of threads) and giving a graphical interpretation. A comparison of results of the experiments in NT and UNIX and your general comments on the results.