Skip to main content

Exercises

  1. Starting from the sequential implementation of the bubble sort algorithm found in the oets.c file from the lab skeleton, implement and parallelize the odd-even transposition sort algorithm.
  2. Analyze the scalability of the implementation from the previous point. Check hint 1 below for additional information.
  3. Starting from the sequential implementation of the shear sort algorithm found in the shear.c file in the lab skeleton, parallelize the algorithm.
  4. Analyze the scalability of the implementation from the previous point. Check hint 1 below for additional information.
  5. Starting from the sequential implementation of the merge sort algorithm found in the merge.c file in the lab skeleton, parallelize the algorithm. Check hint 2 below for additional information.
  6. Starting from the code skeleton in the parallel_binary_search.c file in the lab skeleton, which has a sequential implementation of the binary search algorithm as a hint, implement the parallel version of binary search. Analyze the scalability of the implementation.
tip
  1. In all source files from the lab skeleton, the correctness of the parallel implementation is verified by sorting the array using quick sort as a reference at the end (element-by-element comparison). When you want to test the scalability of your program, comment out or remove the quick sort and the associated comparison to obtain more accurate timing. Also, try to remove all terminal outputs.
tip
  1. The merge sort implementation in the lab skeleton works for an N that is a power of 2. Test your parallel implementation only on this case.