CS Unplugged is the source of many of my activities and demonstrations for introducing concepts in computer science. I recently found that Tim Bell (University of Canterbury, New Zealand) delivered a Google Tech Talk [50 min.] about the project. Here is a much shorter video [1:44] just on the sorting network activity. Watching the kids put themselves in order is pretty amazing, once you get past the silly-looking school uniforms.
Earlier this week, I had an array of students model the gnome sort at the front of the classroom. It really is the simplest sorting algorithm. They stood in some arbitrary order, then I handed the left-most person a page with these instructions:
If there is no one to your right, pass these instructions to the person on your left.
If the person to your right is shorter than you, pass these instructions to the person on your left.
Otherwise, swap positions with the person on your right (but keep the instructions).
Go back to step 1.
They tried it out, and before long they were standing in order by height. (The algorithm is written without a stop condition, so I had to be in the right place as a sentinel.) The follow-up questions: how long did this take? How fast does it go if you’re already in the intended order? What if you’re in the reverse order? This one is simple to understand because there’s only one pointer, and all swaps are local.
Seems unlikely, but who am I to argue with the algorithm?
Dear Amazon.com Customer,
We’ve noticed that customers who have purchased or rated Computers & Typesetting, Volume B: TeX: The Program (Computers and Typesetting, Vol B) by Donald E. Knuth have also purchased Learning Microsoft Publisher 2007 Student Edition by Faithe Wempen. For this reason, you might like to know that Learning Microsoft Publisher 2007 Student Edition will be released on March 11, 2008. You can pre-order yours by following the link below.
The spring semester has wrapped, the grades are in, commencement was last Thursday. I’m still in that transition period between the frenetic end of a semester and the calm agenda of the summer. Maybe one thing preventing me from moving on is the pile of 4000 alumni surveys in my office, waiting to be sent out. I’m putting together a gaggle of student assistants later in the week to stuff envelopes. All in the line of duty (as chair of the outcomes assessment committee).
In late April, I gave another instance of my song-and-dance for non-majors, the presentation that I like to call “Adventures in computing.” In this case, it was part of “The College Project,” in which we invite a group of talented high school students onto campus once a week throughout the spring, to interface with professors in different fields. The idea isn’t explicitly to recruit them to LIU, but just to turn them on to higher education in general.
My presentation is just about 1.5 interactive hours (with props!) to convey a flavor of what computing is all about, and some of the “big ideas” that have come from it. Posted here are the slides and three handouts I used.
I wrote once before about staunch criticisms of Wikipedia I heard in a faculty development seminar. Since then I’ve been thinking about different kinds of knowledge, the nature of truth, citation, and verification.
In my professional life, I have used Wikipedia for background on some mathematical concept or details on some algorithm I’m teaching. In these areas, knowledge has a sort of self-consistency, and appeals to authority are worth very little. Suppose a Wikipedia article says, “The following algorithm searches for a number in an ordered list in logarithmic time,” and provides the algorithm. The claim is something that an informed reader can verify for herself, independent of any works cited. The algorithm either works or it doesn’t.
Now, suppose the article also claims that “This algorithm was invented by Charles Babbage in 1856.” It seems to me that this is an entirely different kind of knowledge. There’s no self-consistency, no way to verify this on its own terms. A citation — an appeal to authority — is critical. And probably the cited authoritative work will cite other works, and so on, like a house of cards.
This is a curious situation. We’re not marshaling evidence to support an opinion, but a claim of fact. It’s either true or false. And yet there’s no way to convince you either way except by appealing to a vast network of authorities.
To someone versed in mathematical logic and proof, this is deeply unsatisfying. And yet for most people, in most fields, I guess it’s just the nature of knowledge. If a vast network of authorities is the only handle you have on the truth, then I could understand getting a little anxious at the thought of Wikipedia entering that space.
I have distinguished mathematical truth (e.g., “the real numbers are uncountably infinite”) from historical truth (e.g., “Cantor proved the real numbers are uncountably infinite in 1891”). Perhaps the ‘hard’ sciences offer something in between. Part of the purpose of claims made in scientific papers is that the evidence can — albeit at great expense — be replicated by readers. But still there’s no self-consistency in, for example, biology. Maybe because it deals in knowledge about the real world, you can’t just consider a claim on its own and verify its truth.
Mathematics is not about the real world. If anything, mathematics is about itself. Mathematical truth is meaningful and accessible, but no amount of observing, measuring, or citing esteemed scholars will get you there.
In AI yesterday, I began describing genetic algorithms, a.k.a. evolutionary programming. I thought it important to get the essence of Darwinian evolution on the record too: descent with modification plus selective survival. I find that even among people who are generally supportive of evolution, and science in general, there is a lot of misunderstanding about how it works.
By watching the reactions on my students’ faces, I began to realize how brutal the whole thing sounds. Evolution has an enormous death toll. Lots of critters must die in order for the average fitness of the population to increase. This carnage, resulting from competition for scarce resources, is not optional; it’s essential.
It sounds all the more sinister when I mention that we will impersonate gods by applying our own selection criteria to the population. This isn’t natural selection, it’s artificial. You get to live and reproduce because you came closer to solving my problem than your peers did. In contrast, natural selection seems like a harmless truism: those who are good at surviving and reproducing are more likely to survive and reproduce.
Again, I tried to make the lecture more interactive with props. And nothing represents the concept of chance better than dice. Ideally, for an in-class demonstration, I’d like to leave nothing to chance. But in this case, I gave the dice to my students, put the success of my demo in the hands of Fortuna, and thus demonstrated my own ‘faith’ in the evolutionary process.
We ran through a simulation on the board, where I wrote 6 random 6-bit strings, and computed their fitness as solutions to a 0-1 knapsack problem with 6 elements. As my students passed and rolled the dice, we went through tournament selections, cross-overs, mutations, etc. The average fitness score of our offspring were clearly increasing compared to their parents. And I thanked Fortuna when, on the final roll of the die, a mutation flipped precisely the right bit to produce the optimal solution to the problem. (If that didn’t happen, I’d either have to go on to a 3rd generation, or be content with demonstrating just an increased average and max fitness.)
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.
Such a gloomy, rainy day. Perfect for staying home and hacking.
One course I’m teaching this semester is artificial intelligence. It has nothing to do with my usual areas of interest, but it has always had a special place in my brain. Especially the early symbolic stuff… it’s good fun, no matter that the grand claims for it never panned out.
So I decided, in my subversive PL geek way, to use this opportunity to introduce my students to Scheme. Specifically, I’m using the PLT DrScheme environment as a companion for my AI course. I know that true Lisp is traditional, but I was really seduced by Scheme in my younger years (until ML came along) and it has been a pleasure so far to come back to it. Plus I can set up some nifty cross-platform graphical simulation thingamabobs for my students, which they’ll appreciate.
I chose the AI book by Nilsson. In my first course, we used Winston, and Russell/Norvig seems to be dominant these days. But I’m never one to choose the dominant platform just because it’s dominant (haven’t owned a copy of MS Windows since version 3.0). I still have fond memories from Winston, and was a touch disappointed to find that it hasn’t been updated in all these intervening years.
Anyway, Nilsson starts out with a “grid world” inhabited by an intelligent agent (robot). The first task is to try to make the robot follow the wall clockwise around the room. In other words, the first smidgen of intelligent, goal-directed behavior is to avoid walking into walls. Impressive, eh? Next stop: The Matrix.
So, I used DrScheme to bring the grid world to life, and allow my students (who, after all, have no Scheme exposure at all) to dig right in developing little wall-following robots, just by typing stuff like (if (or s1 s2) ’north (if … )), where s1–s8 are sensors for the 8-directions (clockwise starting from north-west) that return true if a wall is detected. Once you set up your little if-then-else robot controller, you can graphically place a robot on the grid and have it travel one step at a time around the room. The code for my simulator is here: gridworld.zip; just open grid-main.scm in DrScheme. (Select the graphical language, with MrEd + MzScheme.)
Next we’re going to jump right in to two kinds of machine learning, first by inferring a decision tree from a set of examples (Quinlan ID3 algorithm), then by evolving robot behavior by genetic programming. Both of these can be readily applied to the robot world, among other applications.
The students seemed fairly excited by Scheme, on their first exposure. “It’s so easy,” one said, although admittedly he had just been watching me; they have yet to write any code on their own. Nevertheless, I was a little surprised by the enthusiasm. Good signs.
Sauerkraut
Rob
Rumble
Gavi Narra
Eugene Beauchamp-Simmons
link
Filed under 
Tagged 
Related posts • 
(For those in the know, this was a 4-element merge sort.)