Algorithms

Travelling Salesman Problem - a converse solution

An algorithm that solves the travelling salesman problem to optimality. It has a performance of O(n!) but is actually very complicated and slower than the naive (brute force) algorithm. It makes use of a converse approach. That is while the naive algorithm finds the edges for every possibility, this algorithm finds the possibilities for every edge. It can possibly be made into a mathematical equation. Developed in February 2012.

Numbering sequences under xd restriction

A notion involving two equations to number over two different sub-sequences. It has a close relationship with the notion of numeral systems. Developed in March 2012.

Generating permutations

A very simple and efficient algorithm to generate a particular permutation given its corresponding index/rank. The core of the algorithm is the efficient generation of the Lehmer-code sequence using a new method. Developed in May 2012.

Strange generation of permutations

An algorithm to generate all permutations. It starts from a base permutation sequence, for example {0, 1, 2, ..., n-2, n-1} , and progressively generates the rest in recursive calls, doing constant work per permutation. It is simple to implement but rather tricky to understand. Developed in June 2012.

Matrix multiplication

A simple algorithm to perform matrix multiplication in linear time with total matrix size. But this is true only for the special case where inputs are all natural numbers or zero. Developed in August 2012.

Generating palindromic numbers

The pattern followed by palindromic numbers is analysed, then an algorithm is provided that implements this pattern to generate all palindromic numbers in increasing order starting from any given palindromic number, taking constant time per number generated. Finally a purely mathematical method is derived that computes the nth palindromic number, in time proportional to the number of digits of n. Developed in April 2013.

Numbering logarithmically

We generally number/index over a list of items sequentially. This is an algorithm to number/index over a list of items logarithmically (though this may not be a good description!) Developed in June 2013.

Expression parsing algorithm

A new, simple and very efficient iterative algorithm to parse a mathematical expression into a structure which a computer can easily evaluate. The simplest structure used is the Binary Expression Tree. The stack array is then used for optimal space efficiency. The algorithm performance is O(n). It can be extended to parsing of computer application source codes inside a compiler. Originally developed to parse the equation of a graph in the Graph Plotter 3D software. Developed in December 2013 - last major improvement in February 2015.

Sorted List to complete BST

A new, simple and very efficient iterative algorithm to convert a sorted list to a complete binary search tree (BST). It uses constant memory and does not compare list nodes. It is based on the same basic principle as that used by the expression parsing algorithm, along with an added rule to ensure tree completeness. And just like for the other algorithm, the basic principle causes this algorithm to have a performance of O(n), where n is the size of the list. Developed in February 2015.

Math FullFloor function

How can we generate any non-decreasing sequence of integers having a repetitive pattern? For example the sequence {0,0,1,2,2,2, 3,3,4,5,5,5, 6,6,7,8,8,8, ...}. The fullfloor function is a new, simple and efficient mathematical method to generate such a sequence. It is originally developed to be used to generate sequences of numbers of the form 'not a multiple of ', as part of working towards generating prime numbers. Developed in June 2015.

Generating prime numbers

A new, simple and efficient algorithm to generate prime numbers progressively. It turns out to be a non-sieve version of the sieve of Eratosthenes. It is based on generating all integers progressively starting from 2, taking O(n log n) time and O(sqrt(n)) space, where n is the largest integer generated so far. An improved version turns out to be a non-sieve version of the sieve of Euler. It has at its core the fundamental nature of prime numbers, which is used to prove the twin prime conjecture. Developed in December 2015 - last major improvement in May 2016.

Maximum bipartite matching

A new and very efficient algorithm to solve the maximum matching problem for an unweighted graph, in O(E log V) time where E and V are respectively the number of edges and vertexes of the graph. It consists of two main parts: a simple vertex get-and-match traversal, followed by an improved backtracking-search for any residual unmatched vertexes. Developed in July 2016 - last major improvement in July 2017.

Implemented algorithms at
https://github.com/rhyscitlema/algorithms