Archive for March 2012
Whether you think about it or not, your computer spends much of its time sorting “things”. And there are numerous algorithms for doing this, each with varying measures of complexity and efficiency (for the interested reader, you can discover the wonders of sorting and searching in Volume 3 of Knuth‘s bible: The Art of Computer Programming).
Sorting algorithms also provide a gentle introduction to a variety of core computer science concepts, especially data structures and complexity. And what better way to learn some of the common sorting algorithms than through the medium of (Hungarian folk) dance!
For example, quicksort:
Or if you prefer a rather more mundane visualisation of quicksort:
(see more videos at the Algo-Rythmics website)
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.
There is another theory which states that this has already happened.
Today would have been the 60th birthday of Douglas Noel Adams, a writer who has had a profound impact on many people’s lives (including my own) due to his famous trilogy in five parts: The Hitchhiker’s Guide to the Galaxy. He was a staunch atheist (“Isn’t it enough to see that a garden is beautiful without having to believe that there are fairies at the bottom of it too?“), a serious fan of technology (especially the Apple Macintosh) and a passionate advocate for environmental and conservation causes.
DNA sadly died in May 2001 at the age of 49 (with his life celebrated every year on the 25th May by Towel Day), but his contribution to science fiction, comedy and satire lives on. I would have no hesitation in naming HHGTTG as one of my most treasured books; I regularly re-read it and it would certainly be top of my Desert Island Discs book list. If you have not yet had the pleasure, I urge you to do so.
I may not have gone where I intended to go, but I think I have ended up where I needed to be.
Douglas Adams (1952-2001)
I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years. In recent years, a number of program analysers like PREfix and PREfast in Microsoft have been used to check references, and give warnings if there is a risk they may be non-null. More recent programming languages like Spec# have introduced declarations for non-null references. This is the solution, which I rejected in 1965.
Tony Hoare (speaking at QCon London 2009)