An offline activity for teaching CS concepts: programs, algorithms, sorting, assumptions, correctness, computational complexity etc. etc. Requires: pen, paper and a deck of cards. 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] [TL; DR! If you just came here for the printable lesson plan: Here it is ] 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. A typical lesson includes: (Full lesson plan illustrated and linked below) about what is and why it is central to many solving many problems in CS. Illustrating sorting by handing out a or a to a volunteer and asking them to look up a name or a word. Then, ask for another and ask them to find a , or a that contains a specific word. A general discussion sorting dictionary paper phonebook volunteer specific phone number definition Handing out 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 . 5–6 cards sorting them A discussion about what a is program: a series of instructions. Older students can benefit from a short discussion about what an is (the idea behind the program) — what was your to sort the cards? algorithm plan to the “robot” paradigm with a small instruction set Lay 3 cards out, then that causes them to be sorted. , another .(and either the first or third student reads the instructions to the robots, everyone else makes sure instructions are followed.) Introduction (move left , move right, swap) write the “program” One student writes the instructions plays the robot Introduce the (swapping only ) Now, the target is to write a that can deal with any input. (the cards are randomly was written).; Add another role now, a student who tries to reorder the 3 cards to to sort. “conditional swap” if a specific side is bigger general program laid out after the program generate an input that the program fails Write a function and compose the program using that. MAX SORT 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 please feel free to send me comments or thoughts. google docs here. 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 . 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, play-by-play Again, lay out the cards first, but now write the entire set of instructions. Known Input, all-at-once. 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. Unknown input. Rather than shuffling the cards, the students try to find an order for which the program from step 3 won’t work. Adversarial input. Step 1: Known Input, play-by-play. 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 : , , and . Move Left Move Right 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. “MOVE LEFT” Figure 5: The robot has moved left. “SWAP CARDS” Figure 6. Now the cards are sorted. Step 2 : Known Input, all-at-once. The first program 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 Discussion for Steps 1–2 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, (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 “ ) a robot “accidentally falls” off the table ok, for now, only one person gives instructions. and each instruction is only carried out once” If students start arguing about “ ” 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 “ ”) Whose left, my left or your left ? ascending or descending order ? 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 , or , 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.) off the cards doesn’t start in the right place Someone may raise the point that 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.) a 3 of diamonds can’t be compared with a 2 of spades . Step 3 — Unknown input, the first algorithm. 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 , and , or for a younger group, define the problem as extract the max — put the largest card all the way at the (right) end. sort the cards start with 3 cards We must also introduce the now. This instruction replaces the previous 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. conditional swap swap If we issue the instruction when the table looks like it does in above, the cards are swapped and the result is as seen in but, if we issue it again, the larger card remains on the right. “Conditional Swap” figure 5 figure 6 nothing happens, This exercise is the main part of the lesson, the groups will try and fail several times. , 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. Do not skip this An example program that works on most inputs (for starting on the two leftmost cards) might be three cards, Conditional Swap Move Right Conditional Swap It will work on [2, 3, 4], [2, 4, 3], [3, 2, 4], and [4, 2, 3] Step 4 — Adversarial input, try to break it. It will not work on [4, 3, 2] and [3, 4, 2] . For it to work on those, we need to add a and a Move Left Conditional Swap. Discussion for 3–4: 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 , or . 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. Algorithm General Ideaᵀᴹ 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 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.) printout lesson plans Credits: 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.
