[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. 
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)
It can be used to teach various CS concepts:
The printable lesson plan is available on google docs here.
please feel free to send me comments or thoughts.
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
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” again.
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.
Figure 5: The robot has moved left.
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)
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 swap instruction — it only swaps the cards if the larger card was on the lefthand side, such that after this instruction the larger card will be on the righthand side whether they were swapped or not.
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 figure 6 but, if we issue it again, nothing happens, the larger card remains on the right.
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
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 Conditional Swap.
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.
 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.