Michael Dowse

Last semester I took a paper called Algorithms and Data Structures. On of the topics we covered was non-comparing sorts.

Most sorting algorithms are comparing sorts in that they put a sequence in order by comparing values to each other and putting lower ones before higher ones. 

Non-comparing sorts allow us to sort a series of numbers without ever comparing them to each other. Counting sort is a well known non-comparing sort. There is a cost to non comparing sorts though, Counting sort only works when we know the range and minimum value of the data to be sorted*.

Say we want to sort this sequence of numbers and we're told that they are all less than 10 and greater than 0:

5, 7, 3, 2, 1, 3, 2, 4, 8, 5, 9, 2

1. We calculate the range of the sequence and create an array of that size with all values set to 0. Here the range is 9 (max - min + 1) so we create an array like this:

 0  1  2  3  4  5  6  7  8      << Index
[0][0][0][0][0][0][0][0][0]     << Value

2. We move through the sequence of numbers incrementing the corresponding cell in our new array. The first number is 5, so we subtract the minimum to calculate its relative location. 5 - 1 = 4. Now we increment the value at index four in our array like so:

 0  1  2  3  4  5  6  7  8
[0][0][0][0][1][0][0][0][0]

We repeat this for the rest of our sequence. The finished array should look like this:

 0  1  2  3  4  5  6  7  8
[1][3][2][1][2][0][1][1][1]

3. Almost there, now we just need to print out the result. Moving through our array we print out the index of each cell a number of times as denoted by the cells value.

Don't forget we need to add one to each value because the array indexes start at 0 but our data range starts at 1, this can be thought of as an offset.

1, 2, 2, 2, 3, 3, 4, 5, 5, 7, 8, 9

There you have the initial array sorted without ever comparing one value to another.

* You could calculate the maximum and minimum (and derive range) beforehand and then perform counting sort, and this is often done, but it requires comparing values.

I forgot to mention I'm back in Wellington for the summer.

