﻿ Algorithms and Data Structures Glossary (Starting with "K")    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

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

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

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

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

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

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

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

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.

 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

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

 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       