Learning About Algorithms

The first two CS Unplugged lessons introduced students to concepts of algorithms.  We first illustrated concepts of inputs, outputs, and instructions via several “bean cooking algorithms.”  To help students appreciate the difference between “correctness” and “efficiency,” we demonstrated two hypothetical algorithms.  The first was obviously incorrect (made with oil, sugar, and beans, refrigerated instead of cooked—it had them in stitches—what do “muzungu” know about cooking beans?).  The second produced cooked beans, but one bean at a time—they got an even bigger kick out of this example.  But it got them thinking.  Given enough time, water, and fuel, the algorithm produced a bowl of cooked beans; but no one would waste the water and fuel to cook beans like this in Rwanda! 

We followed ideas in the CS Unplugged curriculum to get students working out algorithms for finding the minimum of a set of cards and for sorting them.

We phrased the exercises as a game played in teams of 2.  One student of each team played the role or the "Decider" and the other of the "Comparer".  

The rules of the game:
The decider could (1) arrange the cards as she wished, but never see the number on the front of the cards; (2) show any two cards to the comparer and ask which was smallest.

The comparer could (1) only point to the smaller of the two cards when asked.

The goal of the MIN game:  The decider must learn the minimum card without ever looking at the numbers on the cards.

The goal of the SORT game: The decider must sort the cards from smallest to largest without ever seeing the numbers on the cards.   

Not surprising, all groups used a linear search algorithm to sort the cards.  So in our second CS Unplugged lesson, we started by counting the cost of linear sort (as a function of the number of cards).  We estimated the cost to sort PINs of  about 45 K MSU students.  The could easily see that this algorithm was not practical even for sorting MSU student PINS, let alone the population of Rwanda. 

There was time for only two more sort algorithms.  I demonstrated a few runs of quick sort with 8 cards, while the students counted the costs. They could appreciate the savings after their experience linear sorting just 6 cards.   With more time, we would have have them all practice it and averaged the cost over all the trial runs.   But I also wanted them to see a parallel algorithm, so we skipped this planned exercise.

With just 5 minutes to go, six brave volunteers got a chance to try out a 6-input parallel sort network.  It took them a couple of tries to work out the kinks so they could reliably sort themselves.  We could have used a few more networks to give everyone a chance to try it, and to race a couple of teams.

These lessons provided us the opportunity to illustrate and motivate important algorithmic constructs: sequential execution, choice, repetition, recursion, modularization, and parallel execution.  Students saw several of these again in the modules on Scratch.