Home * Programming * Algorithms

Muḥammad ibn Mūsā al-Khwārizmī ¹

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

General Concepts

• General Setwise Operations
• Iteration
• Pseudorandom Number Generator
• Recursion

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

• Backtracking
• De Bruijn Sequence Generator
• Traversing Subsets of a Set
• Trial and Error

Mathematical Optimization

• CLOP
• Dynamic Programming
• Evolutionary Algorithms
• Hill Climbing
• Simulated Annealing
• SPSA

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) ²

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

Watch on YouTube

• 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

• Category:Algorithms from Wikipedia

Algorithms for calculating variance

Approximation algorithm from Wikipedia

Cryptographic hash algorithms

Divide and conquer algorithm

• List of algorithms from Wikipedia

Deterministic algorithm

Distributed algorithms

Nondeterministic algorithm

Metaheuristic

Online algorithm

Parallel algorithm

Quantum algorithm

Streaming algorithm

• Randomized algorithm from Wikipedia

Las Vegas algorithm

Monte Carlo algorithm

Pseudorandom number generator

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

Watch on YouTube

• 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

• Even-odd rule from Wikipedia
• Flood fill from Wikipedia
• Line drawing algorithm from Wikipedia

Digital Differential Analyzer (graphics algorithm)

Bresenham's line algorithm

Xiaolin Wu's line algorithm

• Ray tracing (graphics) from Wikipedia
• Spline interpolation from Wikipedia

De Boor's algorithm

De Casteljau's algorithm

Linear Programming

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

Sorting and Searching

• Merge algorithm from Wikipedia
• Search algorithm from Wikipedia

[https://en.wikipedia.org/wiki/A* 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

• Sorting algorithm from Wikipedia

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

Watch on YouTube

References