This web site is hosted in part by the Software and Systems Division, Information Technology Laboratory.

This is a dictionary of algorithms, algorithmic techniques, data structures, archetypal problems, and related definitions. Algorithms include common functions, such as Ackermann's function. Problems include traveling salesman and Byzantine generals. Some entries have links to implementations and more information. Index pages list entries by area and by type. The two-level index has a total download 1/20 as big as this page.

Don't use this site to cheat.

To define or correct terms, please contact Paul E. Black. We do not include algorithms particular to business data processing, communications, operating systems or distributed algorithms, programming languages, AI, graphics, or numerical analysis: it is tough enough covering "general" algorithms and data structures.

Some terms with a leading variable, such as *n*-way,
*m*-dimensional, or *p*-branching, are under
*k*-.
You may find useful entries in
A
Glossary of Computer Oriented Abbreviations and Acronyms.

*
After more than a decade of service, I will end my editing of DADS.
Everything will move to the
FASTAR
group at University of Pretoria (South Africa), Stellenbosch University
(South Africa),
and Eindhoven
University (Netherlands).
*

To look up words or phrases, enter them in the box, then click the button.

We thank those who contributed definitions as well as many others who offered suggestions and corrections.

Because of operational changes for better web security in February 2009, the URL for DADS changed to http://www.itl.nist.gov/div897/sqg/dads/ Policy changes in September 2010 led to changing the URL to http://xw2k.nist.gov/dads/ Machine changes in February 2011 changed the URL to http://xlinux.nist.gov/dads/ The older URL http://www.nist.gov/dads/ is an alias which should continue to refer to the latest URL. We regret any inconvenience this may cause.

Here are some references on algorithms and data structures.

The Stony Brook Algorithm Repository, which has algorithms organized by type, succinct, illustrated definitions, and ratings of sites with implementations.

Data Structures and Algorithms is a wonderful site with illustrations, explanations, analysis, and code taking the student from arrays and lists through trees, graphs, and intractable problems.

Eric Weisstein's World of Mathematics or MathWorld.

The Sphere online judge (SPOJ) has about 6600 small programming tasks or puzzles and 900 contests. Even nicer it automatically assesses your programs written in 40 languages.

The Computing Research Repository (CoRR). Sixth International Conference on Fun With Algorithms (FUN 2012). The conference "is dedicated to the use, design, and analysis of algorithms and data structures, focusing on results that provide amusing, witty but nonetheless original and scientifically profound contributions to the area."

[AS98]
**Pankaj K. Agarwal** and **Micha Sharir**, *Efficient
Algorithms for Geometric Optimization*, ACM Computing Surveys,
30(4):412-458, December 1998.

[ATCH99] *Algorithms and Theory of Computation
Handbook*,
**Mikhail J. Atallah**, ed., CRC Press LLC, 1999.

[CLR90]
**Thomas H. Cormen, Charles E. Leiserson**, and **Ronald
L. Rivest**, *Introduction to Algorithms*,
MIT Press, 1990.

[GBY91]
**Gaston H. Gonnet** and **Ricardo Baeza-Yates**,
*Handbook of Algorithms and Data Structures -- in Pascal and C*,
2^{nd} edition, Addison-Wesley, 1991.

[GCG92]
**P. Gupta, P. P. Chakrabarti**, and **S. Ghose**,
*The Towers of Hanoi: Generalizations, Specializations, and
Algorithms*, Intern. J. Computer Math., 46:149-161,
Gordon and Breach Science Publishers S.A., 1992.

[GG98]
**Volker Gaede** and **Oliver Günther**,
*Multidimensional Access Methods*, ACM Computing Surveys,
30(2):170-231, June 1998.

[GT97]
**Michael T. Goodrich** and **Roberto Tamassia**,
*Data Structures and Algorithms in Java*,
2^{nd} edition,
John Wiley & Sons, 1997.

[Graef06]
**Goetz Graefe**,
*Implementing Sorting in Database Systems*, ACM Computing Surveys,
38(3), Article 10, September 2006.

[Hirv01]
**Mika Hirvensalo**, *Quantum Computing*,
Springer-Verlag, 2001.

[HS83]
**Ellis Horowitz** and **Sartaj Sahni**,
*Fundamentals of Data Structures*,
Computer Science
Press, 1983.

[Knuth97]
**Donald E. Knuth**, *The Art of Computer
Programming*, Addison-Wesley, volumes 1 and 2, 2^{nd}
edition, 1997.

[Knuth98]
**Donald E. Knuth**, *The Art of Computer
Programming*, Addison-Wesley, volume 3, 2^{nd} edition, 1998.

[Leda98] LEDA (accessed 4 December 2002).

[Sedge97]
**Robert Sedgewick**,
*Algorithms in C*,
Addison-Wesley, 1997.

[Stand98]
**Thomas Standish**, *Data Structures in Java*,
Addison-Wesley, 1998.

[Sund98]
**Daniel M. Sunday**, *A Very Fast Substring
Search Algorithm*, Communications of the ACM, 33(8):132-142,
August 1998.

[Vitt01]
**Jeffrey Scott Vitter**, *External Memory Algorithms
and Data Structures: Dealing with Massive Data*, ACM Computing
Surveys, 33(2):209-271, June 2001.

[Wier98]
**Roel Wieringa**, *A Survey of Structured and
Object-Oriented Software Specification Methods and Techniques*,
ACM Computing Surveys, 30(4):459-527, December 1998.

Here are citation examples and an explanation of credit.

Robots, please index all term pages, including spelling variants.

PRIVACY
POLICY/SECURITY NOTICE/ACCESSIBILITY STATEMENT

NIST is an agency of the
U.S. Department of Commerce

This page's URL is http://xlinux.nist.gov/dads/