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.

Training of the Teachers: 2015

A highlight of camp TechKobwa again this year was the 3.5 days in Training of the Teachers (ToT) from August 4 - 7.  With TechKobwa, we hope to interest girls in technology studies and build their self-confidence, but we also want to have farther reaching impact for building capacity.  Therefore each participating school sends six girls but also the ICT teacher.  We hope to create a critical mass within participating schools that will have sustained impact beyond the few girls who come to camp.

The teachers arrive several days earlier than the girls and undergo intense training, learning methods for teaching ICT and self-confidence.  In three days the teachers take all the modules the girls will take during their five day camp in addition to learning other topics applicable espe to ICT teachers, such as how to maintain a computer lab.  The ICT teachers teach many modules to the girls, though they may have only learned the material a few days before teaching the subject.  This gives teachers the opportunity to learn new material and techniques and practice these techniques with a mentor present.

Our training included teachers from 10 schools across Rwanda, 5 mentors from Creation Hill Rwanda, 4 Peace Corps volunteers, 3 people from Michigan State University, a person from Peak Research and one from IBM.  Ice breakers and team-building activities help get such a diverse group comfortable working together as a cohesive team. 

  

 

So, Rusty from the Peace Corps, led the group through several effective exercises, using a rope as the common thread for each.  We jumped rope in teams of two or more. 

We saw how teamwork helped us defy gravity, provided our team member trusted in the support of the other team members.

And, we saw how our collection of talents created a strong network that allowed us to raise others with ease, surprising ourselves at the strength we exhibited as a team.

Blair and Rodney used Elenco’s Snap Circuits kits to teach basic electronic concepts.

 

Laurie taught many Computer Science Unplugged sessions, providing the teachers with material they can teach without needing computers or electricity.  Teachers learned interesting and fun ways to teach binary math, algorithms, and various sort algorithms. 

Here’s an example of an aid which can be used to teach binary math.  Prince and Theogene took turns explaining the topic to the other teachers.

Below the teachers are practicing a human version of a parallel network sort algorithm.  They began the exercise a bit skeptical but felt very surprised and triumphant when they saw the algorithm actually worked.

Teachers also learned programming in Scratch, a visual programming language designed to teach young people basic coding constructs by letting students easily write programs with immediate visual feedback based upon making “sprites” (animated characters) perform various actions.

I reviewed basic internet skills and taught a session on internet safety.  I also introduced the “Mission Innovation” project and familiarized the teachers with their role throughout the week, mentoring the girls on their research projects.  Sorry, there are no pictures but I couldn't act as roving photographer while I taught. (We do have pictures with the girls, however.)

Elisabeth and I also took the teachers through the “Life Skills” modules the students would take.  These modules strive to build skills that raise self-confidence.  We covered topics such as self-confidence, “Finding Your Voice,” written and oral communication, and goal-setting.  Teachers learned the importance of incorporating these topics and also techniques for helping build girls’ self-confidence and problem solving skills.

Elisabeth and KOICA volunteers introduced teachers to a program that teaches them  touch typing.

For teachers with no computers or projection equipment, Elisabeth showed them how they could create mock ups of a keyboard and common applications on rice sacks.  The mock ups allow the teachers to introduce concepts of browsers and the internet.  

Though it made for an extremely packed schedule, the ToT resulted in several teachers either teaching the material to the campers or providing translation from English to Kinyarwanda.

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.