Greg and Kat's blog

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.

I teach at a university. That comes with certain parameters: most of my students are in their late teens or early twenties, the average student is reasonably bright but occasionally unmotivated, and I don’t really have any way to compel students to come to lectures.

I do my best to give interesting, informative, and entertaining lectures. I’m successful enough that most students come most of the time, and that’s awesome.

Sometimes students don’t come to lecture. They don’t need a good reason, and they don’t have to tell me about it. I’m okay with that too: part of being at university is being responsible about that kind of thing and I’m happy to assume that whatever reason they have is a good one.

But what really annoys me is when students feel the need to email me, tell me the stupid reason they didn’t come to lecture, and then ask me to tell them what I covered.

I already spent an hour (or three hours) of my time giving the lecture and they had an opportunity to attend. I put a great deal of time and effort into explaining the material in the best way I can and pointing out the things that I think are important. I did all of this because I think I can actually do a decent job of getting material across in the lecture format and I think the material I’m talking about is important.

These emails leave me with two choices: (1) reduce a carefully-prepared lecture to a pointless list of topics and thus implying that I might as well have read them the textbook, or (2) spending another hour repeating the lecture in email form. Neither one of those is very attractive, but there’s also the third option that I have started to avail myself of: telling the students to shove off.

I’ll say here what I said to my CMPT 165 class last semester: if you miss a lecture, you ask a friend in the class for their notes. If you don’t have a friend in the class, ask the person sitting beside you; if at all possible, try to do this when you are sitting beside someone who you find attractive and offer to buy them coffee in return.

Seriously… do I have to explain everything?

cf. entitlement generation.

I have mentioned here before that I was planning to teach CMPT 383. It ended up being a no-go this semester because of a very productive capstone project team (more on that later).

But, I’m on-deck to teach it in the summer. The class is full; the waiting list is full; must be time to plan a course. After much soul-searching, I have decided there will be three main topics in the course and they will be covered in this order:

Functional programming (and Haskell)

This will be most students’ first introduction to a non-imperative programming paradigm (and associated language). Every little while I think this won’t take long, then I remember the list of things that have to be introduced to get anywhere with Haskell: being really good at recursion, list comprehensions, lazy evaluation, type inference, higher-order functions, and other stuff to be discovered as I try to teach the language.

From my perspective, there are two reasons to be talking about functional programming. First, it’s finding some relevance, probably because people want to parallelize things (e.g. CouchDB). Second, there are important lessons from functional programming that can be transferred to OO programming.

“Language Features”

This section contains the big concepts of the course: type systems (static/dynamic, strong/weak, type coercion, duck-typing, late/early binding, …), interpreted vs compiled, pointers vs references, memory management, reflection, runtime environments, first-class functions, objects, exceptions, mutable/immutable objects, ….

The basic question here is: what are the real differences between the programming languages you have to choose from? How might they affect your choice of language for a project?

Logic programming (and Prolog)

As much as I am aware that Prolog is pretty much confined to old school AI researchers, I still think there’s some value in being exposed to logic programming. It should be possible to translate back to the OO world the idea of expressing a problem as a series of constraints and then looking to satisfy those constraints.

To be fair, this is the chunk I am most unsure of. Part of the reason it comes last is that if anything should fall off the end of a full semester, it’s this.

The exact balance of the topics remains to be seen. I’ll guess 5 weeks, 5 weeks, 3 weeks.

As for getting marks, I am as far as:

• Lab exercises: weekly hour-or-two chances to practice the concrete skills.
• Assignments: like… two of them? One Haskell, one Prolog?
• Project: pick a somewhat obscure language from a list I provide. Explore it by writing a report and some programs with it.
• A midterm and a final exam.

No idea what I’ll ask on the exams. Maybe Warren has some old ones I can look at.

So there it is. Unless I change my mind.

