---
created_at: '2016-10-21T04:40:01.000Z'
title: Dictionary of Algorithms and Data Structures (1998)
url: https://xlinux.nist.gov/dads/
author: nullgeo
points: 222
story_text: 
comment_text: 
num_comments: 18
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1477024801
_tags:
- story
- author_nullgeo
- story_12758176
objectID: '12758176'
year: 1998

---
# Dictionary of Algorithms and Data Structures

This web site is hosted by the [Software and Systems
Division](https://www.nist.gov/itl/ssd), [Information Technology
Laboratory](https://www.nist.gov/itl), [NIST](https://www.nist.gov/).
Development of this dictionary started in 1998 under the editorship of
Paul E. Black.

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

Don't use this site to cheat. Teachers, contact us if we can help.

Currently 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.  If you have
suggestions, corrections, or comments, please get in touch with [Paul
Black](mailto:paul.black@nist.gov).

Some terms with a leading variable, such as n-way, m-dimensional, or
p-branching, are under [k-](#K). You may find useful entries in [A
Glossary of Computer Oriented Abbreviations and
Acronyms](http://www.arcelect.com/babel99.htm).

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

[![Google](http://www.google.com/logos/Google_Safe.gif)](http://www.google.com/webhp?safe=vss)  
Web DADS  

We thank [those who contributed definitions](Other/contrib.html) as well
as many others who offered suggestions and corrections.

After more than a decade of service as editor of DADS, Paul Black was
joined by Vreda Pieterse of the [FASTAR group](http://fastar.org/) at
Stellenbosch University (South Africa), University of Pretoria, and
Eindhoven University (Netherlands) as co-editor. The URL
https://www.nist.gov/dads/ is an alias which should continue to refer to
DADS. We regret any inconvenience this may cause.

Here are some references on algorithms and data structures.

The [Stony Brook Algorithm
Repository](http://www3.cs.stonybrook.edu/~algorith/), which has
algorithms organized by type, succinct, illustrated definitions, and
ratings of sites with implementations.

[Data Structures and
Algorithms](http://www.cs.auckland.ac.nz/software/AlgAnim/ds_ToC.html)
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](http://mathworld.wolfram.com/)
or MathWorld.

The [Sphere online judge](http://www.spoj.com/) (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](https://arxiv.org/corr/home) (CoRR).

Eighth International Conference on [Fun With
Algorithms](http://www2.idsia.ch/cms/fun16/) (FUN 2016). 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."

## Bibliography

\[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, 2nd 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, 2nd 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, 2nd edition, 1997.

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

\[Leda98\] [LEDA](http://www.algorithmic-solutions.com/enleda.htm)
(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](Other/creditNotice.html).

Robots, please index [all term pages, including spelling
variants](ui.html).

[![Viewable With Any
Browser](Images/anybrowser4.gif)](http://www.anybrowser.org/campaign/)

Created Fri Sep 4 16:39:23 1998 This Trailer Updated Mon Sep 18 10:12:55
2017

This page's URL is <https://www.nist.gov/dads/>