Due April 17
Submit the assignment to Abhijit Guria, guria at cs.nyu.edu.
Implement the following program in Ada:
- Read in 30 numbers into an array. Each number is an integer
between 0 and 1000.
Then create three tasks, printer, sorter and
that run in parallel. These tasks perform the followng
- First print out the elements of the array.
- Notify sorter that the numbers have been
- Wait for notification from sorter that it
- Print out the elements of the array again.
- Wait to receive a value from adder
- Print the value received from adder
- Wait for notification that sorter
- Compute the sum of the elements of the sorted array.
- Send the result to printer.
- Wait for notification that printer
has printed the elements of the array.
- Sort the array according to the parallel
quicksort algorithm described below.
- Notify both printer and adder that the
array is sorted.
In a separate package (and in a separate file), define
the procedure Quicksort(A), where A is an array of
size n, which performs the following actions:
- If n=1, then return.
- Otherwise, apply the routine split to A as follows:
- Assign to variable m the median value of the first element, the
middle element and the last element of A. If there are only two elements
of A then assign to m the smaller of the two values.
Define two variables i and j. Set i = 1 and
j = n.
While i is less than j perform the following steps:
While A[i] is less than or equal to m, increment i.
While A[j] is greater than m, decrement j.
If i is less than j, exchange the values of A[i] and A[j].
The array A has been split into two parts. The first part of A
contains only numbers less than or equal to m and the second part of
A contains only numbers greater than m. Call quicksort
recursively on each of the two parts. The two recursive calls should
occur in PARALLEL and should share the array.
Assume that all elements of the array are unique (no repetitions of numbers).
Notice that by making the recursive calls to Quicksort in parallel,
you will end up with many tasks executing concurrently.