# 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!

# 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.

# 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.

# 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.

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;}`