Selection, Revisited.

February 2, 2016

When we think of searching, we generally think of searching a value in a sorted collection of some sort. For a simple array, this implies the array is sorted and that we use binary search or a variant. But what if we want to search by rank? In a sorted array, that’s not very hard: the kth item is in slot k. But what if the array is not sorted?

Read the rest of this entry »

LaTeXify C/C++ code snippets

January 26, 2016

So I’m still writing lecture notes. This time, I need to include kind of larger pieces of C or C++ code, and \LaTeX environments do not really help me a lot. Some are better than others, but you still have to escape and fancify text yourself. This is laborious and error-prone, and is an obvious target for automation. A script of some sort. The task isn’t overly complicated: highlight keywords, and escape symbols like { } _ and & that make \LaTeX unhappy. This looks like a job for

Read the rest of this entry »

Interpolation Search

January 19, 2016

We all know about binary search. It’s been with us such a long time. Knuth thinks it’s first appearance in print is in the Moore School Lectures, in 1946. The technique search for an item in a list by halving, iteratively, the searched portion. Its complexity is O(\log n) for a list of n values, making it a very efficient algorithm for searching.

One may even be tempted to think that it’s in fact optimal, that we can’t do significantly better. Is that so?

Read the rest of this entry »

Search all your Bibtex files

January 12, 2016

When I write papers or other things, I tend to create separate bib files, so that I don’t end with a giant unsearchable and unmaintainable blob. Moreover, topics tend to be transient, and the bibliography may or mayn’t be interesting in a few year’s time, so, if unused, it can safely sleep in a directory with the paper it’s attached to.


But once in a while, I need one of those old references, and since they’re scatted just about everywhere… it may take a while to find them back. Unless you have a script. Scripts are nice.

Read the rest of this entry »

A Bit About Bit-Fields

January 5, 2016

Let’s make a detour through low-level programming this week. Let’s talk about bit-fields and some of their quirks.


Read the rest of this entry »

the Dutch Flag Problem

December 29, 2015

While preparing my lecture notes on sorting, I rediscovered the Dutch flag problem proposed by Edsger W. Dijkstra quite a while ago. This problem is relevant in the context of sorting, especially for variants of Quicksort, where you want to create not two but three partitions.


Like many problems, the Dutch flag problem has a very simple statement. Say you have an array with three types of value, how can you arrange them so that all the items of the first type is at the beginning of the array, the items of the third at the end (and, of course, leaving the second type between the two)?

Read the rest of this entry »

OB Sqrt

December 22, 2015

I have discussed the problem of efficient square root calculation quite a few times. And yet, while reading Rudman’s The Babylonian Theorem, I found yet another square root algorithm. The Old Babylonian square root algorithm. Let’s have a look on how it works.


Read the rest of this entry »


Get every new post delivered to your Inbox.

Join 98 other followers