BuffaloBlog

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.

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.

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.

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.

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?

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.

One of the things that I don’t like about LaTeX is that the thing you distribute – usually a PDF – is not the same thing you edit. This means that if you ever lose the source files, you can’t rely on just redownloading the version you posted on your website or emailed to your friend or whatever. I keep my LaTeX files in a backed-up source control system, but still I worry.

But I was pleased to discover that PDF files actually supports attachments, so there’s really no reason for me to ever distribute PDFs without the accompanying source ever again. With pdftk, attaching a files is as simple as:


pdftk source.pdf attach_files source.tex source.bbl output output.pdf


I really wish that pdflatex had a flag to do this for me, especially since that way all my weird styles and other auxiliary files could come along for the ride easily. But a quick shell script should suffice for my use case easily enough.

So this summer I worked at a video game company to try and get a feel for what skills are important in that field. I figure every CS teacher might not have time to wander off to industry for a summer, so while I was there I did a study about what game developers look for in a new hire. I interviewed some developers, managers and artists and then used that to build an online survey.

For the curious, here is my paper as it will be published in SIGCSE 2010. There was nothing earthshaking here, although I was impressed about the extent to which the people I talked to emphasized that people skills were at least as critical as the technical side of things.

There is a big chart a few pages in that summarizes the results.

…where hubris has driven many before me.

So for a while I’ve been wondering, “Is it possible teach P/NP to introductory CS students?” Taking as a starting point that your students understand Big O, it’s not difficult to get to the definitions (assuming you are willing to call NP the set of polynomial time verifiable problems). But that always seemed to be a cop out, because it really ignores what I think is the actual neat part of P/NP – the fact that NP-complete problems exist. For that you need Cook’s theorem, and that is a sticky wicket indeed.

I’m taking a course on education this semester, and we have to build a couple lesson plans. So, just for fun I decided to try to see if it could be done.

Foolish foolish me. I just got an email from my professor saying that a) she had no idea what my lesson was about and b) it would likely need to be re-worked considerably if I was going to get credit. Not exactly what you like to hear after you’ve already devoted more time than you really should to a project. Not that I can really disagree – it’s just too much for one lesson I think, no matter how you cut it.

So I’m gonna rework it to just talk about P/NP and not Cook’s theorem. You all can feel free to mock me. Even though I really think my extended Sudoku example is cool, and there’s really no point to it if you don’t do Cook’s theorem. But just for posterity’s sake I’m tossing up my slides (scroll to the end to see my sketchy notes) and handout. If you can think of any shortcuts that I missed, do pass it along. Or theoretically unconscionable mistakes…anyone who reads this blog knows I’m not much of a theorist.

Maybe if I completely reworked it to start with Cook’s theorem, and then moved to P/NP from that…it really could be done, maybe. But I’ve got no more time for more time sacrificed to pride right now.

So those of you who have been chatting with me recently know I’ve had my eye out for a layperson level introduction to what P/NP is. Why do I care? Well, this is something high school students have heard of and occasionally ask me about. I feel like the idea isn’t really THAT hard but almost every explanation I’ve looked at tends to require knowledge about things like nondeterminstic Turing machines.

So I ran across what seems like the best intro I’ve read thus far. It’s a little light on the exact details and tends to assume you understand what “polynomial time” is, but it does make things sound cool.

If you are aware of a better explanation, I’d love to hear it:

http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

So I just passed my qualifying exams. These are a traditionally significant hurdle in the Ph.D. process. The point of qualifying exams is to ensure you’re familiar with your area’s literature and can do research. Every Ph.D. program is different but for me the quals consist of:

1. A 8 hour written exam where you answer 4/7 essay questions, drawing on the quals reading list
2. A 4 hour written exam where you answer a personal question, drawing on the quals reading list and ~20 selections you worked out with your advisor
3. A 1.5 hour oral exam where you present your research to a committee of 4 faculty and respond to their questions

I just finished my oral and officially passed (the professors were actually less aggressive than I thought they would be…it wasn’t too bad). Yay! Now time for some slacking…