Learning How Computers Represent Information

  

The third and fourth CS Unplugged lessons were about representing information.  We gave students abbreviated ASCII tables and they collaboratively decoded a brief text message – the TechKobwa motto “Girls love tech”.  Of course, several of them also took it upon themselves to decode my t-shirt. 

The rest of the third lesson was on representing numbers in binary, following the CS Unplugged curriculum.   I created two ‘flip boards’ as visual aids—one with binary dot-cards affixed to the board and construction paper cards that could be flipped to reveal or hide the card underneath, and the other with 0-cards affixed to the board and 1-cards that could be flipped to make any 5-digit binary number. 

Starting with the former, we gave the students binary “dot cards” and started them off counting up from 0 (all cards face down).  Most caught on very quickly.  A few required some extra help from their family leaders.  All counted from 0 to 31.   

 Then we substituted the dot board for the 0-1 board.  We also found it useful to add a strip showing the powers of 2 beneath the board positions to remind them of the position values.  Students were quickly converting from binary to decimal and back again.  Several volunteered to demonstrate their algorithms for doing so on the board.

The fourth CS Unplugged lesson started with a review and then dove into representation of images.  We passed around copies of the TechKobwa girl at different magnification levels to introduce the concepts of pixels and resolution.  These concepts were all the more real when used to explain why our Skype session from the afternoon before had been blurry. 

I simplified the “Kid Fax” from the CS Unplugged curriculum a bit so we could easily transmit images to Louise.  We first transmitted the resolution and then the run lengths for each row, inclusive of the length of the last run of white pixels, if any.  After walking through our run-length encoding of a simple 5x6 letter “a”, the students decoded the first “Kid Fax” to see the image it created.  Then they transmitted it to Louise, who was sitting with a blank graph paper outside the classroom where she couldn’t see the image, by calling out the series of numbers.  Each time they called a number, they waited for an “ack”.  When done, they were happy to see that she had exactly reconstructed the image from their transmission.

We ran out of time to decode the remaining “Kid Fax” images.  But I noticed many students working them out in their free time, curious to see what image they would find.  We sent the teachers back with materials for expanding this lesson to include representation of color images and creating their own images.

The lesson on image representation was a new one for TechKobwa this year.  Given the enthusiasm, it’s one we’ll want to expand on in future camps.  

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.

Learning about algorithms

The second full lesson of CS Unplugged focused on algorithms. In this lesson, students learned:

• A model of a computer system
• The concept of an algorithm
• What makes for a “good” computer algorithm
• Several algorithms and their costs

A computer system

We had a lot of fun first thinking about “Bean Cooking” algorithms.  Students first devised a bean cooking algorithm and then critiqued two alternative bean cooking algorithms that we acted out for them.  These examples let to discussions of "correctness" v.s. "costs".

Qualities to consider for a computer algorithm

Students worked in pairs to devise algorithms for calculating the minimum of a set of numbers and for sorting a set of numbers.  The "Decider" simulated a program and the "Comparer" simulated the CPU.

Roles of the Decider and the Comparer

Working out a sort algorithm

They practiced their algorithms in pairs and counted the work involved.  Most came up with selection sort for their algorithm — fine for a small data set — not so good for sorting ID numbers of 45000 MSU students!

The algorithms that they analyzed for time efficiency

In the process of discussing these algorithms, students learned important concepts of computing — sequencing, repetition, recursion, and modularization (calling other algorithms). 

We could have used another couple of hours to do justice to the sort algorithms. We showed them queue sort as a quick demo at the very end.  The demo really got them thinking — both about why queue sort is correct and the cost tradeoffs between it and selection sort.

How a computer represents information

In the first full CS Unplugged lesson, students learned:

• That computers represent all information as 0’s and 1’s (and why)
• How whole numbers are expressed in binary
• How characters are represented in ASCII 
• A magic trick!

We had planned to project this lesson until we learned that not all of the teachers had ready access to projection equipment at their schools and that the power in the classrooms was not sufficient to run a projector, in any case.  So we jettisoned the planned digital presentation and used blackboard and handmade flip-cards instead.

Blackboard at start of the lesson

We made flip-cards to use in teaching binary place value

The binary number 10101 is equivalent to the decimal number 21

Learning to count in binary

Students caught on quickly and were eager to share

Part of the ASCII Chart

Highlights of the lesson included: counting to 31 on one hand, and magically transmitting the month in which a student was born to Louise.  When the students learned the mystery code, they practiced it on one another. Working in pairs, they transmitted their age to their partner and then received their partner’s age in return.