# Algorithms

**Home * Programming * Algorithms**

**Algorithms**,

in mathematics and computer science, methods for solving a problem expressed as a finite sequence of instructions. The term “algorithm” is derived from the name of Muḥammad ibn Mūsā al-Khwārizmī (born approximately 780 in Khwarezm, died between 835 and 850), the Persian mathematician, astronomer, geographer, and scholar in the House of Wisdom in Baghdad, from the Khorasan province of present-day Uzbekistan ^{[2]} .

## Contents

# General Concepts

# Sorting and Searching

- ABDADA
- All shortest Paths
- Alpha-Beta
- B*
- Best-First
- Brute-Force
- Depth-First
- Flood Fill Algorithm
- Iterative Search
- Jamboree
- Monte-Carlo Tree Search
- Move Ordering
- MTD(f)
- NegaC*
- NegaScout
- Parallel Alpha-Beta in Cilk
- Parallel Search
- Principal Variation Search
- Proof-Number Search
- Retrograde Analysis
- Search
- SEE - The Swap Algorithm
- SEX Algorithm
- SOMA Algorithm
- SSS* and Dual*
- UCT
- Young Brothers Wait Concept

# Enumeration and Backtracking

# Mathematical Optimization

# Combinatorial

- Bit-Twiddling
- BitScan
- Flipping Mirroring and Rotating
- Kogge-Stone Algorithm
- Parallel Prefix Algorithms
- Population Count

# See also

- BCH Hashing
- Data
- Fill Algorithms
- Hash Table
- Learning
- Mathematician
- SIMD and SWAR Techniques
- Space-Time Tradeoff
- Zobrist Hashing

# Publications

## 1960 ...

- Donald E. Knuth (
**1968 ...**).*The Art of Computer Programming (TAOCP)*^{[3]}

- Volume 1 - Fundamental Algorithms (
**1968**) - Volume 2 - Seminumerical Algorithms (
**1969**) - Volume 3 - Sorting and Searching (
**1973**) - Volume 4 - Combinatorial Algorithms in preparation (five fascicles have been published as of April 2009)
- Volume 4A - Enumeration and Backtracking
- Volume 4B - Graph and Network Algorithms
- Volume 4C and possibly 4D - Optimization and Recursion
- Volume 5 - Syntactic Algorithms, planned (as of August 2006, estimated in 2015).

## 1970 ...

- Niklaus Wirth (
**1976**).*Algorithms + Data Structures = Programs*. - Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (
**1979**).*Algorithms of adaptive search*. Machine Intelligence 9 (eds. Jean Hayes Michie, Donald Michie and L.I. Mikulich), pp. 373-384. Ellis Horwood, Chichester

## 1980 ...

- Andrei P. Ershov, Donald Knuth (Eds.) (
**1981**).*Algorithms in Modern Mathematics and Computer Science*. Proceedings, Urgench, Uzbek SSR, September 16-22, 1979. Lecture Notes in Computer Science, Vol. 122, Springer » Ershov Archive - Michel Gondran, Michel Minoux, Steven Vajda (
**1984**).*Graphs and Algorithms*. John Wiley & Sons, google, amazon - Paul W. Purdom, Cynthia A. Brown (
**1985**).*The Analysis of Algorithms*. Holt, Rinehart and Winston - Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (
**1988**).*Algorithms for Games*. Springer

## 1990 ...

- John Tromp (
**1993**).*Aspects of Algorithms and Complexity*. Ph.D. thesis, University of Amsterdam, advisor Paul Vitányi - Warren D. Smith, Kevin J. Lang (
**1994**).*Values of the merging function and algorithm design as a game*. NEC Research Institute, ps - Leen Ammeraal (
**1996**).*Algorithms and Data Structures in C++*. Chichester: John Wiley - Steven Skiena (
**1998**).*The Algorithm Design Manual*. 2nd Edition 2008 - Harald Prokop (
**1999**).*Cache-Oblivious Algorithms*. Masters thesis, Department of Electrical Engineering and Computer Science, MIT, pdf

## 2000 ...

- Donald Knuth (
**2000**).*Selected Papers on Analysis of Algorithms*. CSLI lecture notes series 102 - Paul W. Purdom, Cynthia A. Brown (
**2004**).*The Analysis of Algorithms*. Oxford University Press, amazon - R. C. T. Lee, et al. (
**2005**).*Introduction to the Design and Analysis of Algorithms, a Strategic Approach*. McGraw-Hill, amazon - Jill Cirasella (
**2006**).*Classical and Quantum Algorithms for Finding Cycles*. M.Sc. thesis, University of Amsterdam, pdf, slides as pdf - Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani (
**2006**).*Algorithms*. McGraw-Hill, amazon - Jon Kleinberg, Éva Tardos (
**2006**).*Algorithm Design*. Pearson, Addison-Wesley - Jacques Bahi, Sylvain Contassot-Vivier, Raphaël Couturier (
**2007**).*Parallel Iterative Algorithms: From Sequential to Grid Computing*. Chapman & Hall/CRC Numerical Analysis and Scientific Computing Series - David J. Stracuzzi (
**2007**).*Randomized Feature Selection*. in Huan Liu, Hiroshi Motoda (eds.) Computational Methods of Feature Selection. CRC Press, pdf - Steven Skiena (
**2008**).*The Algorithm Design Manual*. Springer, 2nd Edition - Kurt Mehlhorn, Peter Sanders (
**2008**).*Data Structures and Algorithms: The Basic Toolbox*. Springer - Michel Gondran, Michel Minoux (
**2008, 2010**).*Graphs, dioids and semirings - New Models and Algorithms*. Springer, from google, amazon.com, 2nd edition from alibris.com^{[4]} - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (
**2009**).*Introduction to Algorithms, 3rd Edition*.

