In Soviet Russia, Website Uses You!

I could go on for days about how government websites are hopelessly mired in a funk of ancient design practices and proprietary databases - or I could just point you here, where the U.S. Department of Health & Human Services has kindly made my point for me. Among the snafus:

• Three separate stylesheets. Three: one for IE, one for Navigator 5 and up, and one for the rest - plus the browser detection code is crude.
• Those image links are killing me. They're ugly, they're unnecessary, the rollovers don't even line up properly. Worse, they're backed up by some horrendous-looking JavaScript that could be rewritten in about five lines even without pulling in anything like jQuery.
  
• Searching the site for CSS turns up...no results. How do you write about website usability without once mentioning CSS!? Simple: throw in a bunch of process jargon. And you wonder why these government websites never finish their usability reviews...
  
• That aside, finding anything on this site is a bit of a chore. Either I go with Search and receive what I'll refer to as "context-free results", or I poke through their gangly tab-list-hyperlink structure. Wait, never mind - this makes everything so much clearer, right?
  

And...

...we're back to relative sanity here at Quizzical Quincunx, now that the new CSS has been plugged in. With that out of the way, I might delve into the widget content itself (free time pending, as always!)

Note to Blogger: editing HTML directly through your editor is a terrible experience. So terrible, in fact, that I resorted to saving a local copy and vim-Firebug double-teaming it. Make it easier to quickly see the results of my changes and start supporting things like, you know, the tab key. Ugh.

Note to everyone else (yes, all three of you): comments? thoughts? gripes? minor sticking points? Feedback is always appreciated.

Hooray for Experimentation!

I'll be gutting and tweaking my Blogger theme over the next few days. In the meantime, if you should have the misfortune to happen upon my humble ramblings and irreversibly sear your eyes in the process, well - you have been warned.

On the Bright Side...

...my camera and associated USB cable are finally in the same location, which means I can start annotating my posts with random images like this:

Pay attention to what the Fuel Gauge says!

It was the best of luck, it was the worst of luck: today, en route to salsa lessons (nothing better than dancing away the Ottawa winter blues!), I ran out of gas halfway up a hill on King Edward - almost directly across from a gas station. I was operating under the (evidently false) assumption that the angry blinking indicator really meant that I had about 30 km of good driving left before my ride puttered out on me.

Which brings me to ask - we have indicators that display external temperature, speed, and cumulative distance. We have GPS systems and radar warning systems and anti-lock brakes. Why not tell me exactly how many liters of gas are sitting in my tank? After all, if we want to encourage those hypermiling gas-sipping compulsive optimizers, we should give them all the relevant data.

ICANN't

Here's a question: in the age of crowdsourcing, social networking, and distributed peer-to-peer filesharing, why do we have to pay a centralized body $2500 for the right to directly register a domain name? Small wonder that some disagree. Part of the issue is DNS itself - to translate that nice, human-readable URL into an IP address like 64.58.66.214, your computer has to ask a translator. To find the right translator, it asks a global directory.

If you have any background in security whatsoever, digital or otherwise, you're probably asking yourself - isn't that a really dumb idea? Sure. Let's ignore that, however, and envision instead the following scenario:

A person, who we'll call X, decides one night to nmap -sP 0.0.0.0/0 | grep "appears to be up". X then scrapes DNS and WHOIS info for each responding host using nslookup and whois into a massive database. Since X is a computer programmer par excellence with access to infinite upload bandwidth, they write their own server capable of answering all DNS queries worldwide.

Obviously, there are some minor wrinkles - like the intractability of crawling the IPv6 address space, or the impossibility of X being able to serve the immense global DNS lookup demand, or the infeasibility of expecting your average (read: clueless) computer user to change their DNS lookup settings. The above scheme is clearly suboptimal, though; the scraping part is embarrassingly parallel, and X could easily publish the data publicly - as a torrent, say, or as multiple smaller chunks.