After a simple query from a colleague about the differences between HTML versions, I wrote this. I thought I might as well post it. Everything was from-memory, so there may be some minor errors.

HTML 1 never existed (it was the informal “standard” that the first documentation implied).

HTML 2 was a really minimal initial description of the language. The language was simple because the initial goals were simple. The browser makers made many de facto extensions to this by implementing random stuff.

HTML 3 was an abandoned attempt to standardize everything and the kitchen sink. HTML 3.2 was a really ugly standard that was basically “here’s what browsers accept today.”

Which brings us to modern history…

HTML 4 was an attempt to clean up the language: get rid of the visual stuff and make HTML a semantic markup language again. It included the transitional version (with most of the old ugly stuff) and strict version (as things should be).

HTML 4.01 was a minor change: missed errors and typos.

XHTML 1.0 is HTML 4.01 but with XML syntax: closing empty tags with the slash, everything lowercase, attribute values quotes, etc.

XHTML 1.1 contains some minor changes, but was abandoned in a practical sense because nobody saw any point to the change. XHTML 2.0 was another very ambitious change (non-backwards compatible changes to the language) that was abandoned.

HTML 5 is in-progress of being standardized now. If you ask me, there are two camps driving it. One who thinks “the web is more about more than just simple web pages now: applications and interactivity rule the day” and another who thinks “closing our tags is too hard; I don’t understand what a doctype is: make it easier. Dur.”

As a result, there are some things I like and some things I don’t. I is showing signs of something that will actually be completed and used (unlike HTML 3 and XHTML 2).

Most people don’t know that the HTML 5 standard includes an XHTML version as well. It will be perfectly legal to write HTML 5 with the XML syntax and call it “XHTML 5”.

Addendum: The moral of the story is that I have no intention of teaching HTML 5 anywhere until the standards process is done. For 165 I also need real browser support: no JS/DOM hack to get IE to work, and some defaults in the system stylesheet to let the thing display reasonably without any CSS applied. Even then I will probably teach XHTML 5 because I think it promotes the right habits.

I just got a new netbook: an Asus Eee 1005HA.

As my old tablet got slowly older, I realized that I don’t really have heavy laptop demands: most of my use is a text editor and “hey look at this web page” in lectures. Even when away from the lecture hall, I tend to work primarily in a text editor (for LaTeX, HTML, Python, etc.), Thunderbird, and Firefox. I’m not exactly putting a big strain on the system, and can trade off power for small and light.

As always, there’s a big difference between the average stock setup and what I need to get some work done. Bridging this gap is a hassle, so I’m going to finally record what I need so I can look it up next time.

The new Eee is dual-booting Windows 7 and Ubuntu (Karmic netbook remix). Yay to Asus for shipping with a second “data” partition on the drive that was dead-easy to put Ubuntu on.

I’m open to must-have software suggestions that I missed. I’ll probably add more below as I find stuff I missed.

In Windows

• Firefox
• A text editor, usually Crimson
• WinSCP (or some other SCP and maybe SSH client)
• For 165: Python, GIMP, maybe Inkscape
• TortoiseSVN (if there’s a possibility of development happening)
• ClamWin

In Ubuntu

• rsync (As far as I’m concerned it’s negligent to have an operating system install without rsync.)
• subversion
• sshfs
• ntp
• thunderbird (and thunderbird-gnome-support)
• If I’m going to be downloading pictures from a camera: mmv, jhead, exif, gphoto2, python-pyexiv2, gpsbabel
• ddclient (with a config file like this)

In Firefox

• Delicious Bookmarks
• Flashblock
• QuickJava
• Download Statusbar
• Firebug (if there’s any possibility of webdev on the machine)

… and it’s days like today that I have to say that out loud to remind myself. I am not mentally or physically prepared to be done my Christmas break or resume teaching.

I have posted some pics from Vegas. The trip was good: to give you an idea, we gambled a total of $100 between us because there was too much other stuff to do.

