Algorithms

Click on an algorithm to check out its implementations!


  • Puzzle:

    There are 100 doors in a long hallway. They are all closed. The first time you walk by each door, you open it. The second time around, you close every second door (since they are all opened). On the third pass you stop at every third door and ...

  • 99 Bottles of Beer

    Puzzle:

    You must print the lyric of the song as follows:

    ``` 99 bottles of beer on the wall, 99 bottles of beer. Take one down and pass it around, 98 bottles of beer on the wall. 98 bottles of beer on the wall, 98 ...

  • In computer science, A* (pronounced as A star ( listen ) ) is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between multiple points, called nodes. Noted for its ...

  • In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total and ...

  • Alphabeta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games ( ...

  • In colloquial language, an average is the sum of a list of numbers divided by the number of numbers in the list. In mathematics and statistics, this would be called the arithmetic mean. However, the word average may also refer to the median, mode, or ...

  • Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule. Judea Pearl described best-first search as estimating the promise of node n by a heuristic evaluation function ...

  • In computer science, a binary search or half-interval search algorithm finds the position of a target value within a sorted array. The binary search algorithm can be classified as a dichotomic divide and conquer search algorithm and executes in ...

  • In computer science, binary search trees ( BST ), sometimes called ordered or sorted binary trees, are particular types of containers : data structures that store items (such as numbers, names, etc.) in memory. They allow fast lookup, addition and ...

  • A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom ...

  • In computer science, bogosort (also stupid sort, slowsort, random sort, shotgun sort or monkey sort ) is a particularly ineffective sorting algorithm based on the generate and test paradigm. It is not useful for sorting, but may be used for ...

  • In computer science, the BoyerMooreHorspool algorithm or Horspool's algorithm is an algorithm for finding substrings in strings. It was published by Nigel Horspool in 1980. It is a simplification of the BoyerMoore string search algorithm which is ...

  • Breadth-first search ( BFS ) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a `search key' ) and explores the neighbor nodes first, ...

  • Bresenham's line algorithm is an algorithm that determines the points of an n -dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw lines on a computer ...

  • Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is ...

  • The BurrowsWheeler transform ( BWT, also called block-sorting compression ) rearranges a character string into runs of similar characters. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated ...

  • In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the ...

  • In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively -defined objects. They are named after the Belgian mathematician Eugne Charles Catalan ...

  • In mathematics, Chebyshev distance (or Tchebychev distance ), maximum metric, or L metric is a metric defined on a vector space where the distance between two vectors is the greatest of their differences along any coordinate dimension. It is named ...

  • Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort (which can also refer to a variant of selection sort ), ripple sort, shuffle sort, or shuttle sort, is a variation of bubble sort that is both a stable sorting ...

  • Comb sort is a relatively simple sorting algorithm originally designed by Wodzimierz Dobosiewicz in 1980. Later it was rediscovered by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble sort . The basic idea is to eliminate ...

  • Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science . In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, ...

  • The Counterfeit Coin Problem:

    There is a pile of twelve coins, all of equal size. Eleven are of equal weight. One is of a different weight. In three weighings find the unequal coin and determine if it is heavier or ...

  • In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers ; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key ...

  • Cryptography (or cryptology ; from Greek krypts, hidden, secret; and graphein, writing, or - -logia, study, respectively) is the practice and study of techniques for secure communication in the presence of third parties (called adversaries ). ...

  • Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijkstra in an unpublished paper on sequential process ...

  • Depth-first search ( DFS ) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before ...

  • In computer science depth-limited search is an algorithm to explore the vertices of a graph. It is a modification of depth-first search and is used for example in the iterative deepening depth-first search algorithm. Like the normal depth-first ...

  • The derivative of a function of a real variable measures the sensitivity to change of a quantity (a function value or dependent variable ) which is determined by another quantity (the independent variable ). Derivatives are a fundamental tool of ...

  • An Egyptian fraction is a finite series of distinct unit fractions, such as. That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each other. The value ...

  • The zebra puzzle is a well-known logic puzzle. It is often called Einstein's Puzzle or Einstein's Riddle because it is said to have been invented by Albert Einstein as a boy. It is often claimed that only 2% of the population can solve it. The ...

  • In linear algebra, functional analysis and related areas of mathematics, a norm is a function that assigns a strictly positive length or size to each vector in a vector space save possibly for the zero vector, which is assigned a length of zero. A ...

  • In mathematics, the Euclidean algorithm [a], or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. It is named after the ...

  • In mathematics, the Euclidean distance or Euclidean metric is the ordinary (i.e straight line) distance between two points in Euclidean space. With this distance, Euclidean space becomes a metric space. The associated norm is called the Euclidean ...

  • In mathematics, the factorial of a non-negative integer n, denoted by n !, is the product of all positive integers less than or equal to n. For example, The value of 0! is 1, according to the convention for an empty product. The factorial ...

  • In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence : or (often, in modern usage): By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending ...

  • The Fisher–Yates shuffle (named after Ronald Fisher and Frank Yates), also known as the Knuth shuffle (after Donald Knuth), is an algorithm for generating a random permutation of a finite set—in plain terms, for randomly shuffling the set. The modern ...

  • In computer science, the FloydWarshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed ...

  • Gnome sort (or Stupid sort ) is a sorting algorithm originally proposed by Dr. Hamid Sarbazi-Azad (Professor of Computer Engineering at Sharif University of Technology ) in 2000 and called stupid sort (not to be confused with bogosort ), and then ...

  • In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming(7,4)-code invented by Richard Hamming in 1950. Hamming codes can detect up to two-bit errors or correct one-bit errors without detection of ...

  • In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In another way, it measures the minimum number of substitutions required to change one string ...

  • The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of ...

  • A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly ...

  • In computer programming, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort : like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...

  • Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort ...

  • In computer science, Iterative deepening depth-first search (IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches, the depth of the shallowest goal ...

  • In computer science and mathematics, the Josephus Problem (or Josephus permutation ) is a theoretical problem related to a certain counting-out game . There are people standing in a circle waiting to be executed. The counting out begins at some ...

  • A backpack also called rucksack, knapsack, packsack, pack, or bergen is, in its simplest form, a cloth sack carried on one's back and secured with two straps that go over the shoulders, but there can be exceptions. Lightweight types of backpacks ...

  • In computer science, the KnuthMorrisPratt string searching algorithm (or KMP algorithm ) searches for occurrences of a word W within a main text string S by employing the observation that when a mismatch occurs, the word itself embodies sufficient ...

  • LempelZivWelch ( LZW ) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempel and Ziv in ...

  • In information theory and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. ...