Of course, this opens up a whole new can of worms: as a decentralized DNS provider, I could direct every lookup to my website or add entries for my competitors pointing to, er, less reputable content. Nevertheless, the idea is at least plausible; with a reliable trust model and just enough regulation of domain markets to shut out serial cybersquatters, it might even be workable.

NaNoWriMo 2008

Last term, I had the immense pleasure of participating in NaNoWriMo - that hallowed annual event wherein would-be writers consent to a month of grueling lexical vomitus in exchange for, well, nothing (unless you count pride and a sense of accomplishment as material.)

My tool of choice? Google Docs. Despite some slowdown on the sluggish university lab terminals - especially towards the end of the month - the experience was relatively smooth. The greatest benefit, however, was being able to easily share it with friends and have them track the development of the story. Try doing that with MS Word. Anyways, here it is.

Dimwitted Reactionary Measures

Just read some snippets from Cory Doctorow's 2004 talk at Microsoft Research about the absolute mindboggling brain-deadness of DRM schemes - it's a shame they ignored the lesson. Anyways, the talk is well worth a read, even if it is outdated by online standards.

Monkeying Around

I finally got in touch with PKCC, Ottawa's local parkour community. One of their members is trying to get a weekly group conditioning session going, which is definitely A Good Thing; the harsh and prolonged Ottawa winter puts a damper on most regular outdoor activity, save perhaps for the occasional bit of vigorous snow-trudging.

On my goals list for this term: do 5 muscle-ups in a row. My training has been less than dedicated over the last couple of years, and this seems like a good benchmark to start with.

That said, I'm slightly disappointed to find that PKCC is nowhere near as active or cohesive as the group in Toronto. I'm hoping that the Ottawa scene will pick up again once this frigid pallor lifts. Until then, I've got some serious conditioning to do.

Doesn't Help, Statistically

Bruce Schneier often finds occasion to rail against what he refers to as "security theater" - and what better example thereof than that most venerated of public institutions, the Department of Homeland Security? Happy reading.

