August 31st, 2010, 11:09 am PST by Greg

Earlier this year, Kat got invited to speak at a conference in England, which is awesome. What’s more awesome (from my perspective, at least) is that I’m not teaching in the fall. If you put two and two together, you can see that we have half of our trip to England paid for, and time to spend if we go.

So, we’re going.

We leave tomorrow, and are seeing London, Brighton (where the conference is), Barcelona, and a Mediterranean cruise. On the way back, we’re making a pit stop in Ontario to see my parents. All of that will take most of September: we return Sept 25.

I don’t have much to say about it at this point, other than this is why I haven’t been returning anybody’s emails: too much to get ready before we go, and no time to see anybody either.

We have given preference to hotels with internets, so there is some hope we’ll post some updates during the journey.

CMPT 470: feedback wanted

August 26th, 2010, 4:21 pm PST by Greg

Along with my first offering of CMPT 383, I just finished my 13th offering (!) of CMPT 470. I haven’t changed the backbone of the course much in that time: it mostly feels good to me, and other than moving with shifting web technologies, I haven’t felt the need to change the course style.

But now I’m taking a good hard look at the course. I still like the overall flow, but there are some things I want to change.

I did a survey of the current students to get some feedback, but they lack perspective, having just finished the course. I figure I can get some eyeballs from course alumni here and am looking for some more meaningful feedback.

Question 1: Weekly Exercises and Grading Scheme

When I did CMPT 383, I gave weekly exercises, thinking that they might feel a little bit hand-holdey for an upper-division course. Much to my surprise, they worked better there than they do in 120 and 165: more-senior students are in a much better position to appreciate the micro-lessons that the exercises encapsulate and better understand why they are helpful. It’s also a chance to give problems on everything, not just a few things in major assignments.

I have realized that I want to do weekly exercises in CMPT 470, replacing the three assignments. The problem is: the assignments are worth 30% of the course. The weekly exercises would receive minimal marking and feedback (likely marking scheme: 2=most/everything correct, 1=some stuff done, 0=little/nothing done). With that little “grading”, 30% is too much to give to them: 20% is more reasonable.

So, I have 10% of the final grade to reallocate somewhere. Any suggestions about where an extra 10% of weight should be distributed? (The old grading scheme is online.)

[To give you an idea, I’m imagining that some of the exercises will be like “learn these three important CSS techniques and use each to style this sample page”; “find security holes in this sample mini-app I have created for you”; “pick Rails/Django/whatever and do the tutorial on their site”; “deploy your tutorial code on your group’s web server”; “do something with jQuery”]

Question 2: Content

I have certainly done my best to keep with the times, and talk about new web-related topics as they have become relevant. But like I said before: the overall backbone of the course has remained the same.

Are there things that I should have spent more lecture time on than I did? Things that took up too much time?

I definitely want to move JavaScript stuff a little earlier in the course: it deserves to be at least a little more front-and-centre than it has been.

Question 3: Other Stuff?

I have a few other smaller tweaks in mind, and am open to other feedback.

In particular, I plan to (explicitly) open the technology evaluation to a wider array of technologies: JavaScript frameworks, databases. This past semester, I started to realize that the server-side frameworks (Django, Rails, Cake, …) are all fundamentally the same (at the depth that’s possible in the techeval). There are other pieces of technology that are more interesting choices at this point, and they might as well evaluate those.

I’m happy to take any half-baked thoughts on any of this here, or by email.

And that’s how you teach CMPT 383

August 22nd, 2010, 10:48 pm PST by Greg

I have now completed my first offering of CMPT 383, Comparative Programming Languages.

I had forgotten how much work a new course prep is, particularly as I am anal-retentive enough to not be able to make much use of any other instructor’s course materials. Other instructors just do things… wrong. The only way for a course to feel right is to do it my way, for myself. Giving lectures from somebody else’s notes is like wearing somebody else’s underwear: technically probably just fine, but you just feel dirty.

That’s not to say other people who teach the same courses I do do a bad job: they are generally excellent instructors teaching excellent courses. They just do it wrong, is all.

But, looking at my plan for 383, I came in pretty close to the plan. The final balance of topics was more like 6 weeks, 4 weeks, 3 weeks, but that’s astonishingly close for somebody who usually just stops somewhere around the midterm and thinks “does that feel like about half of the material? Okay good.”

Overall, I’m very happy with it. First offerings of a course are supposed to be bumpy and full of things that you wish you could have done better. Honestly, this was one of my favourite course offerings ever: there are tweaks I’d do for my next offering, but all are fairly minor.


  • The weekly exercises were (to my mind, at least) a total win. My goal throughout was basically to say “remember that thing I talked about this week? Practice it” and I think it worked for the students. I liked them to the point that I’m planning that every course I teach from now on will have weekly exercises, including 470. (More on 470 in a later post.)
  • Some of the more involved examples I put together were among my favourite learning objects ever. (God, I can’t believe I just used the term “learning objects“. I have become everything I hate.)
  • I think I actually convinced them that Haskell was practical. Was that irresponsible?
  • Prolog sucks, but I’m still convinced it’s a worthwhile exercise.
  • The “language concepts” section felt a bit like a laundry list of topics. I don’t know that there’s really any way around that. Maybe I could re-order things a bit so they flow together better.
  • The project was interesting for all concerned. I’d probably cut down to three or four language choices in the future, just to keep the TA from losing his mind.
  • I’m not particularly happy with the exams, but I’m never happy with my exams.
  • Ted was an invaluable sounding board throughout the semester, taking time he didn’t have to listen to my meanderings on the course. Thanks be to Ted, who will do an excellent job teaching the course in the fall. (Excellent, but wrong.)

The feedback I have had from the student side has been very good so far (with the real teaching evaluations still outstanding). I have never before had so many students who had nothing to do with a course talk to me about it. Random students in the hall thought my project was a good idea; everybody and their dog knew about my first assignment; people with friends in the course want to know when I’m teaching it again.

I’ll take that as creating a “buzz” and call it a good thing.

P ≠ NP

August 7th, 2010, 8:21 pm PST by Greg

An email I was recently forwarded (a couple of steps removed) from Vinay Deolalikar from HP Labs:

Dear Fellow Researchers,

I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.

The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.

This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.

This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.

Comments and suggestions for improvements to the paper are highly welcomed.

The paper is about 100 pages, and looks serious (but being a decade away from last thinking about complexity, I am unable to give any more useful evaluation than that). I’ll refrain from posting the paper itself.

Deciding P ≠ NP is a Millennium Prize Problem and I don’t think I’d get much argument to say it is the biggest open problem in computing science.

Update: I see someone else Deolalikar has uploaded the paper. I should point out that in the email thread I got, Stephen Cook said “This appears to be a relatively serious claim to have solved P vs NP.”

Update: Huh, slashdotted. I think “broke” the story is a little strong, but anyway… any media wanting comment on this story, I’d suggest my colleagues David Mitchell (whose work was cited by Deolalikar in this paper), Valentine Kabanets, or Pavol Hell (who also do research in this area).

Update 08/09: Richard Lipton is posting excellent commentary in his blog.