Recently Viewed: Home > Social Sort
 Social Sort

Social Sort

 Described by Gerard Tel (gerard@cs.uu.nl, Utrecht University), but taken from Sivilotti and Pike: The suitability of Kinesthetic Learning Activities for Teaching Distributed Algorithms (SIGCSE2007).

Overview To KLA

 Summary: Some 10 students come forward and get and index number (1 to 10 or 12) visibly attached, and a blind card from a deck. The cards must be sorted by bilateral encounters, where persons meet randomly in pairs, compare their card and swap when they are ordered differently than their indexes.
 The main challenge for the participants is to know when their current card is final (and then report it to the teacher).

Learning Goals:

 At the end of this exercise, students will...

 • understand that simple steps can be building blocks for different algorithms.
 • understand that termination of the process can be concluded from properties of the sequence of interactions.

 Course And Level: The activity was made up for a course on Algoritmics, taken in the 2nd or 3rd year, based on "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein.

 Class Size: Ten to twelve students can participate, the rest of the group can watch.

 Preparation Time: You should have a dozen of stickit notes with the numbers 1 to 12, and bring a deck of cards.

 Execution Time: Up to 10 minutes.

Planning For KLA
 Materials: Stickits, deck of cards.

 Preparation: Hardly necessary; I used it as an introduction to shortest path computations by Relaxations, as described by Corman etal.

 As always, read this description carefully and practice the KLA before using it in class!

Execution Of KLA

 Description: Each of 10-12 players gets a visisble number and one playing card from a normal deck. In a bilateral encounter, players i and j compare their cards, and exchange it if the ordering of the card is the opposite of the ordering of their indexes. A participant must report his (current) card to the teacher when he thinks that his current card is final.
 It can be proven that no encounter brings the state further away from sortedness (use the number of inversions) and also, that any infinite fair sequence will eventually sort the array. So, the activity can be an introduction to various techniques for reasoning about sequences of actions. The obligation to report the final card to the teacher stimulates to think about how finalization of the process can be concluded.

 I ran the activity in Slovakia (Nov 2009)

 Variants And Extra Topics:

Constraints On KLA

 • Limited Vision: If adopted sorting material is available (braille cards) the activity may work very well, because blindness naturally gives the idea of processing limited information in each step.
 • Limited Hearing: hearing-impaired can participate because the activity does not make use of sound communication, but the rules should be communicated in written form, of course.
 • Limited Mobility: The participants must be able to move to other participants.
 • Trouble Speaking: Participants need not speak at all.
 • Touch Aversion: In the basic form, no touching is required, just looking at each others card and exchanging.
 • Other: Not that I know of.

Pitfalls Of KLA

Feedback And Use Notes

 (don't give feedback on your own KLA!)