Finding Median in (Almost) Linear Time

I sometimes find myself needing to find the median of a set of numbers. What I would do was sort the list of numbers and then take the value in the middle index, something like(in Java):
    public static int FindMedian(List <Integer> nums)
{
Collections.sort(nums);
if(nums.size() % 2 == 0)
{
return (nums.get(nums.size() / 2) + nums.get((nums.size() / 2) + 1)) / 2;
}
return nums.get(nums.size() / 2);
}

This solution is on the order of O(n lg n) where n is the number of elements. A faster method would be use a modified quick sort. The idea being that after each partition we gain some knowledge about how many numbers are less than or equal to a given number in the list. So we can be smart and only iterate on the side of the list where we know the selected number is. Here is my implementation of QuickSelect in Java:

public class QuickSelect {
public static < T extends Comparable > T quickSelect(List < T > values, int k)
{
int left = 0;
int right = values.size() - 1;
Random rand = new Random();
while(true)
{
int partionIndex = rand.nextInt(right - left + 1) + left;
int newIndex = partition(values, left, right, partionIndex);
int q = newIndex - left + 1;
if(k == q)
{
return values.get(newIndex);
}
else if(k < q)
{
right = newIndex - 1;
}
else
{
k -= q;
left = newIndex + 1;
}
}
}
private static < T extends Comparable> int partition(List < T > values, int left, int right, int partitionIndex)
{
T partionValue = values.get(partitionIndex);
int newIndex = left;
T temp = values.get(partitionIndex);
values.set(partitionIndex, values.get(right));
values.set(right, temp);
for(int i = left; i < right; i++)
{
if(values.get(i).compareTo(partionValue) < 0)
{
temp = values.get(i);
values.set(i, values.get(newIndex));
values.set(newIndex, temp);
newIndex++;
}
}
temp = values.get(right);
values.set(right, values.get(newIndex));
values.set(newIndex, temp);
return newIndex;
}
}

From here implementing FindMedian should be pretty straight forward. The nice thing about this algorithm is that it can find any kth largest number in a set. Plus on average this will run in O(n) with a worst case of O(n lg n). Enjoy!
Read More

Averaging A Group's Salary

I recently wanted to find the average starting salary for some recent college graduates that had also worked at Surface Systems and Instruments. As most people know it is rude to ask what someone's salary is and can cause awkward situations. So I came up with the following algorithm to get a group of people's average salary without disclosing any information to anyone else, except for the average of course.

Person 1 comes up with a random number k. k should be much larger than person 1's salary. Person 1 should compute S1 + k, where S1 is person ones salary. Person 1 then tells person 2 and only person 2, S1 + k.

Person 2 takes S1 + k and adds S2 to it. Then gives person 3 S1 + k + S2.

Person 3 takes S1 + K + S2 and adds S3. Then gives it to person the next person.

On this goes till n people, where n is everyone we want the average salary of,  has added their salary to the running sum. The last person gives S1 + k + S2 + ... + Sn to person 1.

Person 1 subtracts k from S1 + k + S2 + ... + Sn and is left with S1 + S2 + ... + Sn. To compute the average, Person 1 simply takes (S1 + S2 + ... + Sn)/n and can then share it with everyone.

In order to make this secure, n must be grader than 2 and no person can give their sum to anyone else besides the next person in the line. Unfortunately, this does suffer from an attack. If person a and person a+2 want to know person a+1's salary, by subtracting the sum person a gave person a+1  from sum person a+1 gave person a+2.

So this is a fun method. My goal was to make it simple and practical to use. If you can find any other attacks please let me know.
Read More

Dual Monitor Aero Snap in Ubuntu

I think the coolest thing about Windows 7 is Aero Snap. It really helps you get more efficient use of your screen real estate without you have to manually resize your windows. The good people at OMG! Ubuntu posted a great tutorial on how to get Aero Snap in Ubuntu. I followed the tutorial and got my laptop snapping perfectly. I was not so lucky on my dual monitor desktop. So I have modified the script slightly to make it so it will now work on dual screen monitors. Most of this is exactly the same as the OMG! Ubuntu tutorial, so if you feel I didn't explain something clearly you should reference theirs.

