Archive for January 2010

Thoughts on Lecture, Slides, and What We Take Away

Most of you have seen a presentation of mine. My usual presentation style involves big pictures and titles, the occasional joke, and every now and then a diagram to illustrate a point. I certainly like this style, and I know that I can at least be entertaining when I try. But I’ve come to believe it is not a style that really works for teaching.

The main problem as I see it is that you have nothing to take away. The slides are just props to the performance happening up front; they’re useless by themselves. And even if things have been video-taped and are available after the fact, all that detailed motivation and funny stories is just fluff the second time through. That said, your average “regular style” slide deck is pure torture to see live and only marginally better after the fact.

A good set of notes is one alternative and I have no beef with that form. But I’ve been thinking about an alternative, riffing on Tufte’s idea that a good visualization can convey plenty and also be the sort of thing you can take home with you. But the difficulty with these information-dense formats is that they are hard for novices.

I’ve been thinking about a presentation centered around a sheet of graphical notes (pdf). You could use something like prezi to zoom around the sheet, adding digressions and details and explaining. And the sheet acts as “cheat sheet” as well, providing a physical source for definitions and other details that may not have been internalized when they were presented. And then, when the presentation is done the physical artifact acts as a trigger – not only containing its raw summary text but also potentially the memories of the jokes and digressions and examples that came along with the presentation itself.

My first attempt at uploaded video

There are still quite a few problems here.

Also, I’m not sure that allowing me to do re-takes on my introductions is a good thing. I just never feel like I’ve done it properly.

Putting your best foot forward

So I’m going to introduce myself to the class I am observing.

Did it make anybody chuckle? Trying too hard?

Those who want the complete presentation (yes, with even more jokes) can see my slides including notes.

My First Android App: 10K Hours

Ok, for people who haven’t read Malcolm Gladwell’s book Outliers, it includes the idea that to be really good at something you must practice. It’s not exactly revolutionary, but what is interesting is that he puts a number to the amount of practice you ought to do: about 10000 hours to be world-class. Gladwell goes through a lot of examples – Beethoven, The Beatles, Bill Gates. Some people might argue with some of Gladwell’s specifics, but what really is clear is that these people did practice quite a lot before they did any of their really cool stuff.

Gladwell makes a somewhat provocative claim: that what we normally think of as “talent” is basically the opportunity and willingness to practice. Some have disagreed with him on this point, saying basically that he is engaging in wishful thinking.

But when you look at 10000 hours, I’m not sure wishful thinking is really the way I would describe it. Having the opportunity to get that much time to work on a particular skill – well it definitely speaks to a certain amount of freedom from life’s usual responsibilities. It may simply be that 10,000 hours is correlated with great talent because if you are less than supremely talented, around hour 5000 or so somebody is going to insist that you stop practicing and get a real job.

Anyways, this has all got me thinking of my own life and how little time there really is for reflective practice. I may be here at Georgia Tech “training” to become a teacher, but even with practice considered quite broadly I’m not getting many hours in on a daily basis. You don’t have to buy much of Gladwell’s thesis to imagine that maybe 1000 hours of practice on a valued skill would be worthwhile. I am not on track, in that regard.

So this is all to say that I built an Android App to help motivate myself. It’s pretty simple: you tell it what skills you want to practice, how many hours your goal is, and then it logs how many hours you put in.

10k-hours.png

The most motivating line is the one that says how many years it will take to reach your goal at your current speed. It’s surprisingly how easily that can exceed a lifetime.

Anyways, if you have an android phone and would like to try my app, go here. You can also get the source here: hours10src.zip.

Given some motivation, I could probably test this on a couple more emulated systems and drop it in the android marketplace. Would anybody out there in internet land like me to go through the trouble?

The Llamas of Computing: A P/NP Fairytale

As part of my continuing obsession, I had the thought that it might help things if I had a story that people could related to. One of the tricky things about P/NP is everything has non-obvious names and the relationships (i.e. problem reducibility, problem runtime) are not something non-CS people think about. I played around with a couple of metaphors and this one was the one I liked the most. My only regret is that there’s really no llama equivalent of a verifier.

