Tonight went well. I mentioned AI previously, but another course I'm teaching this semester is CS101. This is not like the ACM CS1, but more like CS0 – a very broad introduction to computer science for non-majors and majors with limited prior experience. It's a fun concept; we do a little algorithmics and problem-solving, followed by a brief survey of all the major topics in CS: databases, networks, languages, AI, etc. There's a bit of programming here and there – just to make the algorithmics more concrete – but that stuff doesn't begin in earnest until CS102.
Anyway, the sequence I'm following begins with algorithmics and pseudo-code. I'm just trying to convey the concept of what an algorithm is, and what it means to specify an unambiguous, step-by-step method. This can be incredibly difficult for someone who has never thought about things this way before. Everyone encounters tasks like searching, sorting, and path-finding in their daily lives, but most have no idea how these things actually are accomplished. And when you write down a multi-step procedure with a while loop and an auxiliary variable – just to find the largest number in a list – the uninitiated get justifiably annoyed. They protest, “Anyone can see that the largest number in the list (33 21 73 86 23 51) is 86... just look at it!”
Over the years I have encountered and developed several prop-based methods for conveying these and other complex ideas in computer science. One great source has been the Computer Science Unplugged project in New Zealand. I really believe that manipulating small props can help people understand things more concretely than chalk or markers or even computers.
Today I brought in 10 large index cards (about 5×7 inch) with one word written large on each card. I chose words with a food theme: Apple, Banana, Cilantro, Dates, Eggplant, etc. I began the lecture by placing 6 of the cards in arbitrary order on the chalk tray at the front of the room. Above them, I wrote the numbers 1 through 6. Nobody had any doubt that they could arrange the cards in alphabetical order.
So then I imposed a small restriction: you're not allowed to slide the cards around on the tray; the only operation you can perform is swapping two cards. So I went around the room asking which two cards to swap (i.e., swap #1 with #3, or swap #4 with #5), with the aim of bringing us ‘closer’ to alphabetical order. As people called out pairs of cards, I swapped them, and eventually they were alphabetized. Distributed computation!
Next I tried to examine what led us to choose the pairs of cards that we did. In many cases, people chose pairs that would place cards directly into the positions where they belonged. For example, if Apple was #4, then they would swap #1 and #4 so that Apple would become #1. Although this is an efficient strategy, I actually tried to discourage it because it meant that they had already sorted the words in their heads and were just trying to make what was on the board look like what was in their head. The strategy is not ‘blind’ in the way that an algorithm must be.
Eventually we hit on the fact that you could arbitrarily choose any two cards that are out of order (relative to each other) and swap them. After that step, the number of out-of-order pairs necessarily decreases. So if you continue doing this – again, choosing completely arbitrarily – eventually you'll hit a point where there are no more out-of-order pairs, and that means the cards are completely sorted. Although inefficient as an algorithm, this is pretty sophisticated reasoning!
Next I wanted to demonstrate the sense in which I mean that an algorithm must be ‘blind’. To do this, I sat in a chair facing the students, so my back was to the board. I asked a student to come up and choose any 4 cards and put them in any order on the board, under the numbers 1 through 4. I was not allowed to see the cards, and the other students would watch my helper to ensure her honesty. What ensued was reminiscent of the game “20 questions,” although I guess it was actually just 5 questions. It went like this:
Are #1 and #2 out of order? Yes.
Please swap #1 and #2. Ok.
Are #3 and #4 out of order? No.
Are #1 and #3 out of order? Yes.
Please swap #1 and #3. Ok.
Are #2 and #3 out of order? No.
Are #3 and #4 out of order? Yes.
Please swap #3 and #4 Ok.
And now, as if by magic, the words were suddenly in alphabetical order. I had caused it to happen by asking my helper extremely simple questions and giving her extremely simple instructions – without once looking at the board or knowing what words were there. This is actually fairly impressive – and I wasn't afraid to tell the students when to be impressed! ;) (For those in the know, this was a 4-element merge sort.)
I went through several more exercises like this, and eventually was doing a binary search in the same ‘blind’ way. Does card #5 say ‘fennel’? No. Does the word on card #5 come before fennel in the alphabet? No. Does card #3 say 'fennel'? And so on.
At any rate, I'm telling this story because I really felt that the technique was successful – in a way that just writing on the board is not – at conveying the concept of what it is like to design and specify algorithms like these. The completeness of your case analysis matters when you can't see the input data. And when your assistant will respond only to the most rudimentary questions and commands, you have to enumerate every little step.
