Sunday, December 21, 2008

More experiments in algo-teaching

(ed. note: think of this as a 'theory'-chaser to take the bad taste of cricket-blogging out of your mouth)

Another experiment that I continued this time was a set of lectures on "fun topics". The idea is to convey some ideas about a fun topic in theoryCS without too much jargon, but with enough meat to indicate that there's something deeper going on beneath the fun stuff.

I run these lectures at the end of the semester (when everyone's worn out already :)), and throw them open to the general public: both times I did this, I got substantial attendance from people not in my class, and at least in one case, someone who attended the lecture last year actually decided to take my class this year.

Not all topics are amenable to such a treatment, but my hope is to build up a suite of such lectures: the nice thing is that they can then be reused for other venues: for example, I've given variants of these talks to freshmen and high school students, and will do an undergraduate colloquium in the math department next semester.

For all of these lectures, I've pilfered shamelessly from the original works, as well as great websites developed by the authors. This post can be viewed as a shout-out and a thank you.

1. Pancake flipping:
Brian Hayes wrote a great article on pancake flipping for the American Scientist. In it, he links it to the problem of genomic rearrangement, and in doing so, ends up with a beautiful tale of the interaction between theoretical problems and practical constraints, all told in context of a topic that everyone can relate to.

I made two-color pancakes in different sizes, and distributed them to the students at the start of class: I briefly described the problem, and let them go at it. It was quite entertaining, and put the more formal discussion later on in context.

2. Zero knowledge proofs
ZK proofs are great for this kind of setting: they are completely counter-intuitive, (and so have the 'bizarre' factor), and are easily explained using popular metaphors. I used Moni Naor's Sudoku demo page, as well as the version of the proof that involves slicing and dicing the puzzle. This was done with class participation (I was the prover, and there were multiple verifiers).

The second demo I ran was the Yao protocol for the Millionaire's problem (how do two millionaires determine which is richer, without either knowing the worth of the other). Again, I did this interactively with class volunteers and an RSA applet to speed things along. More details here.

3. Quantum Computing
No demos for this one, but I gave a crude high level view of what quantum computing is about (about one-step up from the "do everything in parallel" explanation). The main goal here was to convey the basic ideas of what a qubit is, what a quantum circuit looks like, and how the Bell inequalities show that quantum computing is much more bizarre than classical randomness. Here, Dave Bacon/Umesh Vazirani lecture notes proved indispensable, coupled with the Nielsen-Chuang book, and a recent blog post by Michael Nielsen.

4. Computational Origami
I haven't quite worked the kinks out of this one, but the basic idea is to demonstrate the principles behind computational origami (and where the 'computation' comes in) by looking at the question: What shapes can you make by folding, followed by a single cut.

There's a cool backstory to this: essentially the first example of such an algorithm was how Betsy Ross designed the 5 point star for the American Flag, and it lends itself to a nice demo in class.

Secondly, it's a classic example of resource-bounded computation: limiting yourself to one cut. Thus, it makes for a good illustration of how computation appears in all kinds of problems.

Thirdly, computational origami actually shows up in many real-world problems, most notable one involving folding mirrors for a telescope to be launched into space. If we're trying to convey a sense of computational thinking, this is a great example.

The actual problem itself was solved in this paper by Demaine, Demaine and Lubiw. Unfortunately, I have yet to find a way of explaining it that will make sense to non-expert geometers, and that's one weakness with this particular story: Erik's page has some nice examples to demo, but it's hard to convey the deeper algorithmics behind the problem.

Lessons learned:
• As always, know your audience. What works for a graduate class doesn't work for sophomores, and certainly doesn't work for eigth-graders :)
• Interactivity is key: if you allow people to participate, they're more involved, and will probably take away something positive
• Keep it light: resist the urge to get too mathematical. There are many beautiful topics in theoryCS that can be explained without jargon, and many others for which with some effort, jargon can be removed.
• A 'bizarro' factor helps: In general lectures that I've given, I find that presenting something completely counter to people's expectations catches their attention immediately, and leaves a lasting impression. ZK proofs have that property. Bell's inequality sort of does, but the impact would be more immediate if I could actually run a quantum experiment to demonstrate violation of Bell's inequality ;)
• Relate it to the real world: again, it's not enough to cite applications: one should try to show them as far as possible. In this regard, the Betsy Ross story is great, because it relates to something everyone (in this country) knows.
My goal is to add one or two such lectures to my arsenal each time I teach the class. For next time, I'm seriously considering running a live auction of some kind to demonstrate some concept in algorithmic game theory (suggestions on how best to do this are always welcome). Are there other such topics that might lend themselves to an entertaining, edifiying and educational experience ?

16 comments:

1. For high school students, I have done envy-free cake division:
http://en.wikipedia.org/wiki/Cake_cutting

I explain cut-and-choose using the the classic scene from the old TV show Friends

http://www.youtube.com/watch?v=98KZNd03l4U

The cut and choose part starts about at 3:30 in.

Then I have 3 volunteer students run through the 3 person algorithm on a real multi-layer cake, asking them to explain why they are not envious as the cuts are made. Then while the students eat the cut up cake, I tell them that they can work on the 4 person algorithm as a hard homework problem, and tell them that I will give them their PhD for an n person algorithm with the number of operations bounded by some function of n.

Cheers,
Kirk Pruhs

2. An auction in class is a fun idea. I'm not sure what sort of auction would help explain the computational aspects of game theory, but there's plenty you can do to illustrate the incentive aspects. A classic is to auction off a dollar bill to the class in several ways: as a first-price ascending auction, as a second-price one-shot auction, and finally (to make some money) as an all-pay auction.

