Robots Sorting Cards: Computer Science for Kids by@avishalom_

May 1st 2019 442 reads

*[TL; DR! If you just came here for the printable lesson plan:ย **Here it is**]*

This activity was developed to give visiting groups of school kids CS content. Otherwise it is just a tour of the architecture and office amenities. [1]

Below is a 1โ1.5 hour lesson plan that can and has been tailored to suit kindergarteners and high-school seniors. It was developed and field tested over the course of several years and tried on hundreds on visiting students with enthusiastically positive results.

*(Full lesson plan illustrated and linked below)*

**A general discussion**ย about whatย**sorting**ย is and why it is central to many solving many problems in CS.

Illustrating sorting by handing out aย**dictionary**ย or aย**paper**ย**phonebook**ย to a volunteer and asking them to look up a name or a word.

Then, ask for anotherย**volunteer**ย and ask them to find aย**specific phone number**, or aย**definition**ย that contains a specific word.- Handing out
**ย 5โ6 cards**ย to each group of kids (make sure there are no cards with the same number) and ask the kids to take turns laying out the cards in random order andย**sorting them**. - A discussion about what a isย
**program: a series of instructions.** - Older students can benefit from a short discussion about what anย
**algorithm**ย is (the idea behind the program) โ what was yourย**plan**ย to sort the cards? **Introduction**ย to the โrobotโ paradigm with a small instruction set**(move left , move right, swap)**

Lay 3 cards out, thenย**write the โprogramโย**that causes them to be sorted.**One student writes the instructions**, anotherย**plays the robot**.(and either the first or third student reads the instructions to the robots, everyone else makes sure instructions are followed.)- Introduce the
**ย โconditional swapโ**ย (swapping onlyย**if a specific side is bigger**)

Now, the target is to write aย**general programย**that can deal with any input. (the cards are randomly**ย laid out after the program**ย was written).;

Add another role now, a student who tries to reorder the 3 cards toย**generate an input that the program failsย**to sort. - Write aย
**MAX**ย function and compose theย**SORT**ย program using that.

**It can be used to teach various CS concepts:**

- Coding (A series of instructions)
- Edge cases, starting conditions, assumptions and clear definitions. (can a robot fall off the edge?)
- Algorithm design (as an abstraction of the method from the instruction)
- Debugging and adversarial input (can you find a counter example.. )
- Sorting methods
- Composing a function of other functions.
- Computational Complexity (High school seniors can calculate the number of actions as a function of the number of cards)

The lesson plan

The printable lesson plan is available onย google docs here.

please feel free to send me comments or thoughts.

Getting started, Illustrated breakdown

See full lesson plan for details, but just to get you started here is the gist:

Break the class into groups of 3โ4 students each

**Known Input, play-by-play**. First, shuffle and lay out the cards, then one student takes instructions and follows them one at a time. (no need to write the instructions.)**Known Input, all-at-once.ย**Again, lay out the cards first, but now write the entire set of instructions.**Unknown input.ย**We introduce a new instruction โConditional Swapโ Now the students must write the entire program (for 3 cards) before the cards are shuffled and laid out.**Adversarial input.ย**Rather than shuffling the cards, the students try to find an order for which the program from step 3 wonโt work.

Start by handing cards out to the students, 4 or five cards will do.

One student plays the robot. The robotโs hands are placed on two adjacent cards. The others will take turns giving instructions.

The goal is to sort the cards.

The robot only knows three instructions :ย **Move Left**,ย **Move Right**, andย **Swap Cards**.

The โrobotโ should react to every instruction, without waiting. later you can ask them to write all the instructions in advance.

*So if we start out like this.*

Figure 1: At the start, the student who plays the robot, touches two adjacent cards and awaits instructions.

*The first instruction might beย **โMOVE RIGHTโย **and will result in this.*

Figure 2: The student emulates moving right by shifting the hands, the right hands moves to touch the next card, and the left hand moves over and now touches the card previously touched by the right hand.

** โMOVE RIGHTโ**ย

Figure 3: After the second โmove rightโ

*Now we have to swap the cards. soย **โSWAP CARDSโ*

Figure 4: We have placed the 7 in its final place. we will now have to rearrange the 3 and the 5.

*โMOVE LEFTโ*

Figure 5: The robot has moved left.

*โSWAP CARDSโ*

Figure 6. Now the cards are sorted.

Same as step 1, but now the series of instructions is written down, after seeing the cards. Then the instructions are read out one by one, and if at the end, the cards are sorted, the mission is a success.

In the above example, with the above starting conditions. an example program might be: (Robot starts on the two leftmost cards)

*Move Right**Move Right**Swap Cards**Move Left**Swap Cards*

