Tuesday, November 29, 2011

It turns out

So it turns out that Douglas Adams had this to say,
Incidentally, am I alone in finding the expression ‘it turns out’ to be incredibly useful? It allows you to make swift, succinct, and authoritative connections between otherwise randomly unconnected statements without the trouble of explaining what your source or authority actually is. It’s great. It’s hugely better than its predecessors ‘I read somewhere that...’ or the craven ‘they say that...’ because it suggests not only that whatever flimsy bit of urban mythology you are passing on is actually based on brand new, ground breaking research, but that it’s research in which you yourself were intimately involved. But again, with no actual authority anywhere in sight.
I'm convinced that every professor knows about this, and chuckle to themselves every time they use this phrase.

End of Entry

Sunday, November 13, 2011

Bubble Sort

Bubble sort is the crappiest sorting algorithm out there. For the longest time I found it perplexing why it was taught in school, when insertion sort and selection sort are more intuitive, (slightly) more efficient, and easier to implement. Researchers mentioned in the Wikipedia page find it mind-boggling as well.

Then bubble sort came up in the most unlikely circumstances, in Galois theory, when proving that the roots of the polynomial x^5+15x+5 cannot be written using +, -, *, / and radicals (taking the n-th root). The key idea is that one can sort a list when equipped with two operations: rotating the entire list, and flipping two elements (at fixed indices).

This means that one can also obtain any permutation of a list using the same two operations. The fact that this can be done isn't difficult to show, but it isn't immediately obvious either (at least to me).

So the takeaway is this: bubble sort tells us that it is possible to permute a list by means of rotation and flipping two elements.

End of Entry