Category Archives: Algorithm

Semi-Stable Partition

Inspiration Alexander Stepanov and Paul McJones in the their book “Elements of Programming” (Chaper 11.1) describe a stable partition algorithm that appears to be more complex than necessary. Here I present an improvement. Problem Definition A partition of sequence with … Continue reading

Posted in Algorithm, C++ | Leave a comment

String Matching Algorithms

Simple algorithms for searching permutations and combinations in strings Continue reading

Posted in Algorithm, C++ | Leave a comment

On Computing the Fibonacci Number in O(log(n))

Introduction Liu Feng posted a number of Lisp functions to compute a Fibonacci number with O(log(n)) time complexity where n is the n-th number to be computed. The last such function involved tail recursion. While the function is correct there … Continue reading

Posted in Algorithm, C++ | 4 Comments

Is Dijkstra Wrong? Another look at the Dutch National Flag problem

The Dutch National Flag problem was invented by W.H.J.Feijen[1]. The problem may be phrased as follows[2] Given `N’ objects coloured red, white or blue, sort them so that objects of the same colour are adjacent, with the colours in the … Continue reading

Posted in Algorithm | Leave a comment

Breadth First Search

Many programming problems can be modeled as search problems. Given an initial state find the set of intermediate states that have to be traversed before reaching a goal state. We could formulate the Water Buckets problem, the BrainVita problem or … Continue reading

Posted in Algorithm, C++, Software Puzzle | Tagged | Leave a comment

Why Functional Programming works for the Eight Queens Problem.

At a recent Boost Conference, Bartosz Milewski [1] presented a solution to the Eight Queens problem from a functional programming perspective. The main argument is that in Functional Programming we do not modify state. We create new states by extending … Continue reading

Posted in Algorithm, Software Engineering, Software Puzzle | Tagged | Leave a comment

Master Mind Solver

Knuth [1] describes Master Mind as follows In this game one player (the “codemaker”) conceals a four-symbol code, and the other player (the “codebreaker”) tries to identify all four symbols by trying appropriate test patterns. There are six symbols, represented … Continue reading

Posted in Algorithm, Software Puzzle | Tagged , | Leave a comment