Algorithms

It’s been a while since I last posted to this blog, mostly because I’ve been incredibly busy being a dad, moving to a new appartment and a new job (I’ll blog about that one).

Nevertheless, I recently found an excellent excuse to finally work on my basics, so I got myself a copy of Introduction to Algorithms (not the Knuth, but still extensive) and began to deepen my knowledge. I’m enjoying it so far, and there’s lots to learn since the topic wasn’t covered in such detail at my university.

Nearly everybody I told about my endeavour said I’ll never need that knowledge. I respectfully disagree. Sure, I probably won’t need to implement sort or matrix multiplication algorithms in my day job, unless that day job involves low level systems programming. But algorithms are everywhere, and studying them doesn’t mean to learn all the existing ones by heart, but mostly to learn how to design efficient algorithms for any problem. The most useful skill is in my opinion to transform real-world problems into problems for which a proven efficient solution already exists, graph problems for instance are everywhere, visible only to the trained eye.

Since all mathematical proofs and no code make Felix a dull boy, I decided to implement every single algorithm explained in the book on algorithms.ubercode.de. I’m also using this as an opportunity to make my first pure HTML5 site and to try Node.js.

The one thing I’m not happy with is that I had to use in-place algorithms in order to visualise the sort process. For instance, my implementation of merge sort originally looked like this:

function merge(array1, array2) {
    var array = [];
    // Merge array1 and array2 into array
    return array;
}
 
function sort(array) {
    if (array.length == 1)
        return array;
 
    var middle = Math.floor(array.length / 2);
    return merge(sort(array.slice(0, middle),
                 sort(array.slice(middle));
}

I find this a lot more readable than what I have now. But since this is a recursive implementation, I wasn’t able to regularly send the whole array from the worker to the main script in order to display the process. The current algorithm modifies the array directly, not returning anything, which clutters the function calls with various indizes and bloats the code. On the other hand, this is very close to the pseudo code in the book, and the performance is likely better. Still, let me know if you can think of how to update the progress with a functional implementation.

Leave a Reply