Exercises will be distributed during our lessons or by email. Max 6 points.

Ex. 2 at p. 11 of the coursebook. Max 5 points.

Exercise 4.5-1 in Cormen. Max 4 points.

Implement the parallel recursive algorithm 3.1 for prefix sum in our textbook. Submit a zipped source code + executable code for .net 7.0 or higher. The application should allow to enter input data and then to print out the result. Max 8 points.

Max 6 points.

Exercise 3 in Section 4.3 of our coursebook. Max 6 points.

Implement the SampleSort described in Exercise 3 in Section 5.2 of our coursebook. Choose n=1024 (size of the input array) and m=15 (there will be 15 splitters and 16 buckets). Elements of the input array must be separated into the buckets in parallel. In C#, use the Parallel.For method or the thread pool, and the recommended class to implement buckets is the ConcurrentBag, https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentbag-1, which allows concurrent addition of elements from multiple threads. Then you can sort all buckets in parallel by the method ToImmutableSortedSet, Finally, concatenate in parallel all the sorted buckets into an output array - you will need prefix sums to map buckets to their correct positions in the array. Max 10 points.

Ex.1 in Section 7.4 of our coursebook. The code must process an arbitrary input array of length n=2^k for any reasonable k>0. Test it with an input array of size n=1024 with random integers in range 0-1000, print the input and the result. Max 8 points

Insert, in parallel, sequence (5, 15, 25, 35, 45, 55, 65, 75, 85) into the tree at Fig. 6.4 (d) in our coursebook following the algorithm in Sec. 6.2. Draw on paper parallel balancing steps of the tree similarly as Fig. 6.4 (a) - (d). Upload the scan or photo. Max 4 points.

Program the parallel insertion of a sequence of keys B into a 2-3 tree under the simplifying assumption that no more than one key ever falls between two existing leaves of the tree. You have available sample code with some methods (not tested so there might be a bug). Please submit (in a zipped archive) source code + sample results: * listing of the tree after the end of phase 1 (in text form - using ToString) * inserted array B * listing of the tree after the end of phase 2 and overall balancing. Max 20 points.

Please submit your source code + sample results: * content of the original tree (in text form); * the inserted array B; * listing of individual phases of adding nodes and gradual balancing. I recommend using Parallel.ForEach or thread pool to create/delete threads. Max 20 points.