The second full lesson of CS Unplugged focused on algorithms. In this lesson, students learned:
- A model of a computer system
- The concept of an algorithm
- What makes for a “good” computer algorithm
- Several algorithms and their costs
|A computer system|
We had a lot of fun first thinking about “Bean Cooking” algorithms. Students first devised a bean cooking algorithm and then critiqued two alternative bean cooking algorithms that we acted out for them. These examples let to discussions of "correctness" v.s. "costs".
|Qualities to consider for a computer algorithm|
Students worked in pairs to devise algorithms for calculating the minimum of a set of numbers and for sorting a set of numbers. The "Decider" simulated a program and the "Comparer" simulated the CPU.
|Roles of the Decider and the Comparer|
|Working out a sort algorithm|
They practiced their algorithms in pairs and counted the work involved. Most came up with selection sort for their algorithm — fine for a small data set — not so good for sorting ID numbers of 45000 MSU students!
|The algorithms that they analyzed for time efficiency|
In the process of discussing these algorithms, students learned important concepts of computing — sequencing, repetition, recursion, and modularization (calling other algorithms).
We could have used another couple of hours to do justice to the sort algorithms. We showed them queue sort as a quick demo at the very end. The demo really got them thinking — both about why queue sort is correct and the cost tradeoffs between it and selection sort.