Programming with Judy

63
Glossary
Terms in this glossary attributed
to (NIST) are derived from the
National Institute of Standards
and Technology (NIST) glossary.
Other terms are derived from the
Free Online Dictionary of
Computing and whatis?com.
1
A
abstract data type (ADT) A
mathematically specified
collection of data-storing entities
with operations to create, access,
or change instances. (NIST) See
also data structure.
algorithm A computable set of
steps to achieve a desired result.
The word comes from the Persian
author Abu Ja'far Mohammed ibn
Mûsâ al-Khowârizmî who wrote a
book with arithmetic rules dating
from about 825 A.D. (NIST)
array A set of items that are
randomly accessible by numeric
index. (NIST)
API See Application
Programming Interface.
Application Programming
Interface (API) The interface
(calling conventions) by which an
application program accesses an
operating system and other
services.
B
B-tree A balanced search tree in
which every node has between t-1
and 2t-1 children, where t is an
arbitrary constant. This is a good
structure if much of the tree is in
slow memory (disk), since the
height, and hence the number of
accesses, can be kept small, say
one or two, by picking a large t.
(NIST)
big-O notation A theoretical
measurement used to compare
two algorithms that accomplish
the same task, usually in terms of
the time or memory needed.
binary tree A tree with at most
two children for each node. (NIST)
bit array An array whose values
are bits.
C
cache A small fast memory
holding recently accessed data,
designed to speed up subsequent
access to the same data. Most
often applied to CPU access but
also used for a local copy of data
accessible over a network or disk.
cache line A block of memory
local to a CPU chip that caches the
same sized block from the
1. Glossary web sites are at http://hissa.nist.gov/dads/terms.html,
http://www.instantweb.com and
http://foldoc/whatis.techtarget.com.