Mike Hewner's Homepage

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.