This web site is hosted by

the

Software and Systems Division,

Information Technology Laboratory,

NIST.

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.

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

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.

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

button.

### A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

We thank

those who contributed definitions

as well as many others who offered suggestions and corrections.

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, 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).

Tenth International Conference on

Fun

With Algorithms (FUN 2020). 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.”

Sixth International Conference on

Creative Mathematical Sciences

Communication (CMSC 2022). The conference “is to explore new ways

of communicating mathematical sciences” and “will host a unique

interaction between artists (theatre, dance, graphic arts, story) and

scientists /teachers/communicators.” The notion is to build on

“Computer Science Unplugged, Algorithms Unplugged, the IMAGINATION

project, Bebras and other similar efforts.”

## 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*,

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

Library of Efficient Data types and Algorithms

(accessed 17 June 2019).

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

*Created
Fri Sep 4 16:39:23 1998
*

(paul.black@nist.gov)

*This Trailer*

*Updated
Mon Nov 22 15:20:31 2021
*

(paul.black@nist.gov)

This page’s URL is

https://www.nist.gov/dads/

DOI 10.18434/T4/1422485