A warning: when going to Vegas, plan to spend $100–200 per person per day on miscellaneous stuff. By the time you have a nice dinner and go to a show, $100 is gone, and that only entertains you for the evening.

The highlight for me was probably the Gun Store (not-even-subtly-racist targets aside). When else am I going to shoot an assault rifle? I should have upgraded the package to shoot a handgun too.

Other than that, we had a good set of the standard holiday stuff (including our open house, which I haven’t done the time lapse video for yet). All of that went well, but all happened much too fast.

Yesterday, I had both of my CMPT 165 exams (on-campus and distance) back to back. The exams were different enough that students talking for the few minutes between exams wouldn’t get anything useful from it, but no more than that.

Six hours is too goddamn long to be in exams. I can think of no way to describe the day other than a list of happenings:

[tl;dr Go for 2b, 3ab, 4b.]

1. Pre exam:
   1. The first exams start at 8:30. At 7:45, not one but two of my colleagues were still trying to photocopy their exams for big sections. Office photocopier was jamming every two seconds; grad photocopier was down.
   2. Critical mobile phone usage #1: realizing Amanda would already be in her office, I phoned her and got one colleague into the photocopier in the Dean’s Office.
   3. “Wait… did I tell that student she could start a half hour early? Where was she going to meet me?” Send TA running to the room with an exam paper, just in case. (No student.)
2. On campus section:
   1. Before the exam, a girl flagged me down and told me she “had cancer before” and had been feeling lightheaded this morning. If she had to leave during the exam, that was why. I tried to get her to Health Services right away, but she insisted on staying. At the end of the exam, I convinced her to at least go and get her blood pressure taken or something.
   2. Two minutes into the exam, after sitting there for three or four minutes before it started, looking at the exam cover sheet (which says “CMPT 165”) and me, a student put up his hand and said “this isn’t CMPT 120” and left.
   3. Freakin’ piles of questions, including “can you give me a hint” and “what time does the exam end”. Many more questions than the distance section.
3. Distance ed section:
   1. About 10 minutes into an exam, one of the kids that had run in a few minutes late flagged a TA over and said “I feel like I might pass out.” I talked to him for a few seconds and he was not entirely conscious: able to answer yes or no questions, but that’s about it. He probably couldn’t have walked out of the room at that point.
   2. Critical mobile phone usage #2: phoned SFU security for a medical emergency. To the credit of security: they came quickly and handled it quietly and with a minimum amount to spectacle to distract everybody else. They took the student to Health Services.
   3. After all this, I start to realize that I have been getting lightheaded when standing up: I’m hungry and totally dehydrated from four hours running up and down hot lecture halls. A litre of water and snack later, I’m feeling much better.
   4. A guy came in 45 minutes late after “car problems”. A girl came in about 1:15 late after a car accident on the way from Abbotsford.
   5. With an hour left in the exam, passed-out student came back! He wanted to finish his exam and was pretty sure he could get it done. I took this as a sign of not yet being fully capable of making decisions and sent him to the distance ed office to schedule an alternate time.
   6. Critical mobile phone usage #3: phoned distance ed and told them the story so they’d deal with this kid appropriately. Apparently he wrote the exam later in the afternoon anyway (but at least he had the full three hours).
4. After the exams:
   1. I’m barely standing at this point.
   2. I was talking to Anne, and told her the story of my day. Anne is preparing to teach a course like 165 in Uruguay (since she is currently on study leave). She was translating the course outline to Spanish and kept asking me things like “what wording do you like better?” I must have said three times: “Anne… you know I don’t speak Spanish, right?!”
   3. I might have eventually just wandered out of her office while she was still talking. I don’t really remember.

There was probably more. That’s all that’s coming to mind at the moment.

As I said before, I’m not teaching CMPT 383 in the spring (but I will be doing it in the summer). The alternate plan involves the “capstone” project that our dual-degree students have to do.

