OddEvenTranspositionSort

PD_ParallelDecomposition TCPP_Algorithms K_12 DSA CS2 visual accessible

Originally Described by Adam Rifkin (Rifkin1994), with a separate description by Michelle Moore (Moore2000). (Bachelis1994) also presents the sort as a “compare-exchange sort”. We extrapolate on (Rifkin1994), since it is well described.

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, Bachelis1994, Moore2000, Sivilotti2003) for additional details.

Similiar Exercises:

Sorting: parallelRadixSort, sortingNetwork CardSorting

Other activities by authors

Rifkin1994: parallelRadixSort

(Bachelis1994): ParallelAddition, FindSmallestCard, CardSorting, SieveOfErastothenes

(Moore2000): SieveOfErastothenes, CardSorting, MatrixAddition

Details

(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, and the last perform parallel radix sort (described in a separate exercise).

Each group under the care of supervisor stands in three rows. 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. For odd-even-transposition sort, even spots are marked in one color, while odd spots are marked in another.

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.

The row in charge of odd-even-transposition sort performs the following set of steps:

Students are asked note that the round does not need to be coordinated by group leaders, and to observe that that the list was becoming “more sorted” with each phase. At the end of the exercise, students were asked to consider the strengths and weaknesses of Odd-even-transposition sort, and why it was a parallel algorithm, and how it compares to bubble sort.

Variants

(Moore2000)

(Moore2000) describes an example exercise that she presents in a parallel processing lab. It is assumed that students know about the Bubble Sort algorithm ahead of time. Odd Even Transposition Sort is a “parallel” version of bubble sort. In this exercise, students are asked to physically simulate the multiple processors performing the sort. The main difference from (Rifkin1994) is that students stay stationary, while cards move around. This variant may be better for classrooms with students with impaired mobility.

The class then has a discussion that Odd-Even Transposition Sort has a parallel time complexity O(n) when n students are used for sorting. In contrast, the serial algorithm (bubble sort) has a time complexity of O(n2).

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

Accessibility

This exercise appears fairly accessible to everyone. For students who are blind, the Braille cards are recommended so students can read the number on them. For Deaf students the “Odd” “Even” phases can be signified by holding up a large sign. We do not anticipate any mobility issues, as students can sit in chairs for this exercise, and perform the variant described in (Moore2000). However, some groups may choose to use original description in (Rifkin1994) to engage higher energy, able students.

Assessment

(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 odd-even-transposition sort was not provided.

(Moore2000) discusses the impact of the parallel computing labs in her course. In general, students responded to the labs positively, and felt that labs increased their knowledge significantly.

(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 programs 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.

Citations