n3wt0n!

As I’m waiting for the Dell Inspiron Mini 9 to arrive, the one that I ordered December 30 and has an expected delivery date of January 22, I’ve been looking into ways to get the most out of the machine. My first (and as yet, only) concern is the lifespan of the solid state drive. I know, putting the SSD through regular use should yield a few years of use out of the SSD but I don’t put my computer through regular use. Even running Linux on the Mini 9 has me concerned about the log files that Linux generates. So I’ve been looking to touch the SSD as little as possible.

Along the way, I’ve come across an interesting concept. It appears that using the GMail API, one can set up a GMailFS (GMail File System) to read/write files to. Now I won’t go into detail with setting up GMailFS in Ubuntu Linux as it is messy and a pain. Even when I thought I had GMailFS working properly, it wasn’t working properly. It appears that you need to be a Super in order to access the mounted GMailFS drive or you have to go through the steps to assign groups and that’s all a process I didn’t have the patience for.

The GMailFS project isn’t new, it has been around since at least 2005. It just appears that there is no simple .deb package for setting it up (which has the benefit of being stable and easily upgradable). I may have to go step-by-step compiling from source rather than trying the old apt-get approach. Oh, did I mention there was no .deb package? I suppose there is, it just doesn’t work.

And for all the trouble it might take to set up, I’m still not sure if you can save a document and stream it directly to the GMailFS (bypassing the SSD and thus saving it some wear-and-tear) or if the document still saves to the SSD somewhere and then copies over. It would seem that, in theory, one might be able to stream the document from memory and straight to the GMailFS or vice-versa.

GSpace

With that in mind, I came across GSpace. GSpace acts as a kind of FTP client plugin for FireFox that lets you transfer files from your PC and store them in a GMail account. It’s nifty cool and why not take advantage of the 7GB+ of storage that GMail offers.

The downside, it seems that if you transfer too much in a day that you risk the account being locked for 24 hours. Also, as with FTP, the transfer speed is limited by your bandwidth and the bandwidth of the GMail server. The files still must sit on your harddrive in order to transfer them over (no saving directly from a text document to GMail) so you’re still putting wear and tear on the Mini 9′s SSD.

For the time being, at least until I can confirm whether or not GMailFS streams from memory directly to GMail and vice-versa, I’ll be storing my documents in my newly-created GMail account via GSpace.

Here’s a thought experiment for you.

You’re on a game show and you are given the opportunity to choose from three doors. Behind one door is a great reward. Behind two of the doors are goats (which you probably don’t want to win).

You choose one of the doors but the host says he will open one of the doors as well.

Say you chose door A and he opened door B. Now he presents you with the option of changing the door you originally chose, A, and switching to door C.

Is it in your interest to swap doors?

Interestingly enough, yes it is. How so? Consider this.

The host opened up “every door but yours and another door seemingly at random”. What if the host had done so with 100 doors? You choose door 17, he opens every door except door 97. Now there are 98 open doors and 2 closed doors. The host knows which door has the prize and he knows that you originally had a 1 in 100 chance of choosing the winning door. Effectively, the host now turned your odds to almost a 99 in 100 chance of choosing the correct door if you make the switch.

Whether it was 100 doors or 3 doors, the odds better favor you if you always make the switch.

You see that, right?

Well… Write a simulation and figure it out.

Question: “How do I read in input from a C program” or “How do I read input from the command line in C” ??

Answer: Easily

Aside from the usual inclusion of stdio.h and stdin.h you just have to loop through the char* array in main.

#include <stdlib.h>

#include <stdio.h>

int main(int argc, char* argv[])

{

    int i;

    printf ("Number of arguments provided: %d\nThey are:\n", argc);

    for(i=0;i<argc;i++) {

        printf ("%s\n",argv[i]);

    }

    return 1;

}

The above snippet outputs the following:

./ProgramName MyArgument AnotherArgument

Number of arguments provided: 3

They are:

./ProgramName

MyArgument

AnotherArgument

With the traditional C main method, argc gets the number of arguments provided at the command line. Also, this example assumes the name of the program is “ProgramName” (in C the program name is always the first argument).

A co-worker of mine and I were having a discussion about prime numbers and how to calculate them. I clearly recall that very early in my Computer Science schooling that I was given a “Find all the prime numbers between 1 and N” programming assignment.

I admit that from a first-year perspective that I attacked that assignment with brute force. I thought the best way to find those primes was to write an “isPrime(int x)” function and loop from 1 through N checking each one. In my mind I was certain that the way to check if a value was prime was to start by performing modulus on it N % (N/2) and inner-loop my way down to 2 to check if the value was divisible by another number.

WRONG! There is another way to find all the primes from 1 to N and it is this:

1. Start looping i from 2 to the square root of N
2. For every value of i remove every multiple of i there-after (meaning that a value of 2 ensures that every even number is removed from the list of prime numbers, 3 then removes every value divisible by 3, etc)
3. Skip over values that have already been removed
4. When i has reached the square root of N then you are left with only the prime numbers between 1 and N

Here is a benchmark of just how quick (using C) the prime numbers between 1 and 2 million can be found. Note, by default my program prints every value to terminal so I piped it into a file (which I can open and evaluate for proof that only prime values are left).

time ./FindPrime 2000000 > dat.dat

real    0m0.142s
user    0m0.136s
sys     0m0.008s

The method described is called the Sieve of Eratosthenes. Here is my source code for the exercise. Happy programming.

I’m going to get to the point. I’m writing this so you don’t have to spend a whole lot of time scouring the ‘net in search of a solution to your homework assignment.

In later years (2nd, 3rd, 4th) professors get heavy on the subject of efficiency and really analyze algorithms (thus, courses aptly named algorithm analysis). This is where “Big-O” notation comes in to play.

If you’re anything like me, that didn’t make too much sense at the start. Even now I can’t think of when I might actually compare the runtime of an algorithm to the graph created from n² or n log n. However, what algorithm analysis has given me is the understanding that programs that take a really long time to run can usually be improved upon. And if there’s an algorithm that takes a long time to run that hasn’t yet been improved upon then there is often a prize for the person who can improve upon it (or who gets lucky).

With that being said, let’s look at those three sorting algorithms again.

Bubble Sort is said to have a runtime of O(n²) at worst. What does that mean to you? Well, it means that this sorting algorithm sucks for every day use. But we’re human, and that means we can learn from this mistake. Don’t use bubble sort, but maybe give your professor a hard time about it. Squeeze it into another program somewhere, as a joke. No, don’t listen to me.

Insertion Sort is another example of a sorting algorithm with a worst-case runtime of O(n²). Though it has the same runtime complexity as Bubble Sort, don’t be fooled into thinking that Insertion Sort is always just as slow. Insertion Sort is still worlds more efficient at sorting than Bubble Sort.

See that!? Insertion Sort takes care of 150,000 unsorted values in 1/5 the time it took Bubble Sort to sort the same values. But there is still a quicker way to sort…

Quick Sort is the last algorithm in the scope of this article. The algorithm is just that, it’s quick. Quick Sort has an average runtime complexity of O(n log n) which is a huuuge improvement over Insertion and Bubble Sort.

And in case you are curious, this is what n² looks like when graphed.

And what n log n looks like when graphed.

And when the two are compared you can see a massive difference:

If you feel so inclined to play around with sorting algorithms, the source code for my sorting demo can be found here or on the files page.