In an ascending all-pay auction, everyone pays their bid, but only the highest bidder wins the dollar bill. The cute thing here it that bids will likely exceed 1 dollar, because at some point, people are already taking a loss, and would like to at least win the dollar to take a smaller loss.

3. Another nice example of ZKP is one where a blind buyer is trying to buy two identical but different colored pieces from seller.

Seller tries to convince buyer that they are indeed different in color. In every round buyer takes the pieces behind and shuffles them with probability 1/2, then shows it to seller and asks if they are shuffled or not.

I found this in a writing of anup rao http://docs.google.com/View?docid=dq6zxpq_473cvj8ggfx

4. Kirk: cake cutting is an EXCELLENT suggestion. My only worry with the friends video is that today's high schoolers probably have no clue what Friends was :)

Aaron: thanks for the tips on auctions. I'll definitely do something like this next year.

Anon: the blind buyer idea is a good one: I've used Coke/Pepsi tasting, which is a similar concept.

5. For an introductory talk on quantum computing you can play around with polarized light to get some of the ideas across. My typical set-up includes an overhead projector (increasingly hard to find), three sheets of polarizers, two beakers, and some high fructose corn syrup.
With the polarizers you can show the probabilistic and changing effects of measurements in different bases: 2 aligned sheets let light through, when rotating them the intensity decreases, until they are perpendicular and things turn black. Then, you can insert a 3rd sheet between the two and show how the 'measurement effect' of that one allows light to go through again. If you're really ambitious, you can also show how corn syrup can rotate the polarization of light, thus acting as a single qubit gate.

6. You could also explain RSA. I did this with a group of high-schoolers and it went over really well.

I used a phone-book for the analogy. To encode a letter, pick someone who's last name begins with that letter, and write down the phone number. One person gets a reverse-phone book to decode.

I then had them talk about the strengths and weaknesses of this approach (generating the reverse book takes too long) as a lead-in to the actual algorithm.

7. I had never seen that solution to the millionaires' problem before (though it is not Yao's solution...). On the same topic, you may want to check out the paper "Comparing Information w/o Leaking It" that discusses several other (simple) approaches to the problem.

8. I would agree on the "friends" comment. Nobody can remember leave it to beaver.

9. It seems like it should be possible to compile a whole video clip list. It would include a lot of Numb3rs scenes, of course (I especially like the episode that uses the art museum problem), but could also include the 2 boats clip in the Dark Knight for the prisoner's dilemma and I imagine other clips as well.

Also, Suresh, do you have any materials from these lectures to share so that we can borrow shamelessly from you? (: They sound great!

10. I just saw the Dark Knight ! which two boats clip are you referring to ?

And as for material, I linked to all the material that I use: the rest is just my own notes, and me waving my hands around :).

11. At the very end of Dark Knight (um, spoiler) the Joker tells each boat that if they blow up the other then they will be saved. Of course, it ends in the unlikely way (in terms of the prisoners' dilemma) where neither boat is blown up.

12. Oh dang. of course. I was thinking about the dilemma earlier facing Batman, of which person to save of the two being held captive.

13. And here's some discussion on the game theory of the scenario:

http://www.quantitativepeace.com/blog/2008/07/the-dark-knight.html

14. And here's the video of the scene. Isn't the internet great ?

http://www.youtube.com/watch?v=tc1awt6v2M0

15. You can also sort by height a bunch of students following different algorithms. I usually do it with freshmen and they have fun while learn insertion, selection, merge...

16. Hi:

Here are some fun examples that I have used in algorithms courses (undergrad and grad) over the years.

1) Cheney's card trick: Originally Cheney (apparently the first Ph.D. in Math from MIT) developed it as a trick done by two performers A and B. Initially, A is on stage, B is away. A gives a deck of cards and asks the audience to choose 5 cards from the deck. She examines them and selects one, shows it to audience and puts it back in the deck and leaves the other four cards on four vertical place holders on the table and leaves the stage. B then enters, looks at the four cards in display and announces the five card.

I perform this trick in my class as follows: I play the role of A, and my laptop will play the role of B (or vice-versa with a different applet).

One can show that the trick can be done with a deck of size 124 (but no larger) using Hall's theorem.

2) The next one superficially resembles the above trick. A pulls out the spades from a deck of cards (as usual B is away) and asks the audience to select 7 of them and hand it to her. A examines them and places them on 7 vertical place holders - all cards facing down - and leaves. B enters and can be questioned about any specific card - for example, is J of spades one of the cards in display? Since all the cards are facing down, B has no way of answering this question without a wild guess, so B is allowed to take one peek - he can choose to look at one of the cards and should then correctly answer the question.

The idea underlying this is Yao's perfect hash function (from the paper "Should tables be sorted?").

3) This one is performed with a deck of blank cards. Thus each card has a design printed on one side and white on the other side. There are seven vertical place holders for cards on the table. A gives four cards to someone in the audience, and asks him/her to place them in the first four slots so that each card has either printed side or the blank side facing front. Then A adds three more cards in slots 5, 6 and 7. Finally, A asks the audience to flip one of the cards after she leaves. B comes in and identifies the flipped card.

This one, of course, can be implemented using Hamming code.

It is somewhat interesting that they all have similar themes - two performers in which one of them is the computer, but based on very different models.

I have created a series of such tricks ahd have tried them at different times.