Algorithms and Data Structures Glossary (Starting with "Q")
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
Q
 qm sort
 q sort
 quadratic probing
 quadtree
 quadtree complexity theorem
 quad trie
 quantum computation
 queue
 quick search
 quicksort
quadratic probing
(algorithm)
Definition:
A method of open addressing for a hash table in which a collision is resolved by putting the item in the next empty place given by a probe sequence. The space between places in the sequence increases quadratically.
Note:
Deletion may be hard because finding collisions again relies on not creating empty spots. One solution is to mark an entry as deleted so it can be reused for insertion, but the search list is intact.
Author: PEB
More information
An explanation of how quadratic equations got their name.
quadtree
(data structure)
Definition:
A tree where each node is split along all d dimensions, leading to 2^{d} children.
Note:
It was originally designed for 2dimensional data (pictures), so each node had four children, hence quadtree. After [GG98].
Author: PEB
quadtree complexity theorem
(definition)
Definition:
The number of nodes in a quadtree region representation for a simple polygon (i.e. with nonintersecting edges and without holes) is O(p+q) for a 2^{q}× 2^{q} image with perimeter p measured in pixel widths. In most cases, q is negligible, and thus, the number of nodes is proportional to the perimeter. It also holds for threedimensional data where the perimeter is replaced by surface area, and in general for ddimensions where instead of perimeter we have the size of the (d1)dimensional interfaces between the ddimensional objects.
Note:
From Algorithms and Theory of Computation Handbook, page 1824, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
quad trie
(data structure)
Definition:
A tree in which each node is split according to some subset of the key, typically a character.
Note:
After [GBY91, pages 146149].
The name comes from reTRIEval and is pronounced, "tree." See the historical note at trie.
Author: PEB
quantum computation
(definition)
Definition:
Computation based on quantum mechanical effects, such as superposition and entanglement, in addition to classical digital manipulations.
Specialization (... is a kind of me.)
Shor's algorithm, Grover's algorithm, Simon's algorithm, DeutschJozsa algorithm.
Note:
Quantum computers can, in theory, make computations that are impossible to do exactly with classical computers or achieve exponential speedup. Since nobody has yet (as of February 2005) implemented more than a few bit operations, problems such as decoherence and measurement error may limit quantum computation to a few specialized roles.
Author: PEB
More information
Ethan Bernstein and Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, 26(5):14111473, 1997.
queue
(data structure)
Definition:
A collection of items in which only the earliest added item may be accessed. Basic operations are add (to the tail) or enqueue and delete (from the head) or dequeue. Delete returns the item removed. Also known as "firstin, firstout" or FIFO.
Formal Definition: It is convenient to define delete or dequeue in terms of remove and a new operation, front. The operations new(), add(v, Q), front(Q), and remove(Q) may be defined with axiomatic semantics as follows.
 new() returns a queue
 front(add(v, new())) = v
 remove(add(v, new())) = new()
 front(add(v, add(w, Q))) = front(add(w, Q))
 remove(add(v, add(w, Q))) = add(v, remove(add(w, Q)))
where Q is a queue and v and w are values.
Also known as FIFO.
Generalization (I am a kind of ...)
abstract data type.
Specialization (... is a kind of me.)
bounded queue.
Author: PEB
More information
Demonstrations with dynamic array, fixed array, and linked list implementations.
quick search
(algorithm)
Definition:
A string matching algorithm that compares characters from the end of the search string to its beginning. When a character doesn't match, the next character in the text beyond the search string determines where the next possible match begins.
Note:
After [Sund98].
Author: PEB
quicksort
(algorithm)
Definition:
Pick an element from the array (the pivot), partition the remaining elements into those greater than and less than this pivot, and recursively sort the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.
Generalization (I am a kind of ...)
inplace sort.
Specialization (... is a kind of me.)
balanced quicksort, multikey Quicksort, introspective sort.
Aggregate child (... is a part of or used in me.)
partition, divide and conquer, recursion, Select, sublinear time algorithm.
Note:
Quicksort has running time Θ(n²) in the worst case, but it is typically O(n log n). In practical situations, a finely tuned implementation of quicksort beats most sort algorithms, including sort algorithms whose theoretical complexity is O(n log n) in the worst case.
Select can be used to always pick good pivots, thus giving a variant with O(n log n) worstcase running time.
Author: CM
More information
Java applet animation (Java). Comparison of quicksort, heapsort, and merge sort on modern processors.
Published  April 2009
Find free glossaries at TranslationDirectory.com
Find free dictionaries at TranslationDirectory.com
Subscribe to free TranslationDirectory.com newsletter
Need more translation jobs from translation agencies? Click here!
Translation agencies are welcome to register here  Free!
Freelance translators are welcome to register here  Free!
Submit your glossary or dictionary for publishing at TranslationDirectory.com
