Sub Ubi

SIGCSE was good; the location was… rough. I’ve described it as “a cultural pit,” to some people, or a “neon nightmare” to others. My parents asked if I was surprised at being back in the US; I couldn’t possibly tell, given the background shock at being in a casino. Not exactly my kind of place.

Location aside, it was an excellent “people-SIGCSE.” I met a number of new peoples, and spent some excellent time talking with peoples I knew from years past. It was particularly fun meeting a number of the Bootstrappers, who were a good bunch all around.

This last week I’ve been very busy with getting settled back in, as well as spending time with my wife, who is here for the week visiting. This week has been typified by frantic mornings in the office and afternoon/evenings spent with her. Two days ago, of course, I boogered up my neck, and instead spent as much time as possible laying down.

So to lay down a plan for what I want to comment/reflect on:

• The Doctoral Consortium from this year, as well as what I think might make some nice changes for next year,
• Thoughts on papers I attended (or did not attend), and
• The direction of my research based on conversations at SIGCSE.

This should provide context for the next few days/week or so of writing. Current bits will work their way in, but once Carrie heads back to Wales, I’ll have more time for keeping up on posting. And those three categories of post seem to be good starting points at the moment.

It was an exciting conference, by-and-large, although the venue left a great deal (of sunlight) to be desired.
I’ll be posting over the next several days with reflections from conversations from the conference. I’m also hoping over the next several days that I’ll hear from people interested in the CS-ED.org project, and perhaps a few new bloggers will appear!

So, greetings to new readers. Perhaps I should create some docs about RSS reader software, so people are aware that there are useful tools for keeping track of sites like this one?

I’ve managed to get the departmental laptop I am going with (mainly so we can run Clementine, which only runs under Windows) ready to go. It needed Perl, Scheme, Emacs, drivers for the wireless card, SSH, and while I was at it, I tossed on w.Bloggar, the windows weblogging equivalent to kung-log on the Mac.

I also need to put together some cards to hand out, staple some papers, and get to bed. Assuming I can sleep. I had a lot of caffeine today, and am wired about leaving tomorrow. I just have to hope that all the hype surrounding terror alerts right now is just that… hype.

Right. I’m sure I’m forgetting something, but I don’t know what it is.

Next stop, Reno!

I just bought a bag of cookies to snack on this afternoon. I didn’t even think that there might be any kind of cookie other than chocolate chip.

I ended up with raspberry and white chocolate.

It there was ever a cookie I would never eat, it would be raspberry and white chocolate. Especially since it’s artificial raspberry.

That said, they could be worse…

CS-ED.org’s timing, I think, is perfect. There are people asking good, hard questions about the role of weblogs in the dissemination of news, research, and other types of information. Questions about copyright, ownership, rigor, and many other related issues are lively topics of discussion and debate.

The notion of the web as a tool for communication and dissemination is not new, but tools that abstract over the HTML and make this simple a simple type-and-click process for regularly updated sites is relatively new. CS-ED.org runs on Moveable Type, one of many weblogging platforms available; with tools like Kung-Log (for the Mac) and w.Bloggar for Windows, I don’t even have to open my web browser or type a single bit of HTML to put content on the web.

Yesterday, Google announced the purchase of Pyra Labs, the creators of Blogger, a popular weblogging service with well over 1,000,000 users. Google moves from content indexing to content creation.

I need to print up some business cards with the CS-ED info on them for tomorrow; SIGCSE will be the time to promote the venture and see if we can’t get a small, thriving community going here.

And, as it turned out, my code was not “exactly like the pseudo-code.”

There was a very subtle difference between my code and the pseudo-code as given in the paper. Given the relatively ugly notation (everyone I’ve discussed the paper and implementation with agree–their notation is a bit strange and the semantics are very unclear in places) it isn’t surprising that I missed something, and in presenting it to people helped them gloss over it as well.

The lessons learned? I think the most valuable lesson learned is that I should continue trying to acknowledge when I’m stuck sooner, thus seeking insight and new perspectives sooner. I may have hurt my ability to see this kind of thing by working non-stop on the problem for the last three weeks. Had I walked away for a few days, come back, and then taken a Saturday afternoon to carefully check my work, I may have found this myself.

However, there is no shame in the error; I wasn’t the only one who missed it, and there was a lot of good work that got me to the point where a mistake that small could keep me from progressing. So I go to SIGCSE ready to potentially explore some interesting data!

Whoo-hoo!

Another four hours were spent last night crawling through my implementation of the algorithm presented by SWZ entitled Approximate Tree Matching in the Presence of Variable Length Don’t Cares. Ian and I did find a bug in my implementation; in pressing on the fact that there were absolutely bogus negative results coming back from my implementation (for a while) we discovered that my interpretation of theta was incorrect. I took it to mean “the upper left-hand corner of the matrix.” Instead, it should be “one less in both directions than the current upper left-hand corner of the matrix.”

