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).
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
Would your KLA work if your students had the following constraints:
|•||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!)
Feedback: add your feedback here!
Use Notes: add your use notes here!
|•||Used on October 6, 2009, in a group of 60 students of Algorithmics at Utrecht University (author, Gerard Tel). Reactions of students, most: nice way of learning, allows for longer span of attention, helps to understand topic faster. But also: chaotic, time consuming.|
|•||Used on November 12, 2009, in a group of 25 students of Algorithmic Desing at Safarik University in Kosice, Slovakia (author, Gerard Tel).|
You or later users of the wiki can add links (that don't fit into the text above) to related discussions, papers, repositories, examples, etc.