the Dutch Flag Problem

29/12/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)?

OB Sqrt

22/12/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.

Eratosuite

15/12/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?

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!

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?