As usual, my advice on Vegas is, don't bother. This trip, I've gotten sick (something flu-like), been fed far too much, sucked in a lot of signature smoke, been too hot outside and too cold inside, and now my flight home is indefinitely delayed due to mechanical problems (I'm now in the airport).
Unfortunately, I'm coming back in 2 weeks for the TopCoder Open. Oh well.
Saturday, September 25, 2010
Sunday, September 05, 2010
Visualising sorting algorithms
This is another one of my rare technical posts, as opposed to news of which countries I've been visiting.
If you're in computer science, you've probably seen an animation of sorting algorithms, maybe heard a rendition, or seen a visual representation. I have, somewhat by accident, discovered a different way to visualise a sorting algorithm: plot points for memory accesses, with address on the X axis and time (counted by accesses) on the Y axis, and different colours for reads and writes. It produces some rather pretty pictures. Note that these are not to scale relative to each other - the Y axis has been compressed to fit the entire sort into a fixed height.
Ye olde bubblesort. Some of the patterns are an optical illusion due to aliasing, but the green spikes are a feature of the algorithm.
Insertion sort - the version optimized for mostly sorted content. Although the data is random, you can see that in many cases it reduces the search distance.
Shellsort, clearly showing the phases.
Selection sort:
Heapsort: the solid lines at the top are the heap-building phase, while the rest shows the extraction. Note the very slight slope to the bottom-right line: as the heap gets smaller, the heap extraction gets faster, but only as O(log N).
Divide-and-conquer algorithms have a pretty fractal nature. This is quicksort - the perturbations in the fractal indicate the random selection of pivots (it just picks the middle, rather than median-of-3).
Mergesort: this diagram is twice as wide as the others because it uses temporary storage on the right.
If you're in computer science, you've probably seen an animation of sorting algorithms, maybe heard a rendition, or seen a visual representation. I have, somewhat by accident, discovered a different way to visualise a sorting algorithm: plot points for memory accesses, with address on the X axis and time (counted by accesses) on the Y axis, and different colours for reads and writes. It produces some rather pretty pictures. Note that these are not to scale relative to each other - the Y axis has been compressed to fit the entire sort into a fixed height.
Ye olde bubblesort. Some of the patterns are an optical illusion due to aliasing, but the green spikes are a feature of the algorithm.
Insertion sort - the version optimized for mostly sorted content. Although the data is random, you can see that in many cases it reduces the search distance.
Shellsort, clearly showing the phases.
Selection sort:
Heapsort: the solid lines at the top are the heap-building phase, while the rest shows the extraction. Note the very slight slope to the bottom-right line: as the heap gets smaller, the heap extraction gets faster, but only as O(log N).
Divide-and-conquer algorithms have a pretty fractal nature. This is quicksort - the perturbations in the fractal indicate the random selection of pivots (it just picks the middle, rather than median-of-3).
Mergesort: this diagram is twice as wide as the others because it uses temporary storage on the right.
Monday, May 03, 2010
Budapest (again)
Yes, it's blog time again! Once again, it was the 24-hour Challenge in Budapest.
Like last year, there were some very interesting and tough problems. This year they did a much better job of implementation, and there were far fewer issues with things crashing and so it was more enjoyable. Unfortunately we didn't do as well as last year, but we still managed to come 5th.
After the contest, we finally got our cruise on the Danube. This time we came better prepared with info on where to catch the tourist boats. It turns out we were just looking in the wrong area, and if you go to the right place there are scores of them.
Friday, April 16, 2010
IT Challenge over
It ran smoothly, so not much to report. Stellenbosch won, UKZN came second and UCT third. Now I get a week of holiday in Cape Town; too bad half my friends have moved to other places.
Saturday, April 10, 2010
IT Challenge 2010
I'm off to South Africa next week to help run the finals of the Standard Bank IT Challenge. This is a contest for teams of 4 university students. We've already run the heats to select one team from each of 9 universities; on Thursday the teams will meet at Standard Bank headquarters to do the final.
It's been some crazy hard work (including just about every free moment for the last week or two), but it should be a really great contest. We're hoping to have live standings during the contest (although we'll stop them an hour before the end) at http://sbitc2010.dyndns.org/ (yes, that link won't work right now, and probably won't after the contest either).
After that it's off to Cape Town for a week of hard-earned relaxation.
It's been some crazy hard work (including just about every free moment for the last week or two), but it should be a really great contest. We're hoping to have live standings during the contest (although we'll stop them an hour before the end) at http://sbitc2010.dyndns.org/ (yes, that link won't work right now, and probably won't after the contest either).
After that it's off to Cape Town for a week of hard-earned relaxation.
Subscribe to:
Posts (Atom)