(As an aside, I'm still waiting for the day when some enterprising terrorist decides to make explosive clothing, thus resulting in a general ban on clothes in airports. (Not really, of course - but it makes for a darkly comical thought experiment!))

(Update: I can't believe I'm linking to MSN Video, but...watch L'Aeroport.)

So You Think You Can Sort

Selection sort. Insertion sort. Quicksort. Mergesort. All are standard fare in your average basic-level CS class; the first two are inefficient but conceptually simple, whereas the last two are decent general sorting algorithms. This is all good and well, but no one uses them for performance-critical applications:

• Often, a sort is not required; what you really want in most large-scale cases are the top k results for some relatively small k.
  
• Real-world data has patterns that general algorithms like your standard library quicksort fail to exploit.
• Comparisons and swaps aren't always cheap.
  

For you C++ programmers, the first point means little more than the difference between sort and partial_sort. The second point, however, is slightly more subtle.

As a simple example, suppose you have a billion integers to sort, but you know that each one is between 1 and 100. With that restriction alone, you can easily sort them in O(n) time. Other examples:

• The data are k-sorted (i.e. A[i] >= A[i-k].)
• The data aren't quite sorted, but they are unique; furthermore, abs(A[i] - A[i-1]) < k.

The third point might seem like a dubious proposition, especially that part about swaps. How can swaps be expensive? If I want to swap complex structures, I use pointers. Simple, right?

A while ago, I wrote a DHTML table sorter (for fun, naturally!) For reference, here's a standard quicksort implementation. Ignoring the horrendous colour scheme for a moment, why is the first one so much faster? Simple - it avoids swapping DOM elements. (There's a reason it's called permutation quicksort!)

Fine. So we can guarantee O(n) swaps in exchange for linear memory overhead. How do you limit comparisons? Remember that second point - notice patterns.

At Last!

Yeah, I know. Problem 117 is easy. IMHO, it's ranked "harder" than other problems simply because the requisite formulae for many of these questions are easily found using a combination of Wikipedia, MathWorld, and Sloane - which is not to say that the implementation part is always trivial!

Statement Of Content

Off a tip from a co-worker, I pointed my browser at the CS Distinguished Lecture Series 08/09 presentations at the University of Toronto's Knowledge Media Design Institute. If you have the chance, check out Dr. Raghavan's talk on Web Search. Coles Notes version: semantic web.

What does that mean? To the average computer user today, web search is a done deal: we have Google (or Yahoo, or (ugh) Microsoft Live Search.) They scarcely notice, for example, Google's push for universal search. Yet this shows that, even at current levels of quality, traditional page/click-driven search falls short of the goal: to understand and enable the user's intent.

Yes, Google will return flight results, weather, cinema listings, and maps. Yes, it serves up definitions, exchange rates, and simple computations. The problem lies in implementation: all of these are special exceptions, extra branches in a behemoth decision tree that is roughly equivalent to this:

Does this look like a location query? No? Does it look like a request for movie times? No? Does it...

This doesn't generalize well, for obvious reasons: the search engine knows nothing whatsoever about what I'm trying to accomplish. If it has a model for user intent, it's stunningly rudimentary. Sure, there's room for optimizations, like promoting results that look like results I've clicked on before - but these are optimizations on top of a fundamentally limited model.

So how do we form such a semantic web or, as Dr. Raghavan puts it, a web of objects? That remains an open question. On the other hand, thanks to the success of Google et al we now have massive datasets of user click patterns, queries, times spent on various pages - the list goes on. Perhaps we can harness that data to build this new semantic, intent-driven, user-centered web on top of the content-driven web we have now. In fact, I'd be truly surprised if there's a single big-name search engine out there that hasn't been actively researching this for years. If there is, they are certainly doomed to obsolescence.

So close!

98 questions, 2 to go.

A Good Head-bash-ing

Recursive functions in bash. Everyone seems to have the same advice: use local variables, stacks hacked together from bash arrays, or exitcodes. Ugh. Why not echo the result to standard output, like just about every other UNIX program?

ackermann() {
  M=$1;N=$2
  ((M==0)) && echo $((N+1)) && return
  ((N==0)) && ackermann $((M-1)) 1 && return
  ackermann $((M-1)) `ackermann $M $((N-1))`
}

This is somewhat contrived and more than a little inefficient. Not only that, but it's also incorrect: bash, like most "real" programming languages, suffers from integer overflow. Or does it?



function compute {
  echo "$1" | bc | sed ':start /^.*$/N;s/\\\n//g; t start'
}

function ackermann {
  M=$1;N=$2
  ((M==0)) && compute "${N}+1" && return
  ((M==1)) && compute "${N}+2" && return
  ((M==2)) && compute "2*${N}+3" && return
  ((M==3)) && compute "2^(${N}+3)-3" && return
  ((N==0)) && ackermann $((M-1)) 1 && return
  ackermann $((M-1)) `ackermann $M $((N-1))`
}


Of course, most useful recursive bash scripts (like make!) don't abuse standard output in this horribly screw-brained way. Instead, they have side-effects (like compilation!) and reserve output for things like status or error messages.  But that's not the point. The above snippets show that you can deal with recursion (and extended-precision arithmetic!) in bash in a relatively clean manner. (Some might object that, as a CS student, my definition of "relatively clean" is skewed. I'm declining comment on that one.)


(Then again:

 
./ackermann3.sh 4 3
Runtime error (func=(main), adr=19739): exponent too large in raise


I suppose there are limits to everything.)

  

Seven Habits Of The Status Quo

I was just reading through the Seven Habits of Highly Effective Programmers. All was well until I hit this gem:

There is Such a Thing as a Stupid Question

Really, there are lots of stupid questions. [...] Asking for clarification about a specification shows you know how to find and read the spec and your ability to detect ambiguities. [...] Let everyone know that you read the documentation and googled the subject.

This seems like a perfectly reasonable statement. If some script kiddie n00b can't be bothered to RTFM, they aren't worth the time of day, right?

WRONG!

Consider this: how many programmer-hours are wasted every day reading man pages, library documentation, language references, and so on? To paraphrase: ask a stupid question once, shame on you. Ask a stupid question millions of times - well, you can't. That's the point. If I had a dollar (yes, even a Canadian dollar) for every time someone asked a question about the intricacies of UNIX find...

The above excerpt says less about effective programming than it does about the programmer mindset: developers first, users second. Let's collectively ask ourselves a question. What if, instead of rejecting these supposedly dull-minded inquiries, we tabulated them and created a centralized, easily searchable FAQ? This forks a handful of stones and slays an entire flock of birds with them: less experienced developers would stop asking stupid questions, and the seasoned soi-disant experts could respond effectively to any stray requests in constant time by directing the wayward souls to said FAQ.

Until that happens, happy man-page reading!

Gripe Of The Day

A simple one, really: there's no const version of std::map::operator[].

Now, I understand the reasoning here. After all:

#include <map>

#include <iostream>

using namespace std;

class A {
  map<int, int> m;
public:

  void foo(int i) const { cout << m[i] << endl; }
};
int main(int argc, char* argv[]) {
  A a;
  a.foo(42); // what happens here?
  return 0;
}

Our mythical const version of operator[] can't return a reference, as there's no object to refer to. It can't return a default value, either; there's no guarantee that the map's value type will have a default constructor (though in this case, the type int defaults to 0).

On the other hand, why not simply do as std::vector::operator[] does, and throw the programmer in the deep end if they access an invalid index? Thoughts? Comments? Heated counterarguments?

Level 3, Almost

93 problems and counting, including two of the 25 most recent (which means I get a nice red-coloured progress bar under Current Performance!) I'm shooting for 100 by the end of the week - enough for Level 3 status and a permanent place on the Project Euler scoreboard.

Aside from that, I'm currently optimizing my first project at work. After all, a new statistical machine translation feature function isn't much use unless you can run it across a cluster on corpora of at least 10 million phrase pairs within your lifetime. (In my defense, the goal of the first implementation was to get something working; judging from the unit tests, this objective seems to have been met.) Following discussion with co-workers at NRC-IIT, some intense whiteboard sessions, and profuse streams of invective launched (unfairly, perhaps) at valgrind, I'm confident that it can easily be improved to run within a day.

(Now that would be a good use of Python generators - (theoretically) infinite streams of invective, scraped from the bowels of our beloved Internet via httplib. Some would argue that the Internet's capacity to provide said invective is necessarily finite. I (and Bucket - NSFW) respectfully disagree.)

Sonic Boom!

I happened upon an interesting web app today - The Next Big Sound - which lets users play the role of record mogul and "discover" talented independent bands. More proof, if needed, that the screw-the-customer-at-all-costs model currently pursued by the RIAA and its ilk is about to draw its terminal breath. Of course, I have no problem with the RIAA running itself into the ground, as it seems hell-bent on doing. I just wish it would happen faster, and that the courts would stop upholding a sorely antiquated and essentially unenforceable copyright model.

Second Week, Here We Come

I'm one week into my research internship here with the National Research Council's translation group in Gatineau. Like everything else even remotely connected to the federal government here in Canada, this is a bilingual environment; indeed, bilingualism is pervasive throughout the Ottawa-Hull region, and for obvious reasons. As such, I've been making a concerted effort to dust off my somewhat rusty French, left unused since my travels in Europe some four or so years ago. To finish off this post, I'll leave you with two tidbits of linguistic culture:

• pourriel: spam, from a portmanteau of pourrir (to rot) and courriel (email, itself an abbreviated admixture of courrier and électronique).
• The Québecois inherit from their Catholic past a legacy of religious-themed curse words. This famed stereotype has even reached far-off Mexico, where they are known colloquially as los tabernacos.

Other than that: I finally have a car, which is more or less essential if you want to do anything other than admire the vast snowbanks here in Gatineau. Google Maps can attest to the remoteness of my present location: searches for bars, supermarkets, and banks near here all turn up nothing within nearly two kilometres.