FindSmallestCard

PD_ParallelDecomposition PD_ParallelAlgorithms TCPP_Algorithms TCPP_Programming CS1 CS2 DSA touch visual

Originally described by Gregory F. Bachelis, David A. James, Bruce R. Maxim and Quentin F. Stout (Bachelis1994)

No link to independent description publicly available. Please see details section for a synopsis.

Similar Activites

FindOldestPenny, FindYoungestStudent

Other activities by authors

(Bachelis1994): ParallelAddition. CardSorting, OddEvenTranspositionSort, SieveOfErastothenes

Details

From (Bachelis1994): The goal is to find the smallest card (e.g. lowest value card) in a collection of 16 cards. The notion of a “two-card comparator” is discussed as part of the process (e.g. input is two cards, outputs the smaller of the two cards). The processor therefore employs a series of “two-card comparators” to sort the set of cards.

Serial case:

Parallel Case

Two Students:

Four Students:

Eight students

The class then should asked to calculate the speedup of the parallel cases over the serial cases.

Constant Time Case

Another parallel algorithm can be demonstrated (Valiant1975). To find the minimum of n numbers (or n cards with unique numbers) employ n2 processors.

The case for n = 4 is illustrated below. Arrange the students into a 4 x 4 grid. The students along the diagonal are each handed a card. To do this activity with playing cards, we recommend that over-sized cards are used, or that numbers are written on a large piece of paper (front and back). In the example shown below (taken from Bachelis1994), the numbers 5, 1, 9 and 8 are employed. The initial grid is shown.

5 : - : - : - :
- : 1 : - : - :
- : - : 9 : - :
- : - : - : 8 :

The students along the diagonal each have a number, which they hold up, so that everyone in their row can see. The - denotes other students sitting at their desks.

For the matrix above, we expect the following students to raise their hands (‘denoted with U’):

5 : U : - : - :
- : 1 : - : - :
U : U : 9 : U :
U : U : - : 8 :

The student whose row has no hands raised is holding the smallest number. In the above scenario, that student is the one holding the number 1. That is therefore the minimum number.

From (Bachelis1994): The value of this exercise is that “even though each processor knows very little about the global picture, by acting in concert they can solve the problem at hand”.

To achieve this with 16 numbers, there can be four contests each with 4 numbers, followed by one final contest with the final four numbers.

CS2013 Knowledge Unit Coverage

PD/Parallel Decomposition

Core Tier 1:

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

Core Tier 2:

4. Parallelize an algorithm by applying task-based decomposition. [Usage]

PD/Parallel Algorithms, Analysis & Programming - Core Tier 2

3. Define “speed-up” and explain the notion of an algorithm’s scalability in this regard. [Familiarity]

4. Identify independent tasks in a program that may be parallelized. [Usage]

6. Implement a parallel divide-and-conquer (and/or graph algorithm) and empirically measure its performance relative to its sequential analog.

TCPP Topics Coverage

Programming Topics

Algorithms Topics

Accessibility

The visual aspect of this activity may make it less accessible for blind students. However, there are special decks of cards that have Braille printed on them. This will allow blind students to participate equally in this exercise.

Assessment

Unknown. However, the related activities have assessment.

Citations