Algorithms, what is it good for?!

So I’m going to hop on the bandwagon and follow suit with the lovely Mia and Jessika and write a bit about courses!

Hopefully this’ll give you a taster of what a nearly-done-bachelor-student does on their last leg.

Algorithms, Operating Systems, Discrete Mathematics, Web Engineering and Undergraduate thesis – that’s the whole palaver. You might note that these are only 5 courses and I’ve been moaning about 6; I dropped Korean, sometimes we have to be kind to ourselves to survive.

Anyway, chances are that you’re not completely familiar with what those courses entail, I know I wouldn’t have been a while back. I’m going to try and give you the short of it.

Algorithms – in essence it’s solving a problem with a step-by-step solution. That’s all it is. Yet it can still be a headache – oh damn the time complexity is quadratic, I wonder if I can make it into an n log n algorithm… In algorithms we have to think about the efficiency of our solution – in both time and space, which is much more intuitive than it seems. I was literally flabbergasted the first time the notion was presented to me, it made zero sense. Obviously the wrong person introduced it to me, I got it straight away when reading about it online.

Anyway; heard about the Fibonacci sequence? (you probably, if not directly, indirectly have. Da Vinci Code anyone?) If you’d study Computer Science you’d hear about it every other day (ok, maybe not that often), it’s just one of those super popular examples.

The sequence is 0 1 1 2 3 5 8 13 etc

Think about that for a second, what is it that defines the next number in the sequence? Look at the two numbers before it; yep it’s the sum of them.

So – if we want, say, the fifth Fibonacci number we want to compute the sum of the two numbers preceding it. So that’s 3rd and 4th Fibonacci number. One way to compute this is to merely compute n-2 + n-1 (where n is 5 in our example) until we have our number (which will seem like magic but if you think about it we have to go backwards till we hit that 0 and 1 and when we have them work ourselves back to our number). Actually that might not make sense (look at the tree, which is this thing just below).

Note all those repetitions!

And another way is to save these preceding numbers in some fancy fashion.
The difference between these to solutions is HUGE!!! I’m telling you this because I want you to understand the notion of efficiency. It’s interesting, maybe it’ll spark your curiosity, and I’m hoping so.

Why is it such a huge difference you ask? Well, it doesn’t really make a difference for small numbers, but if you want the 1000th Fibonacci number you’re going to be in trouble solving it the first way. This is because you’re re-computing the same Fibonacci number over and over again; you’re just not making use of all those computation! If you want to talk running time it’s a programmer’s worst nightmare, it just gets worse and worse… and worse. On the other hand if you save these preceding numbers in some sort of list that also tells you which Fibonacci number it is (the place in the list will simply do that for you, you can just fetch these number without having to recompute them. OK, so maybe this isn’t making much sense. Hopefully looking at the illustrations will make what I’m rambling about understandable. These two solutions illustrate time and space in a great way, in the first one we’re pretending time is no issue, which is illegal in this field. In the second solution we’re saying that hey so we’re gunna need store those values we’re computing, that’ll save us a great amount of time – which is great practice. We’re basing our solution on facts and logic, we’re being engineers! It’s like Einstein said about time and space, space equals money. Actually, he didn’t, I just did.

Thinking of problems in this manner starts to hardwire us to look them from lots of different angles, which is important in lots of different fields.

OK, so I didn’t tell you anything about the other courses, I rambled about some sequence and told you that it’s interesting. It definitely is and it’s a piece of cake if you allow yourself to see it that way and give yourself time.