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 ...

  • Puzzle: A Harshad Number, in a given number base, is an integer that is divisible by the sum of its digit when written in that base.

    Write a function that returns whether an integer is a Harshad Number or not (in base 10).

    Solution: Of the numbers ...

  • 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 (Tic-tac-toe, ...

  • 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. In statistics, mean, median, and mode are all known as measures of ...

  • 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, binary search, also known as half-interval search or logarithmic search, is a search algorithm that finds the position of a target value, whether alone or part of a record as a key, within a sorted array. It works by comparing the ...

  • In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type 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 permutation sort, stupid sort, slowsort, shotgun sort or monkey sort) is a particularly ineffective sorting algorithm based on the generate and test paradigm. The algorithm successively generates permutations of its ...

  • 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 ...

  • In computer science, bogosort (also permutation sort, stupid sort, slowsort, shotgun sort or monkey sort) is a particularly ineffective sorting algorithm based on the generate and test paradigm. The algorithm successively generates permutations of its ...

  • 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, before ...

  • 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 characters ...

  • 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 after ...

  • Cocktail shaker sort, also known as bidirectional bubble sort, cocktail 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 turtles, or ...

  • 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, with ...

  • 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. More ...

  • 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, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing ...

  • 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 sum 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 of an ...

  • The zebra puzzle is a well-known logic puzzle. Many versions of the puzzle exist, including a version published in Life International magazine on December 17, 1962. The March 25, 1963, issue of Life contained the solution and the names of several ...

  • 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 spacesave for the zero vector, which is assigned a length of zero. A seminorm, on ...

  • 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 operation is ...

  • Fast inverse square root (sometimes referred to as Fast InvSqrt() or by the hexadecimal constant 0x5f3759df) is a method of calculating x, the reciprocal (or multiplicative inverse) of a square root for a 32-bit floating point number in IEEE 754 ...

  • 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 on the ...

  • 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 ...

  • The "Fizz-Buzz test" is an interview question designed to help filter out the 99.5% of programming job candidates who can't seem to program their way out of a wet paper bag. The text of the programming assignment is as follows: "Write a program that ...

  • 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 ...

  • In mathematics, economics, and computer science, the stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. ...

  • 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 later ...

  • The golden section search is a technique for finding the extremum (minimum or maximum) of a strictly unimodal function by successively narrowing the range of values inside which the extremum is known to exist. The technique derives its name from the ...

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

  • 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 either equals 1 (where it will stay), or it loops ...

  • In computer science, 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 unsorted ...

  • In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding and/or using such a code proceeds by means of Huffman coding, an ...

  • 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 search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing ...

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

  • k-means clustering is a method of vector quantization, originally from signal processing, that is popular for cluster analysis in data mining. k-means clustering aims to partition n observations into k clusters in which each observation belongs to the ...

  • A backpack also called bookbag, kitbag, knapsack, rucksack, pack, or sackpack 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 variations. Lightweight types of ...

  • 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 1978. ...

  • 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. ...

  • In computer science, linear search or sequential search is a method for finding a particular value in a list that checks each element in sequence until the desired element is found or the list is exhausted. The list need not be ordered.Linear search is ...

  • The Mandelbrot set is the set of complex numbers c for which the function does not diverge when iterated from, i.e., for which the sequence, , etc., remains bounded in absolute value.The set is closely related to the idea of Julia sets, which produce ...

  • Taxicab geometry, considered by Hermann Minkowski in 19th-century Germany, is a form of geometry in which the usual distance function of metric or Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the ...

  • A Markov chain (discrete-time Markov chain or DTMC), named after Andrey Markov, is a random process that undergoes transitions from one state to another on a state space. It must possess a property that is usually characterized as "memorylessness": the ...

  • In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values 2, 1, 3, 4, 1, 2, 1, 5, 4; the contiguous ...

  • In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization has also been used in ...

  • O(n log n) typical,In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the ...

  • A minimax approximation algorithm (or L approximation or uniform approximation) is a method to find an approximation of a mathematical function that minimizes maximum error.For example, given a function defined on the interval and a degree bound, a ...

  • The Minkowski distance is a metric in a normed vector space which can be considered as a generalization of both the Euclidean distance and the Manhattan distance.The Minkowski distance of order p between two pointsis defined as:For, the Minkowski ...

  • The Monty Hall problem is a brain teaser, in the form of a probability puzzle (Gruber, Krauss and others), loosely based on the American television game show Let's Make a Deal and named after its original host, Monty Hall. The problem was originally ...

  • The move-to-front (MTF) transform is an encoding of data (typically a stream of bytes) designed to improve the performance of entropy encoding techniques of compression. When efficiently implemented, it is fast enough that its benefits usually justify ...

  • The eight queens puzzle is the problem of placing eight chess queens on an 88 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an ...

  • Negamax search is a variant form of minimax search that relies on the zero-sum property of a two-player game.This algorithm relies on the fact that max(a, b) = min(a, b) to simplify the implementation of the minimax algorithm. More precisely, the value ...

  • A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of division. Some are applied by hand, while others are employed by digital circuit designs and software.Division algorithms ...

  • Approximations for the mathematical constant pi () in the history of mathematics reached an accuracy within 0.04% of the true value before the beginning of the Common Era (Archimedes). In Chinese mathematics, this was improved to approximations correct ...

  • Pollard's rho algorithm is a special-purpose integer factorization algorithm. It was invented by John Pollard in 1975. It is particularly effective for a composite number having a small prime factor.The algorithm is based on Floyd's cycle-finding ...

  • Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959, with his work published in 1961, it is still a ...

  • In computer science, the RabinKarp algorithm or KarpRabin algorithm is a string searching algorithm created by Richard M. Karp and Michael O. Rabin(1987) that uses hashing to find any one of a set of pattern strings in a text. For text of length n and ...

  • In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. A positional notation is required, but ...

  • The numeric system represented by Roman numerals originated in ancient Rome and remained the usual way of writing numbers throughout Europe well into the late Middle Ages. Numbers in this system are represented by combinations of letters from the Latin ...

  • Run-length encoding (RLE) is a very simple form of lossless data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as ...

  • In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is ...

  • In mathematics, a self-descriptive number is an integer m that in a given base b is b digits long in which each digit d at position n (the most significant digit being at position 0 and the least significant at position b - 1) counts how many instances ...

  • Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of ...

  • In mathematics, the sieve of Eratosthenes (AncientGreek: , kskinon Eratosthnous), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as ...

  • Stathmodera flavescens is a species of beetle in the family Cerambycidae. It was described by Breuning in 1940. https://en.wikipedia.org/wiki/Stathmodera_flaves...

  • Stooge sort is a recursive sorting algorithm with a time complexity of O(nlog 3 / log 1.5 ) = O(n2.7095...). The running time of the algorithm is thus slower compared to efficient sorting algorithms, such as Merge sort, and is even slower than Bubble ...

  • Alvy (also known as Stringtown from the oil boom days c. 1890s - 1910 because the estimated population of 5000 residents and temporary workers were strung over the hills and hollows hence the nickname Stringtown) is an unincorporated community in Tyler ...

  • In numerical linear algebra, the method of successive over-relaxation (SOR) is a variant of the GaussSeidel method for solving a linear system of equations, resulting in faster convergence. A similar method can be used for any slowly converging ...

  • A standard Sudoku puzzle contains 81 cells, in a 9 by 9 grid, and has 9 zones, each zone being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns. Each cell may contain a number from one to nine; each number ...

  • In mathematics, the symmetric difference of two sets is the set of elements which are in either of the sets and not in their intersection. The symmetric difference of the sets A and B is commonly denoted byororFor example, the symmetric difference of ...

  • In computer science, Thompson's construction is an algorithm for transforming a regular expression into an equivalent nondeterministic finite automaton (NFA). This NFA can be used to match strings against the regular expression.Regular expression and ...

  • The token bucket is an algorithm used in packet switched computer networks and telecommunications networks. It can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness (a measure of the ...

  • The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower, and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with ...

  • The Vigenre cipher is a method of encrypting alphabetic text by using a series of different Caesar ciphers based on the letters of a keyword. It is a simple form of polyalphabetic substitution.The Vigenre (French pronunciation:[vin]) cipher has been ...

  • 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 ...

  • Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.The ...

  • A formula calculator is a software calculator that can perform a calculation in two steps:This is unlike button-operated calculators, such as the Windows calculator or the Mac OS X calculator, which require the user to perform one step for each ...

  • A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward. Allowances may be made for adjustments to capital letters, punctuation, and word dividers. Examples in English include "A man, a plan, a ...

  • Rail Fence Cipher

    In the rail fence cipher, the plaintext is written downwards and diagonally on successive "rails" of an imaginary fence, then moving up when we reach the bottom rail. When we reach the top rail, the message is written downwards again ...