Saturday, February 02, 2008

Shopping Period Lecture

One of the great Harvard "traditions" that I enjoyed as a student is the "shopping period". Students don't pre-register for classes; they spend the first week "shopping" whatever classes they like, and then choose what ones they want to take. (I'll talk more about the "politics" of shopping -- the pros and cons -- next time.)

Because of this, rather than dive right into material the first class for my Algorithms and Data Structures class, besides going over the syllabus and requirements, I do something that at least I consider fun. We talk about how to get fair bits from a biased coin. The class starts with the classic brain-teaser: suppose you have a coin that may be biased. How can we flip that coin to decide something fairly, like who should pay for lunch?

[The simple solution to this question, unless I'm mistaken, is commonly attributed to von Neumann.]

Starting from there, I try and take the class through a series of questions, leading up to how to efficiently extract lots of random bits from a sequence of biased flips. The method I base the lecture on is due to Yuval Peres [(see "Iterating von Neumann's Procedure for Extracting Random Bits," Annals of Statistics, March 1992)], and I learned about it at some point in graduate school at Berkeley. I try to run this lecture in a very back-and-forth manner, asking questions of the students and trying to get them to answer. (I also do this a bunch during the semester, with varying degrees of success...) Here's a version of my notes, with the various questions.

For the students who decide not to take the course, I figure at the very least they've learned something interesting that they can take with them. Also, it's conceivably the only time students will hear the word "entropy" in a computer science class, so I think it's worthwhile for that alone. Somehow, this problem fascinates people. Way back when I had more energy, I wrote a Dr. Dobb's article on it to show it to a wider audience, and there's been lots of related research on the problem. In some sense, this problem is the pre-history of all the randomness extraction work that has come since.

1 comment:

Deniss said...

Could I ask how long is the list of subjects they can choose from?
In our university the same approach is applied, but (from my point of view) the list is too short so there is no real freedom to select lectures to visit