String matching algorithm named BWT.

Tags: Algorithm

Algorithms for swapping blocks of data appear simple, but vary widely in their performance profiles. Choosing the right one can be crucial to good performance.


Three sequential O(n) in-place algorithms for swapping/exchanging blocks of unequal sizes were explored. The Gries-Mills algorithm is the performance leader with the Reversal algorithm coming in a close second, and the Juggling algorithm a distant third. The Reversal algorithm is the gem of the three, having high and consistent performance, the smallest and simplest implementation, and being the easiest to understand. The Gries-Mills and Reversal algorithms performed well due to their cache-friendly memory access patterns. The Juggling algorithm performed the fewest memory accesses, but came in over 5x slower due to its cache-unfriendly memory access pattern.

Tags: Algorithm

This document is a gentle introduction to computational number theory. The plan of the paper is to first give a quick overview of arithmetic in the modular integers. Throughout, we will emphasize computation and practical results rather than delving into the why. Simple programs, generally in JavaScript, are available for all of the algorithms mentioned. At the end of the paper we will introduce the Gaussian Integers and Galois Fields and compare them to the modular integers.

Tags: Algorithm

This is a dictionary of algorithms, algorithmic techniques, data structures, archetypal problems, and related definitions. Algorithms include common functions, such as Ackermann’s function. Problems include traveling salesman and Byzantine generals. Some entries have links to implementations and more information. Index pages list entries by area and by type. The two-level index has a total download 1/20 as big as this page.

The Traveling Salesman Problem is one of the most intensively studied problems in computational mathematics. These pages are devoted to the history, applications, and current research of this challenge of finding the shortest route visiting each member of a collection of locations and returning to your starting point.

Tags: Algorithm TSP