Right. Not that the casual reader of this weblog is going to have idea one about what I’m talking about. The short, English version is this: “I’m working on putting into code someone else’s ideas. Currently, I think my code is wrong, but I’m running out of ideas as to why it is wrong. Eventually, you start wondering if you’re not wrong.” However, that is a big claim to make, and I’m not ready to make it. As you get closer to that point, though, you get more rigorous and fastidious in your examination of the problem, hoping that you will find the critical error in your code, so as not to have to question the correctness of someone else’s work.

Still… why does it seem their code is “right,” while mine is written exactly like the pseudo-code in their paper, yet it is … “wrong” some of the time, but not others? And what is the significance of the fact that my code is always equal to or greater than their solution? On one hand, it could be I’m finding non-optimal solutions, as they are using a slightly different approach…

More exploration, and perhaps more questions to the author. And I have so much to do before Monday….

Argh.

Implementing the ZSW93 algorithm for edit distances between trees has gone from a simple, one-week project to a three week nightmare. I see no reason why I should be having as much trouble as I am… clearly, I’ve made a fundamental mistake that I, myself, am blind to. I’m involving classmates in discussions of the algorithm, my implementation… anything that forces me to explain and defend my work in the hope that I’ll see a mistake somewhere.

Given that my code behaves differently than the reference code (it produces different results) for some trees and not others, it is clear that there is some structure in the trees I am not handling properly. Axel asked a good question today: when your results disagree with the reference code, have you tried feeding only the important parts of the data to your algorithm? That is, the parts of the data that change?

No. I haven’t.

[Time passes]

Now, I have.

And my implementation performs incorrectly on the subtree structure. In this case, it is a linear tree and a tree that has one branch in it. Why does mine fail? Why does the reference code work? Why does my code work for identical trees with arbitrary branching, and why does it correctly pick up some kinds of changes and not others?

Argh.

On a lighter note, I downloaded an Apple //e emulator yesterday, and today I found the game Lode Runner. I owned a copy of this years ago for the Commodore 128 (running in C64 mode, anyway). To be able to play it again is wonderful.

So was the last week a waste? No. Was the best part (so far) that I found Lode Runner? Yes. Will I solve my problem before going to SIGCSE next week, where I really want/need this code to work?

I sure as hell better.

Back to work.

Ah. I have the ability to compare trees.

Joy.

I still don’t know if it works 100% correctly, though. Verifying complex poo like this is the real pain, ya’ know? Even with the algorithm in front of me, and a collection of macros to make my code look just like the algorithm, I have no way of knowing (for sure) that my implementation is correct.

I’ll look at some results on paper this evening, start writing up a tech report on the whole deal, and be glad that I’ve made process.

Coffee. Now.

In a few weeks, CS-ED will be ‘made public.’

For the better part of the past year, Peter and I have been poking at, tweaking, and experimenting with the notion of using weblogs as a way to

1. keep in touch with respect to our doctoral work, and
2. attempt to regularly and actively communicate current ideas about our work.

For large chunks of the past year, neither of us wrote anything. Writing is hard, and writing about nascent ideas is even harder. I don’t think we have a clear idea as to the role of a weblog is in the research process. While there are people exploring this space and asking questions about it, I believe the applicability and utility of such an exercise is an open question.

That said, the question might be different for different people, and jumping in and trying it out is as good a start as any. One of my biggest hurdles to overcome was the writing interface; I’ve found that writing became easier when I started using a tools to assist in the process of posting. Instead of going to the web browser, I downloaded kung-log, which eliminated a large part of the hassle in posting. That, and I committed myself to posting every day from the start of the new year forward. While I didn’t achieve this, I found I started to have a sense when it was worth saying something, and when it wasn’t. Posting (almost) daily gave me something to close my day with, and a way to get thoughts down I might otherwise forget.

Today I turned on the MT option to ping Weblogs.com. This site has not interacted with the greater weblog community before today. In a few weeks, we’ll introduce the CS-ED.org site to the participants at the 2003 SIGCSE Doctoral Consortium. After some more tweaking, we’ll announce the site to various mailing lists, and invite participants in any area of computer science education (research or otherwise) to take part.

There are still parts of the site that need work. The Wiki exists, but is not configured properly. The site has a standard template that isn’t really “modern” (CSS, etc.). I really want people to be able to easily include a list of links on the LH side of their page (a blogroll, perhaps?), in addition to the automatically generated one on the RH side. All in good time, I suppose.

Unless lots of things fall into place soon with what I’ve been working on, this is the state it will be presented in. I’m nervous, but I think I’m nervous in a good way. As I’ve been known to say, it could be worse.