Module: Parallel Sorting

Description

This module consists of some background reading prior to a mini-lecture and an activity that students undertake in small groups. It is a primarily conceptual module with follow-on homework assignments designed to have students studying algorithms begin to consider how to think about designing algorithms where multiple processing units can be executing in parallel. This particular example is based on the classic merge-sort sequential algorithm.

Materials

Initial reading prior to class: AlgorithmsDataStructuresSortingmodule.pdf

Slides for in class: ParallelSortClassPresentation.pptx or ParallelSortClassPresentation.pptx.pdf

In the above, there is a place for the students to stop and break into small groups and develop the pseudocode for parallel merge sort. The solution is on the next slide. This has proven to be a good exercise to have them thinking deeply about the solution (if you have a class size that warrants it use-- otherwise you can simply work through the solution). One day often ends there. If you want to carry the topic further, the slides continue with a couple of other examples that are not sorting. Alternatively, we usually work through these notes with students: an Explanation of the Complexity of Parallel Sort

Suggestions for homework: ParallelAlgorithmHomeworkQuestions.docx

Your Tasks

You can feel free to look through these materials and try the suggested practice problems in the initial reading.

Curricular Use

This module is designed to be used in an Algorithms or Algorithms and Data Structures course, typically shortly after working on sorting algorithms.