Algorithms and Data Structures Glossary (Starting with "Z")

Free glossaries at TanslationDirectory.com

Algorithms and Data Structures Glossary
(Starting with "Z")

By www.nist.gov,
Gaithersburg, Maryland, U.S.A.

paul . black [at] nist . gov
http://www.nist.gov/dads

Become a member of TranslationDirectory.com at just $12 per month (paid per year)

Advertisements:

Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously

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

Z

Zeller's congruence
0-ary function
0-based indexing
0-1 knapsack problem: see knapsack problem
Zhu-Takaoka
Zipfian distribution
Zipf's law
zipper
ZPP

Zeller's congruence

(algorithm)

Definition: An algorithm to find the day of the week for any date.

Author: PEB

More information

Wikipedia entry for Zeller's congruence. A summary of the International Standard Date and Time Notation ISO 8601. The full ISO 8601:2004 standard.

Christian Zeller, Kalender-Formeln, Acta Mathematica, 9:131-6, Nov 1886.

0-ary function

(definition)

Definition: A function that takes no arguments.

Also known as nullary function.

Note: Pronounced "zero-airy". By analogy to unary, binary, etc.

A 0-ary or nullary function that is pure (no state or interactions with external variables) must be a constant function.

Author: PEB

0-based indexing

(definition)

Definition: Indexing (an array) beginning with 0.

Aggregate parent (I am a part of or used in ...)
array.

Note: That is, an array A with n items is accessed as A[0], A[1], ..., A[n-1].

Author: PEB

Zhu-Takaoka

(algorithm)

Definition: A string matching algorithm that is a variant of the Boyer-Moore algorithm. It uses two consecutive text characters to compute the bad character shift. It is faster when the alphabet or pattern is small, but the skip table grows quickly, slowing the pre-processing phase.

Author: BB

More information

R. F. Zhu and T. Takaoka, On improving the average case of the Boyer-Moore string matching algorithm, J. Inform. Process. 10(3):173-177 (1987).

Zipfian distribution

(definition)

Definition: A distribution of probabilities of occurrence that follows Zipf's law.

Also known as Yule distribution.

Note: The distribution of words is often proportional to a function like 1/n^a.

Author: PEB

Zipf's law

(definition)

Definition: The probability of occurrence of words or other items starts high and tapers off. Thus, a few occur very often while many others occur rarely.

Formal Definition: P_n 1/n^a, where P_n is the frequency of occurrence of the n^th ranked item and a is close to 1.

Note: In the English language words like "and," "the," "to," and "of" occur often while words like "undeniable" are rare. This law applies to words in human or computer languages, operating system calls, colors in images, etc., and is the basis of many (if not, all!) compression approaches.

Named for George Kingsley Zipf.

Author: PEB

zipper

(data structure)

Definition: A data structure equivalent to a binary tree that is "opened" so that some node is accessible. It consists of a pair: the current node, along with information to reconstruct the tree. Reconstruction information is called the path or context. A move-to-left-child operation returns the left subtree, along with a new path, which has (i) a Left value, (ii) the current node, (iii) the right subtree, and (iv) any previous path. A similar operation moves to the right child. A move-up operation returns a tree rebuilt from the path information and the current node, along with the previous path.

Note: In functional programming languages, a zipper acts as a "pointer" into a tree. The name comes from visualizing the move-to-child operation as unzipping a tree. (Instead of two halves, though, move-to-child keeps the pieces in a k-ary tree: the path.)

Author: PEB

More information

Gérard Huet, The Zipper, Journal of Functional Programming, 7(5):549-554, 1997.

ZPP

(definition)

Definition: The class of languages for which a membership computation by a probabilistic Turing machine halts in polynomial time with no false acceptances or rejections, but randomly some "I don't know" answers. "ZPP" means "Zero error Probability in Polynomial" time.

Formal Definition: For a language, S, there exists a probabilistic Turing machine, M, that halts in polynomial time. M (correctly) accepts or rejects the string or, randomly, halts in an "I don't know" state.

Note: By repeating the run, the correct answer will always be found, albeit with polynomial expected run time.

After [Hirv01, page 19].

Author: PEB

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