Algorithms and Data Structures Glossary Free glossaries at TanslationDirectory.com translation jobs
Home Free Glossaries Free Dictionaries Post Your Translation Job! Free Articles Jobs for Translators

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 $8 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

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 2d children.

Note: It was originally designed for 2-dimensional 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 2q× 2q 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 three-dimensional data where the perimeter is replaced by surface area, and in general for d-dimensions where instead of perimeter we have the size of the (d-1)-dimensional interfaces between the d-dimensional objects.

Note: From Algorithms and Theory of Computation Handbook, page 18-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A


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 146-149].

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, Deutsch-Jozsa 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):1411-1473, 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 "first-in, first-out" 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.

  1. new() returns a queue
  2. front(add(v, new())) = v
  3. remove(add(v, new())) = new()
  4. front(add(v, add(w, Q))) = front(add(w, Q))
  5. 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 ...)
in-place 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) worst-case running time.

Author: CM

More information

Java applet animation (Java). Comparison of quicksort, heapsort, and merge sort on modern processors.



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

 

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



 



Free Newsletter

Subscribe to our free newsletter to receive news from us:

 

Menu

Use More Glossaries
Use Free Dictionaries
Use Free Translators
Submit Your Glossary
Read Translation Articles
Register Translation Agency
Submit Your Resume
Obtain Translation Jobs
Subscribe to Free Newsletter
Buy Database of Translators
Obtain Blacklisted Agencies
Vote in Polls for Translators
Read News for Translators
Advertise Here
Read our FAQ
Read Testimonials
Use Site Map

Advertisements

translation directory

christianity portal
translation jobs


 

 
Copyright © 2003-2020 by TranslationDirectory.com
Legal Disclaimer
Site Map