This segment is intended to show that the same task can be completed many different ways, with some methods being better than others. We'll learn about algorithms, including their speed and efficiency by making butter & banana sandwiches as well as sorting students and finding the most efficient way to fold paper!
Supplies:
Butter & Banana Activity:
6 slices of bread (some may get destroyed)
2 bananas
1 tub of butter
1 plastic spreading knife
Folding Activity:
1 piece of construction paper per group
1 piece of pre-folded paper for demonstration
Sorting Activity:Outline:
8 pieces of paper with ascending numbers (sequential or random)
This is a very important lesson for allowing the students to see that correct answers are not always "efficient" answers. To get the concept across, we will sneak the idea up on them. Begin by telling the students that this is a very special day. We're going to do some activities and try to guess what they all have in common. First, a little snack.
Butter and Banana:
This is a classic exercise, which is usually done with peanut butter and jelly. In our school system, we are increasingly finding that children have peanut allergies (even to the touch) so we have adapted this for butter and bananas.
We want this activity to show students the importance of being clear with their instructions. Knowing how to accomplish a task is not sufficient when that idea must be communicated with a machine. How might one translate thoughts into something that a machine is sure to understand?
Here, the instructor will seat the class in front of them, presentation style. The instructor will then spread all ingredients out, and ask if anyone knows how to make a butter and banana sandwich. Inevitably, several hands will go up. If no hands are raised, ask if anyone knows how to make a sandwich at all, or if anyone is willing to give it a try.
When your first volunteer comes to the front, have her sit with her back to you (preferably behind you, with her back also to the class). If you have the volunteer sit with her back to you while facing the class, the class may give her cues that help or hinder the process.
Now that your volunteer is situated, have her explain how to make a butter and banana sandwich. As the instructor, you will do your best to take her literally, messing the sandwich up intentionally when the instruction is ambiguous. As the first volunteer, she will probably be quite general, leaving several steps to the imagination. Here is an example of how it could go, and how the instructor might react:
Volunteer Says Instructor Does Pick up the bread Lift the whole loaf (or plate) of bread Put butter on the bread Lay the tub of butter on top of the bread stack Cut up the banana With peel still on, cut the banana in half Put the banana on the bread Place an entire half of the banana on the stack of bread Put the top on the sandwich Use the top of the butter tub to complete the stack
One might think they see how this is going, but students are often full of surprises. The second and third volunteers usually make huge improvements. The limiting factor to this is generally the bananas, which I will cut in half (either as part of the first try, or purposefully) to get more milage. In the end, I generally cut the successful sandwiches up and allow the students to have a quarter-piece. You can use your own judgement on that!
Once the activity has wrapped up, ask the students what they learned. Help them see that giving instructions to a finicky teacher is an awful lot like programming a computer. The coder may think they know what they want the machine to do, but if their instructions are ambiguous (or unclear, or incorrect) then they may end up with a surprising result.
Folding for Fun:
With this careful and clear attitude in mind, gather students into groups of 2-4. Give each group a piece of paper, and show them an example of what they're trying to make. Illustrate with your paper how the creases divide the paper into 16 squares. DON'T FOLD IT FOR THEM AT THIS TIME. Just show them the end result once it's been re-opened, and ask them if they can figure out how to re-create the look. If you feel it's necessary, you can provide each group with a paper that has been folded and opened, so they can inspect it as they go.Sorting it Out:
Give the class about 5 minutes to re-create the fold. If you see they have finished sooner, you can regroup at any time. Once the class has come back together, ask if anyone wants to share their folding method. Once they have, ask if any other groups have done it differently.
Send the students back to their groups to try again. Challenge them to find as many ways to fold the paper as possible. Have them try to keep track of all the different ways there are to fold that one piece of paper into the specific shape required. After about 10 minutes, gather them again and ask them how many ways they came up with. Try to find the group who came up with the most methods.
Ask the class what the most number of folds was that they were able to fit in. Then, ask what was the least number of folds that they could manage for the same pattern. Does anyone think they can beat either of those numbers?
Follow up on this activity by discussing the idea that the exact same thing can be accomplished with more or less work depending on the method that you use. Can your students think of any other place that this is true?
This exercise can be as simple or complex as your class can handle. If the students are young just explore different ways to sort numbers without getting into how fast or slow the methods are. With older students it's a good idea to go through the specific algorithms and use the algorithm names so that students can get ready to use the methods in coding activities.
Ask for 8 volunteers. Have your volunteers come to the front of the room and line up shoulder to shoulder facing the class. Give each student a number picked randomly from a pile and tell them to hold it in front of them. Let the class see that the numbers are all mixed up. Ask one student to come to the front to help you sort.
Ask the student to describe how she would sort the numbers if she was asked to do so. Often, the first volunteer will describe a method that requires human help ("I'd take the littlest one and put it there, then move this one between these two where it belongs...") In that case, it's a good idea to explain that a computer can only inspect one list item at a time, which means that it can't observe order without first going through each item individually and storing information. If a demonstration is necessary, describe a simple algorithm, like Insertion Sort, Simple Sort, or Selection Sort.
Insertion Sort
Selection Sort
Now, have the student try sorting the group using insertion sort or simple sort. Does the class have any other suggestions as to how the list could be sorted without going through the line directly from start to finish in just one go? As they suggest ideas, try to relate their discoveries back to algorithms that are fairly standard, such as:
Bubble Sort
Merge Sort
or Quick Sort
If your students are old enough to understand powers (at least what it means to square a number), you can take this opportunity to compare how quickly each algorithm sorts a list of numbers.
Start with a list of three. There probably won't be a difference in how long each takes at all. On a list of five, you may see a slight difference, but attempt to sort a list of eight students and see what happens!
What you will have stumbled upon is called the "complexity" of an algorithm. Essentially, that means that you can expect any given algorithm to perform at or below a certain number of steps, depending on the specific items being operated on. In our case, we can expect Insertion Sort to never take longer than it takes to compare each item to every other item in the list, for as many times as there are items in that list. That is to say, if there are X items in our list, we will compare each item to fewer than X other items, X (or fewer) times. Altogether, that's at most X*X steps, which is equal to X2. We call this "Big-O of X2".
Mergesort, on the other hand, still compares X items, but it only has to compare each item to about half of X each time through. That means for each item of the list, you're comparing to about half the items of the time before. This constant chopping in half is estimated to be a maximum complexity of "log X". Therefore, the complexity of Mergesort is "Big-O of X*logX", which is better than X2.
If you're running short on time, just allow the students to see that some perform better, some perform worse, and some are pretty similar...but they all do the same thing in the end!
Here's an example comparison:
Helpful resources:
Graphic Sorting Algorithm Animations
Sortlab Applet
