Category Archives: Algorithm

Check If It Is a Good Array

Problem Leetcode presents the following problem: Given an array nums of positive integers. Your task is to select some subset of nums, multiply each element by an integer and add all these numbers. The array is said to be good … Continue reading

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

Longest Palindromic Substring

Problem Write a function that, given an input string, locates and returns the longest sequence in the string that is a palindrome. Solution Every sub-string starting from the longest to the shortest needs to checked as shown below is_palindrome can … Continue reading

Posted in Algorithm, C++, Software Puzzle | 2 Comments

On computing the checksum

Problem Marius Bancila [Bancila 2018](Chapter 8, Problem 69) describes a checksum computation problem which can be paraphrased as follows: Let X = x1x2…xN where xi is a decimal digit. X is a valid number if (Σi=0N (N-i)*xi) mod 10 = … Continue reading

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

A quick note on all permutations

Marius Bancila [Bancila 2018] (Chapter 6, problem 52) poses the next permutation problem as follows: Write a function that, prints on the console all the possible permutations of a given string. and provides a recursive version of the solution as … Continue reading

Posted in Algorithm, C++ | Leave a comment

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