www.steveneely.org

Shuffles & randoms

steve — Wed, 20 Jan 2010 18:19:43 +0000

I was asked a question about shuffling yesterday which got me thinking. How do you write an algorithm to truly shuffle a deck of cards without any bias?

There are a couple of well-known algorithms to do this, both popularized by Donald Knuth. At a very abstract high-level they are:

generate a random number for each card in the deck then sort the cards by number. If two cards are assigned the same number then try again;
go through the deck, taking each card in turn and swap it with some random position in the deck.

Clearly #1 could take a longer time to run since you’ve got to sort cards and deal with clashes. Although with only 52 cards in a deck you are probably not too worried about algorithmic complexity.

#2 looks good on the surface but there are a few gotchas to be aware of. With a deeper mathematical analysis you can see why. The first is that if you swap cards with any position in the pack you will not get an even distribution with shuffles. This is because you’ve written an algorithm that has n^n execution paths and there are only n! permutations. Using the wikipedia example consider just 3 cards: your algorithm can produce 3^3 = 27 outcomes but there are only 6 permutations for shuffling. You cannot fit 27 into 6 so there must be some outcomes from your algorithm that are more likely (see pigeonhole principal).

The solution is to swap with the portion of the pack that has not yet been swapped with.

Wikipedia has a clear article on shuffling and implementations with further details on the impact of using the mod operator with random numbers (again, the space of randoms being generated then having mod applied is not an even distribution). A final note is that you need to seed your random number generator or it’ll be pseudo-random. Or better yet use random.org

Bookmark and Share

Location based services for mobiles

steve — Fri, 08 Jan 2010 15:49:53 +0000

Location based services have been around for a number of years in the research community. They were always fun to build and excellent research vehicles but needed something to change before hitting the streets. Well, now we’re beginning to carry GPS enabled devices these services have hit the mainstream. I regularly use Yelp and Around Me on the iPhone to find local restaurants, gas stations, and coffee shops. The integration with the maps application is a fantastic coupling. Now Google have released their search services with the “Near me now” service (iPhone and Andriod in US only).

Location data for these applications is usually derived from GPS readings but it is not limited to that. You can use wifi spotting, video capture, parse user calendars or discover location by inference (I am near Alice and Alice knows where she is so I can find where I am). But in practice are these other inputs really required? Or are they all part of a larger model of the real world?

Location based services are a manifestation of pervasive computing in the real world. Next will come more complex context aware services with social aspects and recommendations. I’ve oft heard the question “who will pay for the infrastructure for pervasive computing?”. I think the answer is still “we will” but now you can add “and already are”.

Bookmark and Share

Installing dd-wrt on a Linksys WRT160N-RM v.3

steve — Tue, 08 Dec 2009 00:33:54 +0000

So I cheaped out and bought a refurbished Linksys WRT160N from Amazon for $28. Great price for a 802.11n enabled router (most are in the $100 range) but it kept dropping wifi connections, slowing up and refusing to respond. Wired connections were fine so I suspected a dodgy radio. Linksys support couldn’t fix the wifi issues so I was about to send it back when I decided to wipe the Linksys firmware and flash dd-wrt to it. The router wasn’t doing much anyhow.

The latest version of dd-wrt supports the WRT160N v.3 router. It is easy to install via the router’s web admin interface and rather than repeat myself here I’ve updated the dd-wrt community wiki page with the step-by-step instructions.

Note: when you search the dd-wrt router database it’ll give you back three different bin files to choose from. You only need one of those to kick off: dd-wrt.v24-13309_NEWD-2_K2.6_mini_wrt160nv3.bin AKA “mini” is the basic dd-wrt firmware that I used. It has more than enough features to keep most users happy.

My router has been up and running with dd-wrt for the last 4h29m without any problems and it feels faster (not sure if that is psychological). The best part is that the nerd in me is now super excited to have a working, fully featured, Linux-based router in the office.

Bookmark and Share

Construct at University of Colorado at Boulder

steve — Mon, 07 Dec 2009 16:51:32 +0000

I’ve been talking with faculty staff at CU CSCI about the kind of work they’re doing and to see if there is any projects that we might collaborate on. After a chat with Katie Siek we decided that the most efficient way to introduce my research from UCD and Glasgow was to drop by and give a presentation.

For the opening I talked a little about the data binding technologies we developed at Strathclyde. These “type projection” systems provide a safe and extremely efficient mechanism for computing over semistructured data sources (if you’ve ever used JAXB from Sun they’re kind of similar). I skipped pretty quickly over that, hopefully didn’t loose too many listeners, and jumped into Construct.

Construct is our open-source community platform for Pervasive Computing. It is a middleware that provides the plumbing for developers of Pervasive or Ubiquitous systems. Rather than spend time writing code for management of services and data flow across the network developers can concentrate on the problem domain for their specific project.

I was invited back to talk with Ric Han’s group early January.

[slides]

Bookmark and Share

Tiddlywiki

steve — Mon, 02 Nov 2009 20:54:42 +0000

I’m a note writer.

I’ve got Google docs full of notes, dropbox notes, iPhone notes, plain text files for GTD, and inked back-of-envelopes everywhere. Or at least, I did.

After a pointer from a friend and colleague I decided to consolidate and digitize my notes using TiddlyWiki. TiddlyWiki is a personal wiki wrapped up in a single web page. Because key text automatically hyperlinks (these are called wikiwords) a TiddlyWiki can be thought of as a “non-linear notepad”. You don’t write or read from top to bottom but rather jump from “tiddler” to tiddler.

A tiddler is a block of text or a given topic. Collectively they form your TiddlyWiki. Let me try explain better with my Getting Things Done Tiddler. I’ve got a GTD note (a tiddler) in my TiddlyWiki that links to three other notes: ToDo, Done, and Waiting. Clicking on any of these three opens a new note with a list of either “todos”, “done stuff” or “waiting on something”. Within each of these are further links to notes on tasks in my every day life.

