After teaching a basic course on data structures and algorithms many times, I grew weary of saying the same things each semester, yet never quite saying them right. So I spent (too) many hours in the studio and editing on my laptop, to produce some short (mostly 15-25 minute) video lectures, available on my Youtube channel. They are posted under a CC-BY licence, so feel free to use them but give me appropriate credit. Feedback from students using them the last time I taught the material (where I tried with mixed success to replace traditional lectures with more active learning) was clearly positive.
Category Archives: Algorithms and data structures
Binary search rules!
This afternoon I visited a branch library with my sons and checked out a large number of books for them, using the self-checkout. On leaving, we set off the alarm, because at least one book had not been correctly scanned. A librarian seized the pile of books, and proceeded to determine the offending book by binary search using the alarm (his algorithm may not have worked completely if more than one book was unscanned, so he performed a final check on the original pile, after scanning the one he found). His colleague was amazed and said that everyone else uses (in effect) sequential search of the receipt, checking it with the books in hand. I was amazed that someone this clever was working as a librarian, and that I had finally found a real-life application of an algorithm – I try to give many such examples when teaching algorithms courses, but they always have a slightly contrived feel to them.
Big O(micron) and Big Omega and Big Theta
Teaching an algorithms course recently, I realized that the correct use of these asymptotic notations is apparently rather difficult for students to grasp. In fact, I have some colleagues whose understanding of these concepts is not maximally clear.
In 1976 Donald Knuth published an article explaining these notations in detail and recommending their use. After 35 years and plenty of evidence that it works well, we still have resistance. Perhaps one reason is that the idea of “asymptotically equivalent to”, or “of the exact order of” is formalized by the symbol Theta, while O is a simpler and more familiar symbol that evokes the word “order”. The most common misuse I have seen is exactly this use of O when Theta is meant. The principle that the most important and useful concepts should have the simplest notation implies that O would be better for computer science use. However, that would make it inconsistent with mathematical use where big-O is definitely used for upper bounds only.
The main mistake seen (also mentioned by Knuth) apart from the perhaps excusable one above is not excusable: it is the use of O to discuss lower bounds as in the example: “Algorithm A is better than Algorithm B because A is known to run in time O(n log n) and B in time O(n^2)”. If O is replaced by Theta, then this might make sense, but the literature is full of algorithms whose O-bounds are not asymptotically tight – how do we know B doesn’t run in time O(n) also? Again, if you think that O means Theta, this mistake is an easy one to make.
Algorithm song contest!
The NZIMA programme in Algorithmics is sponsoring a competition to produce a song on the topic of algorithms. There is a well-known parody of Billy Joel’s “For the Longest Time”, but this is 20 years old, and we are sure that New Zealand can produce something of comparable, if not higher, standard.
Rules: entry is open to anyone resident in New Zealand. The song must be to the tune of Billy Joel’s “We Didn’t Start the Fire”. It may be submitted either as lyrics or audio file (or both). The best entry by a secondary or tertiary student will receive $200 of textbooks of the winner’s choice. Desirable features of an entry include correct scansion and real content about the subject of algorithms. The deadline for entries is 28 February 2009.
UPDATE: deadline extended to 31 May 2009.