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 "K")

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

K

Karmarkar's algorithm
Karnaugh map
Karp-Rabin
Karp reduction
k-ary heap
k-ary Huffman coding
k-ary tree
k-clustering
k-coloring
k-connected graph
k-d-B-tree
k-dimensional
K-dominant match
k-d tree
key
KMP: see Knuth-Morris-Pratt algorithm
KmpSkip Search
knapsack problem
knight's tour
Knuth-Morris-Pratt algorithm
Königsberg bridges problem: see Euler cycle
Kolmogorov complexity
Kraft's inequality
Kripke structure
Kruskal's algorithm
kth order Fibonacci numbers
kth shortest path
kth smallest element: see select kth element
KV diagram: see Karnaugh map
k-way merge
k-way merge sort
k-way tree: see k-ary tree

Karnaugh map

(algorithm)

Definition: A method for minimizing a boolean expression, usually aided by a rectangular map of the value of the expression for all possible input values. Input values are arranged in a Gray code. Maximal rectangular groups that cover the inputs where the expression is true give a minimum implementation.

Also known as Veitch diagram, KV diagram.

Aggregate child (... is a part of or used in me.)
Gray code.

Note: "Karnaugh" is pronounced "car-no".

In the example, "*" means "don't care", that is, it doesn't matter what the function value is for those inputs. This expression may be realized as AB' + AD + BC'D + B'CD'. Some expressions may be implemented more compactly by grouping the zeros, possibly including "don't care" cells, and negating the final output. The positive implementation is smaller for this expression.

Author: SKS

More information

A primer on Karnaugh maps motivated by minimizing logic. An interactive quiz.

Maurice Karnaugh, The Map Method for Synthesis of Combinational Logic Circuits, Trans. AIEE. pt I, 72(9):593-599, November 1953.


Karp-Rabin

(algorithm)

Definition: A string matching algorithm that compares string's hash values, rather than the strings themselves. For efficiency, the hash value of the next position in the text is easily computed from the hash value of the current position.

Also known as Rabin-Karp.

Author: PEB


Karp reduction

(definition)

Definition: A reduction given by a polynomial time computable transformation function.

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

Author: CRC-A


k-ary heap

(data structure)

Definition: A complete tree where every node has a key more extreme (greater or less) than the key of its parent. Each node has k or fewer children.

Author: CLK


k-ary Huffman coding

(algorithm)

Definition: A minimal variable-length coding based on the frequency of each character. Similar to a Huffman coding, but joins k trees into a k-ary tree at each step, and uses k symbols for each level.

Note: The coding at each stage has k symbols, not just 2 (0 or 1) like traditional Huffman. If k is a power of two, that is, k=2n, every symbol can be represented by n bits.

Author: PEB


k-ary tree

(data structure)

Definition: A tree with no more than k children for each node.

Also known as k-way tree.

Generalization (I am a kind of ...)
tree, multiway tree.

Specialization (... is a kind of me.)
binary tree, ternary search tree.

Note: A k-ary tree may be thought of as a multiway tree limited to k children.

Each node may be implemented as an array, a linked list, a tree (see binary tree representation of trees), or more elaborate schemes such as mentioned at multiway tree.

In an array implementation for a tree without insertions, nodes might be overlapped in one big array, since many entries are note used. Such an improvement is also referred to as "packed" or "compressed".

Author: PEB


k-coloring

(definition)

Definition: 1) The assignment of k colors (or any distinct marks) to the vertices of a graph. 2) The assignment of k colors to the edges of a graph.

A coloring is a proper coloring if no two adjacent vertices or edges have the same color.

Author: ME


k-connected graph

(definition)

Definition: A connected graph such that deleting any k-1 vertices (and incident edges) results in a graph that is still connected.

Note: Informally, there are at least k independent paths from any vertex to any other vertex.

Author: PMS


k-d-B-tree

(data structure)

Definition: A data structure which splits multidimensional spaces like an adaptive k-d tree, but balances the resulting tree like a B-tree.

Note: After [GG98].

Author: PEB


k-dimensional

(definition)

Definition: (1) Dealing with or restricted to a space where location can be completely described with exactly k orthogonal axes. (2) Dealing with a space of any number of dimensions.

Author: PEB


K-dominant match

(definition)

Definition: A match [i,j] having rank k and such that for any other pair [i',j'] of rank k either i'>i and j'≤ j or i' ≤ i and j'>j.

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

Author: CRC-A


k-d tree

(data structure)

Definition: A multidimensional search tree for points in k dimensional space. Levels of the tree are split along successive dimensions at the points.

Note: After [GG98]. Robert Keith Oswald (rko9h@virginia.edu) explains, In a traditional binary search tree, records are defined by only one key. In a k-d tree, records are defined by k keys. Like a traditional binary search trees, records are inserted and returned using < and ≥. However, the key that determines the subtree to use (i.e. left or right) varies with the level in the tree. At level L, key number L mod k + 1 is used, where the root is at level 0. Therefore, the first key is used at the root, the second key at level 1, and so on until all keys have been used. The keys are used again beginning at level k.

Author: PEB


key

(definition)

