Vivek’s Soapbox

Sadly, UCI does provide a LaTeX template for dissertations. Getting the formatting right without a template can be a major pain, so here are the templates that I used.

LaTeX UCI thesis class and sample LaTeX file (ZIP file)

Credits: I initally got this template from TeX guru and ex-officemate Jeff von Ronne. I’ve made a tweak or two, but it’s 99% Jeff’s work (and lots of people before him too — see the class file for more credits).

O Google, please make this the first hit for the next poor grad student who searches for “uc irvine dissertation template”!!

Shouldn’t government websites try to be a little more cross-platform??

I’ve been using BlogBridge for a day and its now my blog reader of choice, for several reasons:

• feed ratings help when you have to quickly scan though a hundred feeds
• the little activity indicators next to each feed are a really good visual indication of which feeds have new stories
• you can sync your feeds up to a server (need to sign up for that) and then sync them across all your clients
• its in cross-platform Java

All the same, there’s still plenty more I want in a newsreader. My number one gripe: newsreaders have to effectively summarise and present information from a large number of feeds. All current newsreaders work on the “feed-browsing” model, where the user clicks on a feed, reads its stories, moves on to a different feed and so on. I want my newsreader to be a statistical clustering engine that automatically learns from my reading habits, and also clusters similar stories from across different feeds into a coherent view. In short, a newsreader has to make it easy for me to keep up with hundreds of feeds without having to scan each one of them.

So here’s a problem I faced while trying to build a little map application:

Say I have the locations (both in terms of street addresses and latitude/longitude) of various stores in a given vicinity. E.g. All Frys, Circuit Citys, Best Buys etc in my location. Now I want to find clusters where all of them are close to each other. So, for example, I want to find a cluster where a Frys store, Circuit City and Best Buy are all “close” to each other. Why? So that I can go visit all of them at once! I’m willing to travel some extra distance away from my location if I can find such a cluster. What’s an efficient algorithm to find such clusters?

Here’s a possible algorithm:

(1) Let S1, S2… Sn be the sets of locations of each shop. Pick the smallest one. For every shop s that has location (x, y) in this set:

(2) Find shops in each of the other Si that are in the location range (x +/- delta, y +/- delta), where delta is the threshold for determining what’s inside your cluster. These shops go into the “current cluster”.

Let’s analyze the runtime of this algorithm. For simplicity, assume that there are m sets of shops (S1… Sm) and that each of the sets has n elements.

Sort each of the sets both on x and y. Each can be sorted in O(n log n) time, and there are m of them, so this step takes O (mn log n)

Step (2) above can be done with a binary search (that’s why I sorted the sets first) in O(log n) time, and it needs to be repeated n times, so this step takes O(n log n) time.

So our total running time is O(mn log n + n log n) = O(mn log n).

The numbers of stores of which we’re looking for clusters, m, is usually a small constant less than 5. So we basically have an nlogn algorithm for doing this.
Does anyone know of a faster way of doing this?

I can’t imagine using delicious without this fantastic tool called Director. It uses a nifty trick to plant its own UI over a user’s delicious bookmarks page:

This project uses the only reliable loophole for executing foreign Javascript code: the bookmarklet bootloader. It works by inserting a