I recently got an email about Scholarships from Intergen (all CompSci students got the email, I'm not special). I visited Intergen in 2007, it's a really cool company. I won't be applying but I read the scholarship form anyway. I loved the questions. I hope they don't mind me publishing them here.

Where do you think your interest in IT came from initially?  Why did you choose to study it and make a career out of it?

Do you have a technical blog?  If so what is it?

Tell us about your ideal role

What are your short and long term career goals?

Have you done any IT work on your own accord – i.e. not a university project but something like building a website for a friend, or an application to catalogue your music collection etc?

Do you have a computer?  What kind?  What do you use it for?

What do you know about Intergen?

What are your interests? What do you do in your spare time?

Why do you deserve this Scholarship above other students?

How do you think this Scholarship would benefit you and what would you get out of it?

I read this article (Family in strife after kids left alone in park) this morning and I've been thinking about it all day. Here's a summary of the article: After making them prove they are capable of doing so, a father lets his children play alone in the park. Someone freaks out and calls CYF who decide to investigate.

What really got me thinking was a quote in the article from Peter Gerrie of Barnados:

We all pine for all the old days when it was totally safe to let your kids play at the park alone, but those days have gone.

I hear this all the time. I get the impression that in the 60's and 70's when my parents were growing up it was perfectly safe to for children to play unsupervised, and now there are pedophiles hiding in every bush. The sentiment that our communities are not as safe as they used to be is incredibly prevalent. So prevalent perhaps that no one questions it. I'll take the bait.

What changed? Is our society falling to pieces? Not really. Are there more pedofiles now than when my parents grew up? Maybe, it's difficult to research. I honestly don't know what's going on. Enlighten me.

Are our communities more dangerous or is that just something parents tell themselves to justify being overprotective?

I'm sure you know who Soulja Boy is but here's a refresher just in case. He's the gangster rapper behind such hit singles as Crank Dat and Soulja Girl. He took over the charts in late 2007. He's renowned for lyrics such as “Superman dat hoe” which may or may not be sexual innuendo. Now he's back with a new single out called Kiss Me Through The Phone, you probably won't like it.

His first single, Crank Dat, could have been a fluke. Maybe. But he followed it up with Soulja Girl which was another huge hit. I was running a radio station at the beginning of 2008 and we played Soulja Boy at least as much as Crank Dat. Now, it's 2009 and he's all over the radio again. That doesn't sound like a one hit wonder to me. How did he do it?

"When I first got my computer, I was 12," says Soulja Boy, adding that "it got me where I am." - Washington Post

He used social media. Sure, he had opportunities and advantages (his dad just "provided a recording studio") but his success was primarily due to the grassroots fanbase he built using social media. Let me explain. For our purposes the Soulja Boy story begins in 2005:

"He started making beats and songs and then turned to the Internet. He began uploading tracks to SoundClick.com, where artists comment on one another's songs. Getting good feedback, Soulja Boy borrowed a cousin's video camera and uploaded videos of himself and friends doing popular teen dances." - Washington Post

Sounds like the perfect start to a social media success story! After this initial encouragement Soulja Boy started posting his music on YouTube and MySpace where it was well received by HipHop fans. His YouTube video for Crank Dat got over 3 million views and his MySpace page broke the record for most page views. Ever. That's a serious grassroots fanbase. This success earned a lot of respect from fellow musicians and attracted the attention of the producer Mr Collipark.

"Tell that dude to call me. He could do my MySpace page, 'cause I need one. I want that little dude to blow me up on MySpace like he blew up. I'm being real as fuck. He got that MySpace shit goin’ nuts." - Scarface

He soon signed on to a major label and become a mainstream star but his roots were firmly in the virality of social media. In October 2007 he released his first album, titled SouljaBoyTellem.com. His album name was his domain name. That sounds like something my $500/hour social media consultant would suggest.

It's easy to discount him because he used Myspace and Youtube instead of Facebook and Vimeo but he used the right medium for his audience. Even now that he arguably doesn't need social media he uses Vimeo for his vlogs and has a respectable 550,000 followers on Twitter. His official website, SouljaBoyTellem.com, is a Ning network.

I'll leave you with a quote from Soulja Boy himself [referring to Lil Bow Wow]. If nothing else I hope this convinces you that gangsters use the internet too:

"we Wikipedia-ed this nigga, this nigga was born in 1958...you was born before the Internet was created; how the fuck you even find me?" - Soulja Boy

What is the single most useful metric in measuring the spread of Swine Flu? I'm no doctor but I would think the most important metric would be the number of people who have Swine Flu. The media seem to agree. The main number being thrown around is the number confirmed cases of Swine Flu.

So how many confirmed cases of Swine flu are there in New Zealand right now?

"The number of confirmed cases of swine flu has risen to 86, an increase of 15 from yesterday, Health Minister Tony Ryall said today." - Stuff.co.nz

This means that 86 people in New Zealand have Swine Flu right? Not quite. Stuff got that information from the latest bulletin released by the Ministry of Health. Here's a direct quote from that bulletin:

"The cumulative total of confirmed cases in New Zealand is now 86 up from 71 yesterday. Of these, 66 are current cases being treated in isolation." - Ministry of Health

Stuff chose to only mention the cumulative total rather than the number of current cases. The 20 people who Stuff counts as cases but do not currently have Swine Flu are those who were infected but have now recovered (no deaths in NZ at this point). This number that the media keep touting, which increases every day, is the total number of Swine Flu cases in New Zealand ever. Not the number of people currently infected.

This becomes even more deceptive when the media emphasises the increase in cases. In an epidemic, the number of people infected starts of small, then it increases until at some point it peaks, then it decreases again. I don't need a medical degree to work that out. So in a very general sense an epidemic would look like a bell curve.

Do you see the problem yet? The media are reporting the number of cumulative cases instead of current cases. Instead of a bell curve this would graph as a constantly (but not steadily) increasing line. The number of cases is always increasing. Even when the epidemic is almost over, the number of cases is still increasing!

As I said earlier, I don't have a medical degree, but cumulative cases seems a ridiculous metric to use to measure the current threat posed by Swine Flu. It's deceptive and it feels like scaremongering. Please stop it.

Disclaimer: I'm not a doctor, I know nothing about epidemics, don't take me too seriously.