Showing posts with label computer science. Show all posts
Showing posts with label computer science. Show all posts

May 7, 2009

Death From Above

(Or this DFA - whichever you prefer.)

I'm writing this in the middle of an especially sluggish induction proof in CS 360. I've decided to make a few minor but hopefully positive changes in the way I approach class:
  • I'll try to make it to as many of them as possible - even those pesky 8:30 am ones that have marred my attendance track record in previous terms. (Not that anyone keeps track, but still...)
  • I'm keeping semi-rigorous notes for any lectures that don't have nice preformatted course slides available online.
  • I'm keeping those notes...in LaTeX.
The idea with the latter step is that having legible notes will encourage me to revisit them, a process that lies in stark contrast with my longstanding practice of keeping sporadic write-only notes. We'll see how that one goes. In either case, I'll endeavour to make the notes publicly available, thus driving a further spike in various efforts initiated by the University of Waterloo administration to lock up our course materials.


Final note: if you are concerned about the privatization of knowledge, I strongly urge you to do the same. Keep notes, make PDFs, and distribute like crazy. Help us bridge our ingenuity gap.

April 20, 2009

Speaking of Essential Research...

...here's a gem from the pen of Knuth.

February 1, 2009

So You Think You Can Sort

Selection sort. Insertion sort. Quicksort. Mergesort. All are standard fare in your average basic-level CS class; the first two are inefficient but conceptually simple, whereas the last two are decent general sorting algorithms. This is all good and well, but no one uses them for performance-critical applications:
  • Often, a sort is not required; what you really want in most large-scale cases are the top k results for some relatively small k.
  • Real-world data has patterns that general algorithms like your standard library quicksort fail to exploit.
  • Comparisons and swaps aren't always cheap.
For you C++ programmers, the first point means little more than the difference between sort and partial_sort. The second point, however, is slightly more subtle.

As a simple example, suppose you have a billion integers to sort, but you know that each one is between 1 and 100. With that restriction alone, you can easily sort them in O(n) time. Other examples:
  • The data are k-sorted (i.e. A[i] >= A[i-k].)
  • The data aren't quite sorted, but they are unique; furthermore, abs(A[i] - A[i-1]) < k.
The third point might seem like a dubious proposition, especially that part about swaps. How can swaps be expensive? If I want to swap complex structures, I use pointers. Simple, right?

A while ago, I wrote a DHTML table sorter (for fun, naturally!) For reference, here's a standard quicksort implementation. Ignoring the horrendous colour scheme for a moment, why is the first one so much faster? Simple - it avoids swapping DOM elements. (There's a reason it's called permutation quicksort!)

Fine. So we can guarantee O(n) swaps in exchange for linear memory overhead. How do you limit comparisons? Remember that second point - notice patterns.