Step 1 - Install Compiz Config

sudo apt-get install compizconfig-settings-manager wmctrl

Step 2 - Set up the commands

  • Open the Compiz Config manager (System -> preferences -> CompizConfig Settings Manager)

  • Select the "Commands" option

  • In "Command Line 0" past:



WIDTH=`xdpyinfo | grep 'dimensions:' | cut -f 2 -d ':' | cut -f 1 -d 'x'` && HALF=$(($WIDTH/4)) && wmctrl -r :ACTIVE: -b add,maximized_vert && wmctrl -r :ACTIVE: -e 0,0,0,$HALF,-1


  • In "Command Line 1" past:



WIDTH=`xdpyinfo | grep 'dimensions:' | cut -f 2 -d ':' | cut -f 1 -d 'x'` && HALF=$(($WIDTH/4)) && LOCATION=$(($WIDTH-$HALF)) && wmctrl -r :ACTIVE: -b add,maximized_vert && wmctrl -r :ACTIVE: -e 0,$LOCATION,0,$HALF,-1


  • In "Command Line 2" past:



wmctrl -r :ACTIVE: -b add,maximized_vert,maximized_horz


Step 3 - Enable the commands
Go to the 'Edge Bindings' tab and set the following:

  • Run Command 0 - Set to Left

  • Run Command 1 - Set to Right

  • Run Command 2 - Set to Top



Good luck, let me know if you have any questions.
Read More

SuperComputing 2010

I managed to talk the K-State CIS department into sending a team, including myself, to SuperComputing 2010 to compete in the student programming contest. As a team of 5 members we had a combined total years of experience with super computers of about a year. To our surprise we placed third. So looks like we are going to try going for gold next year in Seattle, WA at SuperComputing 2011.

If you are interested in the questions you can find them here.
Read More

in_addr to string(char*)

The other day I needed to turn a IPv4 address to a string in C. I figured some others would find it useful:


char* hexToCharIP(struct in_addr addrIP)
{
char* ip;
unsigned int intIP;
memcpy(&intIP, &addrIP,sizeof(unsigned int));
int a = (intIP >> 24) & 0xFF;
int b = (intIP >> 16) & 0xFF;
int c = (intIP >> 8) & 0xFF;
int d = intIP & 0xFF;
if((ip = (char*)malloc(16*sizeof(char))) == NULL)
{
return NULL;
}
sprintf(ip, "%d.%d.%d.%d", d,c,b,a);
return ip;
}
Read More

Android 2.2.1 Released(the unofficial change log)

Early last week, I received a notice on my Nexus One that Android 2.2.1 was available for download. I was surprised but excited none the less. So I quickly searched the web looking for any and all information about what was new. It turns out that a number of people had posted that the new version of Android was available but no one had any kind of change log.

Well now that I have had the update install on my Nexus One for a week I think I may have found the extent of the new features:

WiFi finally works correctly. A number of Nexus One users have had a hard time getting their phone to auto connect to known WiFi networks. I believe it had something to do with it would stop after one failed attempt to connect at the fringe of the network. Well now this is fixed, in fact my battery life nearly cut in half the day after the update. I had my WiFi sleep options set to "never turn off." Before the update, this was not actually an issue due to the fact my WiFi was never actually connected. However after the update my phone is almost always connect to the campus WiFi as would be expected. So I turned back the sleep options to turn off when my screen was off and my battery life went back to normal.

Different color status lights. I was told, when I purchased the Nexus One, that the track ball would glow different colors depending on the type of notification you have. I was sad to see that not to be the case when I got the phone. With Android 2.2.1 my track ball now sometimes glows green instead of the white. Email, text message, and missed calls all seem to glow white. While things from Google voice, like texts or missed calls, make it glow green. I can't seem to find any options on how to switch this or try to get it to glow any other color. It seems silly to make a device that can glow either green or white, perhaps it does more but the feature to set it has not been fully integrated in the phone. Hopefully the next update will complete this feature.

I am sure there are a number of other updates, most likely security updates. I hope that in the future Google makes it a point to release some sort of official change log so that people are not just guessing. Let me know if you have found anything else new with Android 2.2.1.
Read More