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

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.

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.

## No comments:

## Post a Comment