## 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 adder, that run in parallel. These tasks perform the followng actions:

• Printer:
• First print out the elements of the array.
• Notify sorter that the numbers have been printed.
• Wait for notification from sorter that it is finished.
• Print out the elements of the array again.

• Wait for notification that sorter is finished.
• Compute the sum of the elements of the sorted array.
• Send the result to printer.

• sorter:
• 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.

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