Tuesday, August 5, 2014

Learning about algorithms

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.

No comments:

Post a Comment