List of algorithms

Table of Contents

Algorithms in C

Algorithms in Prolog

Algorithms in Python

A* (A-Star) in Python

In computer science, A* (pronounced "A star") is a best-first, graph search algorithm that finds the least-cost path from a given initial node to one goal node (out of one or more possible goals). A* is complete and computationally optimal.

BK-Tree in Python

BK-Trees, or Burkhard-Keller Trees are a tree-based data structure engineered for quickly finding near-matches to a string, for example, as used by a spelling checker, or when doing a 'fuzzy' search for a term.

Elementary Graph Search in Python

Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking. In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes.

Greatest common divisor in Python

In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder.

Greatest common divisor in C

In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder.

Greatest common divisor in Prolog

In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder.

Heap in Python

A heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) <= key(B). This implies that an element with the smallest key is always in the root node, and so such a heap is sometimes called a min heap. This is why heaps are used to implement priority queues. The efficiency of heap operations is crucial in several graph algorithms.

Knapsack in C

The knapsack problem is a problem in combinatorial optimization. It derives its name from the following maximization problem of the best choice of essentials that can fit into one bag to be carried on a trip. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible.

Newton's method in Python

In numerical analysis, Newton's method (also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson) is perhaps the best known method for finding successively better approximations to the zeros (or roots) of a real-valued function.

Pairing Heap, Elmasry in C

An implementation of Elmasry's variation of the Pairing Heap published in SODA09.

Pairing Heap, Multi-pass in C

The multi-pass variation of Pairing heaps is a type of heap data structure with relatively simple implementation and excellent practical amortized performance. However, it has proven very difficult to determine the precise asymptotic running time of pairing heaps.

Pairing Heap, Two-pass in C

Pairing heaps are a type of heap data structure with relatively simple implementation and excellent practical amortized performance. However, it has proven very difficult to determine the precise asymptotic running time of pairing heaps.

Quicksort in Prolog

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes O(nlogn) (big O notation) comparisons to sort n items. However, in the worst case, it makes O(n2) comparisons. Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the probability of requiring quadratic time.

Secant method in Python

In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f.

Sieve of Eratosthenes in C

In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. It was created by Eratosthenes, an ancient Greek mathematician.

Simplex Method in Python

In mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerical solution of the linear programming problem. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the century.

Trie in C

In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings.

Union-Find in C

Given a set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping sets. A disjoint-set data structure is a data structure that keeps track of such a partitioning. A union-find algorithm is an algorithm that performs two useful operations on such a data structure: * Find: Determine which set a particular element is in. Also useful for determining if two elements are in the same set. * Union: Merge two sets into a single set