I’m going to be supervising a group of students on the technical side of their project. Since I’m me, the plan is to do a web project. I thought about this for about 8 seconds before I realized what I must do… there’s an obvious set of web projects that I understand, students understand, and need to me done.

We have some very old and clunky web tools around the School that work, but aren’t pretty and don’t have much hope of improving in the future. Students will know our gradebook and assignment submission tools, but there are a bunch more that aren’t student-facing.

My plan: replace as much as possible with modern, integrated, functional tools. The plan goes (or at least start) like this:

• Global: Unified CAS authentication. A useful “dashboard” for everybody displaying recent activity relevant to them (upcoming due dates, recently posted grades, recent assignment submissions, etc). Instructors should be able to copy an old offering to a new one (copying grading info, due dates, etc).
• Gradebook: the basics as currently implemented, with calculated columns, released/unreleased columns, AJAX-y sorting and display of class lists, email notification of new grades (?).
• Submission: Per-assignment configuration (e.g. assignment 1 requires submission of a text file for part 1, and a .java file for part 2; both are submitted as distinct files).
• Marking: Instructor sets up a marking key for TAs; TAs give grades and comments; info returned to students and grades automatically put into gradebook.

Additional functionality suggestions welcome. I have some cool “maybe” features to throw in if things go well.

I’m going to be treating whatever group I have as a development team, not a class. So, I’ll be whipping them much more to get good-quality code, not a class project.

There’s certainly a possibility of catastrophic failure, but I’d say a reasonable chance of success. We’ll see what happens.

I know the schedule for the spring semester was announced with me teaching CMPT 383, but that is no more. I have been moved from 383 to something else that I’m sure I will have much to say about later.

Yarolsav Litus will (likely) be taking over the spring 383 offering.

I should be teaching CMPT 383 in the summer, though.

I have alluded to this in a status update, but I think it’s time to look more widely for feedback…

A while ago, I started thinking about all of the annoying things my CMPT 165 students do in their HTML, and then started thinking about ways to get them to stop. I started working on an automated checker to give them as much personalized feedback as possible without me actually having to talk to them.

They already use an HTML validator which checks documents against the HTML/XHTML syntax, but it’s amazing what kind of things actually pass the validator. In the list: resizing images with width/height on <img />; saving their source as UTF-16 (no idea how they do it); putting spaces in their URLs; using class names like “red” instead of “important”; not specifying the natural language/character encoding of the document; etc.

As the list became longer, the thing became sort of a general HTML lint: the thing you go to after your code is valid to check for other common problems, annoyances, and omissions. The more I look at it, the more I think it’s a useful tool for CMPT 165 students as well as a good way to make others think a little more about the code they are producing.

I’m now at the point of wanting some feedback. There are still some missing strings and help text, but hopefully you get the idea. I don’t want to guarantee that this link will exist forever, but have a look at my web lint.

As with any “lint”, the goal here probably isn’t for authors to get zero warnings, but just to think about why they are ignoring the warnings that remain. (No, I don’t need you to tell me that some of my pages produce some warnings.)

At this point, I’m most interested in:

• Links to input that causes an exception (500 Internal Server Error) or other truly broken behaviour.
• Feedback on the warnings presented and their “level”. I have deliberately hidden levels 4 and 5 in the default display: I’m aware that the tool is pretty anal-retentive.
• Are there things you can thing of (that could be automatically-checkable) that should get a warning but don’t? I have a few more on my list, but the core is in there.
• I don’t think the URL validation (for <a>, <link>, <img>) is perfect: I still need to go back to the RFC and check the details. Any cases you notice that don’t pass but should would be appreciated.
• Any spelling/grammar errors?
• I’m trying not to duplicate functionality of the HTML validators: they already do their job well. But, notice the links to “other checkers” on the right. Didn’t know about all of them, did you? Any others I should include?

My intention is to GPL the code and CC license the text, but let’s take one step at a time.