Teaching Algorithms

Introduction

One thing that we have found a fun side class is to teach a little computer science, specifically about sorting. The goal here is to give a flavor of computational thinking.

Sorting Straws

We learned early on that programming is breaking down problems into steps and teaching the computer how to accomplish each step. This exercise takes it to the next level. Bring a stack of randomly cut straws of different sizes. Explain that the only things you can do are:

1. Create a new pile
2. Select a straw by index from a group of straws
3. Compare 2 straws to see which is longer

Have the students write down (on paper) instructions on how to put the straws in order by size. This is usually super interesting by itself! Test each one by playing the role of the computer - this is best done by strategically ordering the straws for worst case brute force sorting to show that the easiest solution can be very bad in terms of points.

Discussing Performance

Have the students count the comparisons - each time you compare 2 straws things it costs them a point. Were all the solutions the same cost? Can anyone think of a way to improve the scores?

Advanced Algothms

If the above goes well you can teach them merge sort and show why it scores better.