- The goal of this stage is to convey that the robot follows instructions and does not โthink for itselfโ. It is sometimes entertaining to seed this interaction by suggesting that the kids being the robots try to do what people tell them, not what they mean.
- Sometimes chaos ensues, this is great, encourage it. Here are a few examples below, Iโm sure others will come up, keep it playful, but it is very easy to steer the conversation into various topics that relate to computer problems.
- If in one group,ย
**a robot โaccidentally fallsโ off the tableย**(apparently this is hilarious๐คท) because 5 different people were yelling โmove rightโ and it moved right 5 times โ you might talk about the problem of communication protocols, the Byzantine Generals Problem. (and then close it off by saying โ*ok, for now, only one person gives instructions. and each instruction is only carried out onceโ*) - If students start arguing about โ
*Whose left,*ย*my left or your left**?**ย ascending or descending order**?*โ you can lead a short discussion about assumptions in programs, the need for nomenclature and common language, unambiguous instructions etc. (and close it off by saying โ*from now on, left means the robotโs left, and sorted means the largest card is on the right, the robotโs right*โ) - If a robot goesย
**off the cards**, orย**doesnโt start in the right place**, so step 2 is all messed up, you can discuss assumptions, and verification of initial conditions. (and close it off by deciding on some convention of where the robot starts.) - Someone may raise the point thatย
**a 3 of diamonds canโt be compared with a 2 of spades .ย**This is a great segue into a discussion on comparisons, assumptions, removing ambiguity, and common language. Also how do you decide on the sort order of items that are equal?

What if the instructions are first sort by suit then by number, or just by suit? (we can close off this discussion by saying we only care about numbers, and make sure that the cards handed out to the groups have no duplicates,. But whatever the decision, it doesnโt affect the program as long as we can all agree what the correct ordering should be after sorting.)

*This step is usually too advanced for 6-7 year olds. (there is enough material above for a full lesson for younger students.) YMMV about the age, your call.*

For this step, either define the problem asย **sort the cards**, andย **start with 3 cards**, or for a younger group, define the problem as extract the max โ put the largest card all the way at the (right) end.

We must also introduce theย ** conditional swap**ย now. This instruction replaces the previousย

If we issue the instructionย **โConditional Swapโย **when the table looks like it does inย ** figure 5ย **above, the cards are swapped and the result is as seen inย

This exercise is the main part of the lesson, the groups will try and fail several times.ย **Do not skip this**, let the groups come up with ideas, walk around the room as they do so. Figure out which group has an idea that works on most but not all inputs. Bring that program up, write it on the board. Show how it works on the input that it was tested on, ask other groups if they can show an example of โinputโ (card order at the start) for which this fails.

An example program that works on most inputs (for**ย three cards,ย **starting on the two leftmost cards) might be

*Conditional Swap**Move Right**Conditional Swap*

It will work on [2, 3, 4], [2, 4, 3], [3, 2, 4], and [4, 2, 3]

It will not work on [4, 3, 2] and [3, 4, 2] .

For it to work on those, we need to add aย ** Move Leftย **and aย

But how can we be sure it is right?

One way is to test all possible inputs.

Testing all possible inputs for sorting is only feasible on very small inputs, but it is a super valid way to prove that our program that sorts 3 cards is correct (no matter which order the 3 cards are presented in).

At this stage we can talk about theย **Algorithm**, orย **General Ideaแตแดน**ย . Up until now we wrote a series of instructions to deal with specific input, now we must come up with an idea that will work on any input. We must be able to reason about the problem in an abstracted way.

For example, we can break the problem down into two steps.

Step 1. make sure that the largest card is placed in the rightmost position

Step 2. make sure that the last two cards are sorted.

Step 1 may be achieved by starting at the leftmost location, performing a conditional swap, then moving right, one step at a time, each time performing another bubble sort. by the time weโve reached the end (in the case of 3 cards this takes a single move) we can be sure that the largest card is in its place. (because no matter where it started, at some point the robot got to it, and from that point on, it kept moving it right, by swapping it).

Step 2 is easy, just move left to get the two cards, and conditional swap them.

In general if there were more than three cards, weโd add a step similar to step 1, move the second largest card to the second spot, etc.

Weโve just rediscovered bubble sort.

Theย printout lesson plansย contain other expansions, such as computational complexity. etc. It also suggests when and how to move to more cards. Enjoy. (and lmk if you have comments.)

Thanks to Mark Dittmer for the initial idea and discussions around development, and Sergei for helping develop the delivery.

This program is being maintained and delivered by the Laura and the Toogler (Teaching Googler)-WAT team.

[1]ย At the Google office in Waterloo weโd get a lot of requests for school tours. School kids donโt really appreciate the design philosophy expressed with a new-glass-and-steel-decor atop a century old industrial brick building; and while the lounge with a playstation and arcade games is a cool impressive feature, it isnโt really worth the trip. Some of the teachers were impressed with the micro-kitchen budget, but kids have no idea what cashews cost.

Join Hacker Noon

Create your free account to unlock your custom reading experience.