PD_ParallelDecomposition TCPP_Algorithms K_12 CS2 DSA visual movement

Originally Described by Adam Rifkin (1994). No web-link to independent description available. However, (Sivilotti2003) employed the exercise in a summer workshop for middle school girls, and provided a write-up of the activity and slides associated with the activity at his website

See papers (Rifkin1994, Sivilotti2003) for additional details.

Similar Exercises:

Sorting: oddEvenTranspositionSort, sortingNetwork, cardsorting

Other activities by (Rifki1994, Sivilotti2003)

Rifkin1994: oddEvenTranspositionSort


(Rifkin1994) designed the activity to take place in the course of the hour, and was introduced to high school minority students in a workshop format. Prior to the exercise, students are given an overview of the concept of sorting, and try to come up with ways to sort a collection of six random numbers.

The instructor then splits the group into nine teams (of about the same size), with three teams assigned to a separate supervisor. The supervisor will then have one of the three teams perform bubble sort, the second perform odd-even-transposition sort (described in a separate exercise ), and the last perform parallel radix sort.

Each team under the care of supervisor stands in a separate row. Each row has indices noted on the ground, indicating where students should stand, numbered from 0 … n-1 where n is the number of students in each row. Each student at index i is handed a random number that corresponds to the same index in a separate row. Each row is then given its own set of instructions, and they are instructed to follow the instructions specifically (without talking) to sort the numbers.

For parallel radix sort, the exercise is formed as a “race”, where the group leader walks down the line with the student at space 0.

The smallest number will have had a private counter of 0, and will stand in space 0, as they never encountered a number that was smaller. The next smallest number will be at space 1, and so forth.

Students are asked to think why the list should be sorted at the end of Parallel Radix Sort.

Variants (Sivilotti2003)

Sivilotti performed the activity exactly as described in (Rifkin1994). However, prior to introducing the activity, used an analogy to describe computers as “chefs” and programs to “recipes”. Like programs, recipes are characterized by what their ingredients (input) and the final product (output). A software engineer is thus described as a “recipe-engineer”.

CS2013 Knowledge Unit Coverage

Parallel Decomposition

2. Identify opportunities to partition a serial program into independent parallel modules. [Familiarity]

TCPP Topics Coverage

TCPP algorithms


The exercise may be difficult for students who are mobility-impaired, or have trouble with visual. Cards can have Braille on them, so when a blind student plays the stationary student role, he or she can reach out and touch the card to read the value. Verbal acknowledgments may be most appropriate when the blind student acts as the roving student in the exercise. Verbal acknowledgments may also be preferable to students who have trouble raising their hands.


(Rifkin1994) gives a general overview of assessment; 81 students completed surveys, in which they overwhelmingly responded that the workshop as a whole was a positive experience, and that respondents “learned something, had fun, and had a better impression of computer science” (Rifkin1994). However, specific assessment of parallel radix sort was not provided.

(Sivilotti2003) reported the sorting activity could be completed in a 45 minute period. Students were asked a number of questions, including rating the exercises. On a scale from 1 (low) to 5 (high) students rated the parallel sorting exercise as a 4.4. Students also made statements such as “the more ‘chefs’[processors] you use, the faster the program will finish” and “sequential are slow” (Sivilotti1999). Students were also asked to evaluate the overall quality of the computer science module on scale of 1 (low) to 5 (high), and rated the cs component of the workshop as 4.6. Note that this includes other activities.