Definition: The part of a group of data by which it is sorted, indexed, cross referenced, etc.

Note: For instance, to sort customer records alphabetically, the key is the last name, then the given names. Other information, such as the address, outstanding balance, credit limit, etc. do not matter in sorting the records alphabetically. Different keys may be used at different times, for instance, an accounting report may need customers with larger balances first, so the records could be sorted using the outstanding balance as the key.

Author: PEB


knapsack problem

(classic problem)

Definition: Given items of different values and volumes, find the most valuable set of items that fit in a knapsack of fixed volume.

Formal Definition: There is a knapsack of capacity c > 0 and N items. Each item has value vi > 0 and weight wi > 0. Find the selection of items (δi = 1 if selected, 0 if not) that fit, ∑i=1N δiwi ≤ c, and the total value, ∑i=1N δivi, is maximized.

Also known as 0-1 knapsack problem, binary knapsack problem.

Note: Also called 0-1 or binary knapsack (each item may be taken (1) or not (0)), in contrast to the fractional knapsack problem. Also called bounded knapsack (BKP) because there are a limited number of items, in contrast to the unbounded knapsack problem. The decision problem is, given items of different values and volumes and a knapsack, is there a subset that exceeds a certain value? The decision problem is NP-complete.

Pictures of several reproduction knapsacks, many with rigid internal frames.

Author: PEB


knight's tour

(classic problem)

Definition: A series of moves of a chess knight that visits all squares on the board exactly once.

Note: The associated problem is to find such a series of moves. The problem can be generalized to an n × m rectangular chess board. Solutions may be found using backtracking.

Author: PEB

More information

Dan Thomasson's Knight's Tour page, with application to prime numbers, tour on a cube's face, etc.


Knuth-Morris-Pratt algorithm

(algorithm)

Definition: A string matching algorithm that turns the search string into a finite state machine, then runs the machine with the string to be searched as the input string. Execution time is O(m+n), where m is the length of the search string, and n is the length of the string to be searched.

Also known as KMP.

Author: SB

More information

Series of pages explaining how Knuth-Morris-Pratt works.

Donald E. Knuth, James H. Morris, and Vaughan R. Pratt, Fast Pattern Matching in Strings, SIAM Journal on Computing, 6(2):323-350, 1977.


Kolmogorov complexity

(definition)

Definition: The minimum number of bits into which a string can be compressed without losing information. This is defined with respect to a fixed, but universal decompression scheme, given by a universal Turing machine.

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

Author: CRC-A

More information

Special issue of the Computer Journal on Kolmogorov Complexity (1999). Tributes to, pictures of, bibliography of, etc. Andrei Nikolaevich Kolmogorov.


Kraft's inequality

(definition)

Definition:i=1N 2-c(i) ≤ 1, where N is the number of leaves in a binary tree and c(i) is the depth of leaf i.

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

Author: CRC-A


Kripke structure

(definition)

Definition: A nondeterministic finite state machine whose states are labeled with boolean variables, which are the evaluations of expressions in that state. It may be extended with fairness constraints.

Author: PEB


Kruskal's algorithm

(algorithm)

Definition: An algorithm for computing a minimum spanning tree. It maintains a set of partial minimum spanning trees, and repeatedly adds the shortest edge in the graph whose vertices are in different partial minimum spanning trees.

Author: JLG

More information

Eppstein's lecture outlining and contrasting MST algorithms.


kth order Fibonacci numbers

(definition)

Definition: A sequence of numbers where each number is the sum of the k preceding numbers. The usual Fibonacci numbers occur when k=2.

Formal Definition:

  • F(k)n = F(k)n-1 + F(k)n-2 + . . . + F(k)n-k      for n ≥ k.
  • F(k)k-1 = 1
  • F(k)n = 0      for   0 ≤ n ≤ k-2

Also known as pth order Fibonacci numbers.

Author: PEB

More information

Apparently first studied by V. Schlegel, El Progreso Matemático, 4:173-174, 1894.


kth shortest path

(classic problem)

Definition: The problem of finding the kth shortest path from one vertex in a graph to another vertex. Variants may require that paths are edge- or vertex-disjoint, that is sharing no edges or vertices. "Shortest" may be least number of edges, least total weight, etc.

Specialization (... is a kind of me.)
shortest path.

Author: PEB

More information

The optimal problem page with definitions, links to basic concepts, variants, and algorithms.


k-way merge

(definition)

Definition: Combine k sorted data streams into a single sorted stream.

Generalization (I am a kind of ...)
multiway merge, merge.

Aggregate parent (I am a part of or used in ...)
k-way merge sort.

Author: PEB


k-way merge sort

(algorithm)

Definition: A merge sort that sorts a data stream using repeated merges. It distributes the input into k streams by repeatedly reading a block of input that fits in memory, called a run, sorting it, then writing it to the next stream. It merges runs from the k streams into an output stream. It then repeatedly distributes the runs in the output stream to the k streams and merges them until there is a single sorted output.

Also known as p-way merge sort.

Aggregate child (... is a part of or used in me.)
k-way merge.

Note: This is an external sort.

Author: ASK



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-2024 by TranslationDirectory.com
Legal Disclaimer
Site Map