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
K
 Karmarkar's algorithm
 Karnaugh map
 KarpRabin
 Karp reduction
 kary heap
 kary Huffman coding
 kary tree
 kclustering
 kcoloring
 kconnected graph
 kdBtree
 kdimensional
 Kdominant match
 kd tree
 key
 KMP: see KnuthMorrisPratt algorithm
 KmpSkip Search
 knapsack problem
 knight's tour
 KnuthMorrisPratt algorithm
 Königsberg bridges problem: see Euler cycle
 Kolmogorov complexity
 Kraft's inequality
 Kripke structure
 Kruskal's algorithm
 kth order Fibonacci numbers
 k^{th} shortest path
 k^{th} smallest element: see select k^{th} element
 KV diagram: see Karnaugh map
 kway merge
 kway merge sort
 kway tree: see kary 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 "carno". 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):593599, November 1953.
KarpRabin
(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 RabinKarp.
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 2825, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
kary 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
kary Huffman coding
(algorithm)
Definition:
A minimal variablelength coding based on the frequency of each character. Similar to a Huffman coding, but joins k trees into a kary 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=2^{n}, every symbol can be represented by n bits.
Author: PEB
kary tree
(data structure)
Definition:
A tree with no more than k children for each node.
Also known as kway tree.
Generalization (I am a kind of ...)
tree, multiway tree.
Specialization (... is a kind of me.)
binary tree, ternary search tree.
Note:
A kary 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
kcoloring
(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
kconnected graph
(definition)
Definition:
A connected graph such that deleting any k1 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
kdBtree
(data structure)
Definition:
A data structure which splits multidimensional spaces like an adaptive kd tree, but balances the resulting tree like a Btree.
Note:
After [GG98].
Author: PEB
kdimensional
(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
Kdominant 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 1318, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
kd 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 kd 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 v_{i} > 0 and weight w_{i} > 0. Find the selection of items (δ_{i} = 1 if selected, 0 if not) that fit, ∑_{i=1}^{N} δ_{i}w_{i} ≤ c, and the total value, ∑_{i=1}^{N} δ_{i}v_{i}, is maximized.
Also known as 01 knapsack problem, binary knapsack problem.
Note:
Also called 01 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 NPcomplete.
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.
KnuthMorrisPratt 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 KnuthMorrisPratt works.
Donald E. Knuth, James H. Morris, and Vaughan R. Pratt, Fast Pattern Matching in Strings, SIAM Journal on Computing, 6(2):323350, 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 2920, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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=1}^{N} 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 126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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)}_{n1} + F^{(k)}_{n2} + . . . + F^{(k)}_{nk} for n ≥ k.
 F^{(k)}_{k1} = 1
 F^{(k)}_{n} = 0 for 0 ≤ n ≤ k2
Also known as pth order Fibonacci numbers.
Author: PEB
More information
Apparently first studied by V. Schlegel, El Progreso Matemático, 4:173174, 1894.
k^{th} shortest path
(classic problem)
Definition:
The problem of finding the k^{th} shortest path from one vertex in a graph to another vertex. Variants may require that paths are edge or vertexdisjoint, 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.
kway 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 ...)
kway merge sort.
Author: PEB
kway 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 pway merge sort.
Aggregate child (... is a part of or used in me.)
kway merge.
Note:
This is an external sort.
Author: ASK
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