## 2010 ...

- Donald Knuth (
**2010**).*Selected Papers on Design of Algorithms*. CSLI lecture notes series 191, Cambridge University Press - Berthold Vöcking et al. (eds.) (
**2011**).*Algorithms Unplugged*. Springer - Matteo Frigo, Charles Leiserson, Harald Prokop, Sridhar Ramachandran (
**2012**).*Cache-Oblivious Algorithms*. ACM Transactions on Algorithms, Vol. 8, No. 1, pdf - Christos H. Papadimitriou, Leonard Adleman, Richard Karp, Donald Knuth, Robert E. Tarjan, Leslie Valiant (
**2012**).*An Algorithmic View of the Universe*. ACM-Turing 2012 » Alan Turing

- Katja Grace (
**2013**).*Algorithmic Progress in Six Domains*. Technical report 2013-3, Machine Intelligence Research Institute, Berkeley, CA, pdf, 5 Game Playing, 5.1 Chess, 5.2 Go, 9 Machine Learning

# External Links

- Algorithm from Wikipedia
- Muḥammad ibn Mūsā al-Khwārizmī
- Banū Mūsā from Wikipedia
- Algorithm characterizations from Wikipedia
- Analysis of algorithms from Wikipedia
- Algorithmic efficiency from Wikipedia
- Big O notation from Wikipedia
- Algorithms - Wikibooks
- Dictionary of Algorithms and Data Structures by Paul E. Black, National Institute of Standards and Technology
- Dictionary of Algorithms and Data Structures from Wikipedia
- The Aggregate Magic Algorithms by Hank Dietz » Bit-Twiddling
- Algorithmic Art by Maarten van Emden
- The Art of Computer Programming from Wikipedia
- Java implementation of algorithms from Norvig and Russell's
*Artificial Intelligence: A Modern Approach*. 3rd edition

## Algorithms

- Algorithms for calculating variance
- Approximation algorithm from Wikipedia
- Cryptographic hash algorithms
- Divide and conquer algorithm

- Deterministic algorithm
- Distributed algorithms
- Nondeterministic algorithm
- Metaheuristic
- Online algorithm
- Parallel algorithm
- Quantum algorithm
- Streaming algorithm

### Algebra and Calculus

- Algorism from Wikipedia
- Berlekamp's algorithm from Wikipedia » Elwyn Berlekamp
- Berlekamp–Massey algorithm from Wikipedia
- Buchberger's algorithm from Wikipedia
- Cantor–Zassenhaus algorithm from Wikipedia
- Computus from Wikipedia
- Divisibility rule from Wikipedia
- Division (digital) from Wikipedia
- Euclidean algorithm from Wikipedia
- Gaussian elimination from Wikipedia
- Gauss–Newton algorithm from Wikipedia
- Householder's method from Wikipedia
- Kuwaiti algorithm from Wikipedia
- Levenberg–Marquardt algorithm from Wikipedia
- Multiplication algorithm from Wikipedia

- Karatsuba algorithm from Wikipedia
- Algorithms: Design and Analysis, Part 1 by Tim Roughgarden, Stanford University, Coursera, YouTube Video

- Numerical analysis from Wikipedia
- Numerical linear algebra from Wikipedia
- Pollard's kangaroo algorithm from Wikipedia
- Quine–McCluskey algorithm from Wikipedia
- Rod calculus from Wikipedia
- Root-finding algorithm from Wikipedia

### Graphics

- Digital Differential Analyzer (graphics algorithm)
- Bresenham's line algorithm
- Xiaolin Wu's line algorithm

### Linear Programming

- Criss-cross algorithm from Wikipedia
- Karmarkar's algorithm from Wikipedia
- Simplex algorithm from Wikipedia

### Sorting and Searching

- A* from Wikipedia
- Bellman–Ford algorithm
- Dijkstra's algorithm
- Flooding algorithm
- Floyd–Warshall algorithm
- Greedy algorithm
- Hill climbing
- Kruskal's algorithm
- Nearest neighbour algorithm
- String searching algorithm

## Complexity

- Complexity from Wikipedia
- Combinatorial explosion from Wikipedia
- Category: Computational complexity theory from Wikipedia
- Complexity class from Wikipedia
- Computational Complexity of Games and Puzzles by David Eppstein
- Computational complexity theory from Wikipedia
- Game complexity from Wikipedia » Games
- Go and mathematics from Wikipedia » Go
- List of complexity classes from Wikipedia
- Problem solving from Wikipedia » Artificial Intelligence
- Reduction (complexity) from Wikipedia
- Shannon number from Wikipedia » Claude Shannon
- Time complexity from Wikipedia
- Wheat and chessboard problem from Wikipedia » Chessboard

## Misc

- Correctness (disambiguation) from Wikipedia
- Correctness (computer science) from Wikipedia
- Halting problem from Wikipedia
- Kraan - Gut und Richtig (1973), YouTube Video

# References

- ↑ A stamp issued September 6, 1983 in the Soviet Union], commemorating Al-Khwārizmī's (approximate) 1200th birthday
- ↑ Kurt Mehlhorn, Peter Sanders (
**2008**).*Data Structures and Algorithms: The Basic Toolbox*. Springer, Appetizer: Integer Arithmetics (pdf) - ↑ The Art of Computer Programming from Wikipedia
- ↑ Ordinal optimization from Wikipedia