TiddlyWiki is immediately useful to anyone with a modicum of HTML knowledge. If you know what

Bookmark and Share

Google Wave

steve — Mon, 12 Oct 2009 16:49:51 +0000

So I’ve been playing with Google Wave for the last couple of days and I’m still not sold on it. Perhaps because of all the hype, and hyperbole descriptions that say things like Wave is what we’d have “if email was created today”.

When you first log in to Wave you’re presented with a set of panels. These are for navigating through your folders, selecting contacts and participating in Wave conversations. Waves are a mix between email and IM. You can edit/add comments to any section of the conversation and these appear in real-time to other online participants. This Techcrunch article sums up the abstract concepts nicely by grouping e-comms mechanisms as passive-aggressive.

The Wave team have integrated a widget model (like those on iGoogle home pages) to allow programmers to extend the environment. Of particular note is the Ribbit teleconferencing application that makes use of this API. It allows you to jump out of written Waves and into a phone conference call. I’m less excited about the Sudoku app.

To get going I created a Wave to discuss Wave with my friends and colleagues who are also beta testers. So far the poll I posed has 4 votes for unimpressed and zero for impressed. Since Google are performing a slow roll out of Wave it looks like they’re testing the water to see how people use it. The ingenuity of the online world can often produce some unexpected uses of new technologies. I’ll be interested to see what happens with this one.

Bookmark and Share

Augmented reality steps closer

steve — Wed, 12 Aug 2009 14:54:05 +0000

BBC tech News is reporting on mobile phone handsets with augmented reality. The article says that this is the first time AR has been available on handsets which is not strictly true. In CIS at Strathclyde University we had MSc students developing prototype map assistants on handsets with AR back in 2003, and I’m sure we were not the first. Maybe the BBC mean this is the first time AR handsets have hit the mainstream.

If you read the article bear in mind that the cyborg theme is erroneous and misleading. Yet another UK media attempt to glamorize a story and attract attention. Regardless, the technology is very cool. Sign me up.

Bookmark and Share

Network Addressable Storage

steve — Thu, 02 Jul 2009 11:10:39 +0000

We’ve got a bunch of USB hard disks at home that are used for backup and media storage. I’m fairly good about plugging them in and running backup utilities (rsync and SyncToy, mostly) but it is a bit of a pain. So I spent an hour looking at options for network addressable storage.

You can now buy a USB to Ethernet dongle that shares disks over the network. They come in a variety of flavours: feature-low Newlink [£26] which says Windows only; Addonics [£37] which has a load of extra features such as BitTorrent, iTunes, SMB/Samba, XBox media (great review at crunchgear.com). I’m not sure if you can put a USB hub on either of these and access multiple drives.

Another alternative would be to take the drives out of their USB enclosures (they’re usually just laptop or 3.5″ drives) and put them into a NAS enclosure. I found these enclosures on ebay for as low as £13. Again, prices and features vary for them — the Newlink offering at Amazon gets decent reviews for the price [£27].

The final goal is to create a multi-disk box with RAID on an Ubuntu Server. I’ll use that for all backups, media and remote storage. By setting up port forwarding on a home router I’ll be able to access them from anywhere in the world. I’ll wait until we’ve moved into our new home before working on that.

Bookmark and Share

Post from Google Reader shared items to your Facebook profile

steve — Sun, 24 May 2009 21:43:46 +0000

I’ve just figured out how to post from my shared items in Google Reader (and this blog) to my Facebook profile. Log in to Facebook and click on the profile tab. Under the “share” button is a “settings” link. Click on that link and you should see the Google Reader option there (and Digg, Pandora, Blog/RSS, Flickr, Picasa, and much more).

To find the public link to your Google Reader shared items go to http://www.google.com/reader/view/user/-/state/com.google/broadcast and look for the text that says “Your shared items are available publicly at this web page“

Bookmark and Share

So long desktops

steve — Tue, 12 May 2009 06:27:03 +0000

Reflecting on people and places I’ve visited the home desktop PC seems to be a thing of the past. Now you can buy tricked out consoles for gaming, e-readers, lightweight netbooks and smart phones for connectivity on the move. Why would we want desktops in our homes?

This morning I was listening to a discussion with Leo Laport on the TWiT podcast [from 3 May] in which they were discussing Apple’s aquisition of chip designer P.A. Semi and what this meant. On the Apple jobs site a quick search for hardware turns up a bunch of new posts for hardware engineering positions so there is movement in that space. I subscribe to the theory that Apple will start designing their own chips for mobile devices with the longer term view of dropping desktops and eventually laptops (they just started with Intel chips in desktops/laptops so I don’t think they’ll design for those).

What the TWiT podcasters didn’t pursue was where the long view of this takes us. Underlying the chat of so long to the desktops are the first trickles of pervasive and ubiquitous computing. To paraphrase Mark Weiser, it is certain that computational machinery is disappearing into the fabric of everyday life. That is now never a question. Yet we’re still a long way from the ubiquitous support system envisaged as omnipresent smart dust that unobtrusively manipulates our world in our benefit.

It will take a whole new set of standards and technologies in spaces such as location, context, communications, and human understanding before we can start to see this next generation of technology in everyday life. The reason that Apple may have a big advantatge here is that they like to live in a closed world of machines, networking, peripherals and storage. This means that their systems can work together right out the box. All-Apple environments can safely rely on homogeneous hardware and software in which to operate.

So what about Windows? After the Vista debacle it is likely that Windows 7 will be the penultimate desktop OS from Microsoft. Their research labs already host world-class minds who are working towards the Weiser-world.

Bookmark and Share