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.

dutch-flag

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.

wood

Read the rest of this entry »


Eratosuite

December 15, 2015

The other day in class, we were looking at recurrence relations and how to solve them with the characteristic equation. Among the examples I gave was a recurrence that seemed to give a good number of primes numbers. Are there many of those? How do we find them?

Eratosthene.01

Well, we need two things: a method of testing if a given number is prime, and a method of generating recurrences—parameters and initial conditions. Well, make that three: we also need to generate the suite generated by the recurrence relation. Let’s go!

Read the rest of this entry »


Single-Pointer Doubly-Linked Lists

December 8, 2015

Old computer science books aren’t perceived as being of much use, since everything is so much better now. Of course, that’s not entirely true, especially when we are interested in the techniques used in the days where 32KB core memory was “a lot”. Leafing through one such book, Standish’s 1980 Data Structure Techniques, I found a method of maintaining doubly-linked lists using only one pointer. Let’s see how it works!

chain

Read the rest of this entry »


Pythagorean Primes

December 1, 2015

Last Week, we had a look at Pythagorean triples. Remember: a Pythagorean triple is three natural numbers (positive integers) such that a^2+b^2=c^2. Most of the times, even with a and b natural numbers, c is irrational. Sometimes c is prime; sometimes c^2 is. Is either frequent?

Read the rest of this entry »