My original thought was that I would use this story as an introduction, and then have it structure the rest of the lesson. Now that’s it’s fully written out I wonder if it’s a bit long and involved for that. A homework assignment beforehand? With a few questions at the end to make sure you’ve thought through all the details? Or is it just too patronizing to make people do homework with made up fairy stories?

Once upon a time, there was a giant mountain range. And in this giant mountain range there was city. And in this city was a tribe of people. And this tribe of people was called the Llama Scientists.

The Llama Scientists were a hearty people, and they loved nothing better than to travel out from their city and explore the mountains. The mountains were filled with treasures: gold, platnum, jewels, DVD players and boulders that were shaped like various celebrites – everything was out there in the mountians if you knew where to look.

But the treasures were all very heavy, and the Llama Scientists moderately lazy, and so all the treasure would have remained in the mountains if not for the Llamas. The Llamas could carry the treasures back to the city. But Llamas, not being very smart, had to have a path. And it was important that the path not be too long – otherwise there was no way for a Llama overburdened with treasure to make the trip back to the city.

So the Llama Scientists soon became great experts at finding short paths for the Llamas to take. And the city soon was overflowing with treasure. The city became as rich as a kingdom, and being like a kingdom, needed to have borders. And so the Mayor set forth a Mayorial Decree:

Let all the land to which a llama may traverse in a reasonable amount of time be called P (“P” being short for “Polynomial”, which means “short” in the Llama Scientists simple but beautiful language). P will be the kingdom of the Llama Scientists, this I decree.


So now the Llama Scientists had a kingdom called P. But the kingdom borders infurated the royal cartographers. Clearly, all the land that Llama scientists had found a short path to, that was in the kingdom P. And it might be reasonable to think that Llamas could not fly off to the clouds or cross over an ocean. But that still left a great big chunk of land that still might be in P, just no one had ever found a path yet.
Having nothing better to do, the called this mysterious land NP. They had names for the clouds and the oceans too, but those are not important for this story.

Let all the land to which a llama might traverse, but no path has yet been found, be called NP. NP is the mysterious land of possibility, because at any moment a path may be found that makes something that was in NP part of P.


As Llama Scientists scouted more and more, there were certain rich mountian treasures they longed to find a short route for. But as years of Llama Scientists searched for the paths and found nothing, the more pragmatic Llama Scientists started to believe there was no short path at all. But everyone was infuriated that there was no way to prove that no short path existed, not even for one mountian in the realm of NP.

It might have remained that way forever, were it not for one smart Llama scientist called Cook.

Cook was climbing a mountian in NP called “Satisfiablity” that had been climed many times before. But when he got to the top, he noticed something no one had ever noticed before. Coming down from Mt. Satisfiablity were llama paths: one-way llama paths that led from Satisfiability to the top of every other mountian in NP.

If a short path could be found for Satisfiability, a llama could travel from there to every other mountian in NP. So Satisfiability was “NP-Complete” in that a path for Satisfiability was a path for every other mountian in NP. If Satisfiability had a short path, then the kingdom of P encompassed all of NP.


Cook’s discovery was big news. But then other Llama Scientists noticed something interesting: certain mountians had short paths to the top of Satisfiability. A llama reaching the top of those mountians could quickly travel to Satifiability – and then to any mountian in NP. All these mountains were NP-complete as well.

Any mountian that has a path to a NP-Complete mountian is itself NP-Complete.


Many of the mountains that turned out to be NP-Compelete were mountains that people had been trying to find a path to for a long time. These were the hardest mountains in all of NP.

Most Llama Scientists believe that there is no pratical point in trying to find paths to NP-Compelete mountains, because so many have tried and failed before. So showing that a mountian is NP-Complete is almost like saying “there is no short path”.

But no one is really happy with this. If no short path exists to the NP-Complete mountains, it would be nice to prove that for sure. If there is a short path to one of the NP-Compelete mountains, it would revolutionize Llama science: all the treasures in all the NP-Complete mountains would be open to the Llama Scientists.

Llama scientists often say “Does P = NP?”. What they mean is “is there a short path to every mountian in NP?” If P does not equal NP, it must be the case that there is no short path to any of the NP-Compelete mountains.