175 lines
6.4 KiB
Markdown
175 lines
6.4 KiB
Markdown
---
|
|
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.
|
|
|
|
[](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).
|
|
|
|
[](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/>
|