Sums of powers

When you’re studying algorithms, there is a number of series and expression that keep showing up. A while ago, I discussed the special form . But that’s not the only one. Another form that keeps showing up is

.

We can look the particular form this sum takes for specific in some compendium (like CRC’s tables and formulae, that have seen 30-something editions over the last half century), or… you can find the formula yourself. It’s a bit tedious, but not that complicated.

Science!

Sorry, no entry for this week: I’ve been rather busy lately (because of science).

Real dice.

Suppose you want to draw randomly a number between 0 and 1, with multiple throws of a six sided dice, what would you write down on its face?

ln n!

In the course of analyzing an algorithm, I used the simplifying hypothesis that the cost function is

.

That expression is cumbersome but we can get a really good simplified function to use as a proxy. Let’s see how.

Rotating Arrays (part II)

Last week we had a look at Kernighan’s algorithm to rotate an array position and concluded that it might not be optimal, as each element was moved twice. This week, we’ll have a look at another algorithm that moves some items more than once, but overall will do less than two exchanges per items.

Rotating Arrays (Part I)

To “rotate” an array position to the left (or to the right, doesn’t really matter) we could repeat times a shift of one, using only one temporary variable. This method doesn’t use much auxiliary memory but is inefficient: it will do copies if we apply it to an array of size . Surely we can do better.

Selection, Revisited.

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 th item is in slot . But what if the array is not sorted?

LaTeXify C/C++ code snippets

So I’m still writing lecture notes. This time, I need to include kind of larger pieces of C or C++ code, and 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 unhappy. This looks like a job for
sed.

Interpolation Search

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 for a list of 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?

Search all your Bibtex files

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.