Algorithms and Data Structures Glossary
(Starting with "C")
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
C
- cactus stack
- Calculus of Communicating Systems
- calendar queue
- candidate consistency testing
- candidate verification
- canonical complexity class
- capacitated facility location
- capacity
- capacity constraint
- cartesian tree: see randomized binary search tree
- cascade merge sort
- Caverphone
- CCS
- cell probe model
- cell tree
- cellular automaton
- centroid
- certificate
- chain
- chaining
- child
- Chinese postman problem
- Chinese remainder theorem
- Christofides algorithm
- chromatic index
- chromatic number
- circuit
- circuit complexity
- circuit value problem
- circular list
- circular queue
- clique
- clique problem
- clustering
- clustering free
- coalesced chaining
- coarsening
- cocktail shaker sort: see bidirectional bubble sort
- codeword
- coding tree
- Collatz problem
- collective recursion
- collision
- collision resolution scheme
- Colussi
- combination
- comb sort
- Commentz-Walter
- Communicating Sequential Processes
- commutative
- compact DAWG
- compact trie
- comparison sort
- competitive analysis
- competitive ratio
- complement
- complete binary tree
- complete graph
- completely connected graph
- complete tree
- complexity
- complexity class
- computable
- concave function
- concurrent flow
- concurrent read, concurrent write
- concurrent read, exclusive write
- confluently persistent data structure
- conjunction
- connected components
- connected graph
- constant function
- continuous knapsack problem: see fractional knapsack problem
- Cook reduction
- Cook's theorem
- CORDIC
- counting sort
- covering
- CRC: see cyclic redundancy check
- CRCW: see concurrent read, concurrent write
- CREW: see concurrent read, exclusive write
- critical path problem
- CSP
- CTL
- cube root
- cuckoo hashing
- cut
- cutting plane
- cutting stock problem
- cutting theorem
- cut vertex
- cycle
- cyclic redundancy check
cactus stack
(data structure)
Definition:
A variant of stack in which one other cactus stack may be attached to the top. An attached stack is called a "branch." When a branch becomes empty, it is removed. Pop is not allowed if there is a branch. A branch is only accessible through the original reference; it is not accessible through the stack.
Formal Definition: The operations new to this variant of stack, branch(S, T) and notch(v), may be defined with axiomatic semantics as follows.
- top(branch(S, T)) = top(S)
- notch(new()) = false
- notch(push(v, S)) = false
- notch(branch(S, T)) = true
Also known as saguaro stack.
Generalization (I am a kind of ...)
stack, tree.
Note:
A saguaro is a kind of branching cactus.
Author: PEB
More information
Pictures and a description of saguaro cactus.
Calculus of Communicating Systems
(definition)
Definition:
Robin Milner's algebraic theory to formalize the notion of concurrent computation. Commonly known as CCS.
Author: SKS
calendar queue
(data structure)
Definition:
A fast priority queue implementation having N buckets each with width w, or covering w time. An item with priority p more than current goes in bucket (p/w)%N. Choose N and w to have few items in each bucket. Keep items sorted within buckets. Double or halve N and change w if the number of items grows or shrinks a lot.
Author: PEB
More information
Randy Brown, Calendar Queues: A Fast 0(1) Priority Queue Implementation for the Simulation Event Set Problem, CACM, 31(10):1220-1227, October 1988. R. Jain, The Art of Computer Systems Performance Analysis, John Wiley and Sons, Inc., 1996, page 410.
candidate consistency testing
(definition)
Definition:
The stage of two-dimensional matching where a candidate occurrence of the pattern is checked against the "witness" table.
Note:
From Algorithms and Theory of Computation Handbook, page 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
candidate verification
(definition)
Definition:
The stage of two-dimensional matching where candidate occurrences of the pattern are actually tested.
Note:
From Algorithms and Theory of Computation Handbook, page 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
canonical complexity class
(definition)
Definition:
One of the classes defined by logarithmic, polynomial, and exponential bounds on time and space, for deterministic and nondeterministic machines. These classify most of the important computational problems.
Note:
From Algorithms and Theory of Computation Handbook, page 27-21, 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
Scott Aaronson's Complexity Zoo
capacitated facility location
(classic problem)
Definition:
Given a set of demand points, a distance function, and a parameter p, find a set of p supply object (points, lines, segments, etc.) which minimizes some distance objective function and no supply supports too many demand points.
Note:
Adapted from [AS98, page 428].
Author: PEB
capacity
(definition)
Definition:
The maximum flow that may be sent through an edge or a vertex.
Note:
Formally the capacity is just a weight, but because it is used with networks and flows, it is helpful to think of it as analogous to a physical capacity.
From Algorithms and Theory of Computation Handbook, page 7-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
capacity constraint
(definition)
Definition:
The property that the flow on every edge of a flow network is no more than the edge's capacity. More formally, for all edges e, f(e) ≤ u(e), where f(e) is the flow on e and u(e) is its capacity.
Note:
From Algorithms and Theory of Computation Handbook, page 7-10, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
Caverphone
(algorithm)
Definition:
An algorithm to code English names phonetically.
Generalization (I am a kind of ...)
phonetic coding algorithm.
Note:
The first Caverphone algorithm is similar to metaphone, but customized for the Caversham data set (names and accents in the southern part of Dunedin, New Zealand in 1893-1938). The updated algorithm, 2.0, is a "general purpose English phonetic matching system."
Author: PEB
CCS
(definition)
Definition:
Robin Milner's algebraic theory to formalize the notion of concurrent computation. An acronym for Calculus of Communicating Systems.
Author: SKS
cell probe model
(definition)
Definition:
A model of computation where the cost of a computation is measured by the total number of memory accesses to a random access memory with  log n bits cell size. All other computations are not counted and are considered to be free.
Note:
From Algorithms and Theory of Computation Handbook, page 5-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
cell tree
(data structure)
Definition:
A spatial access method where successive levels are split by arbitrary hyperplanes. Concave objects are decomposed into convex pieces. Each convex piece is indexed in every cell which it overlaps.
Note:
After [GG98].
Author: PEB
cellular automaton
(definition)
Definition:
Usually a two-dimensional organization of simple finite state machines whose next state depends on their own state and the states of their eight closest neighbors. In general the machines may be arranged in meshes of higher or lower dimension, have larger neighborhoods, or be arbitrarily complex processors.
Note:
Conway's game of Life is probably the most well known instance of a cellular automaton.
Author: PEB
centroid
(definition)
Definition:
The center of gravity or center of mass of an object.
Author: PEB
More information
Clark Kimberling's pictorial example and physical method of finding the centroid of an plane object. A more analytical description and information about the word's origin.
certificate
(definition)
Definition:
(1) Extra information so the correctness of an answer to a decision problem can be quickly checked. (2) For any graph property P and graph G, a certificate for G is a graph G' such that G has property P if and only if G' has the property.
Note:
(1) After comp.theory FAQ. (2) From Algorithms and Theory of Computation Handbook, page 8-22, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Authors: PEB,CRC-A
chain
(definition)
Definition:
A set with a total order.
Author: PEB
chaining
(data structure)
Definition:
A class of collision resolution schemes in which linked lists handle collisions in a hash table. The two main subclasses are separate chaining, where lists are outside the table, and coalesced chaining, where the lists are within the table.
Generalization (I am a kind of ...)
collision resolution scheme.
Specialization (... is a kind of me.)
coalesced chaining, separate chaining.
Aggregate child (... is a part of or used in me.)
load factor.
Note:
Any searchable data structure may be used instead of a linked list, but it is usually better to expand the hash table, thus lowering the load factor, and use a simple collision resolution mechanism, like the linked list.
Author: PEB
child
(definition)
Definition:
A node of a tree referred to by a parent node. See the figure at tree. Every node, except the root, is the child of some parent.
Author: PEB
Chinese postman problem
(classic problem)
Definition:
Find a minimum length closed walk that traverses each edge at least once. Finding an optimal solution in a graph with both directed and undirected edges is NP-complete.
Note:
This is similar to finding the most efficient way to route garbage trucks, school buses, etc. A good algorithm is given in Jack Edmonds and Ellis L. Johnson, Matching, Euler Tours, and the Chinese Postman, Mathematical Programming, 5:88-124, 1973. From Algorithms and Theory of Computation Handbook, page 6-21, 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
Kwan Mei-Ko, Graphic Programming Using Odd or Even Points, Chinese Math., 1:273-277, 1962.
Historical Note
K. Mei-Ko's article referred to optimizing a postman's route, was written by a Chinese author, and appeared in a Chinese math journal. Based on this Alan J. Goldman suggested the name "Chinese Postman problem" to Jack Edmonds when Edmonds was in Goldman's Operations Research group at the U.S. National Bureau of Standards (now NIST). Edmonds appreciated its "catchiness" and adopted it. Goldman was also indirectly influenced by recalling an Ellery Queen mystery named "The Chinese Orange Mystery". (Alan J. Goldman, personal communication, 14 December 2003)
Chinese remainder theorem
(algorithm)
Definition:
An integer n can be solved uniquely mod LCM(A(i)), given modulii (n mod A(i)), A(i) > 0 for i=1..k, k > 0. In other words, given the remainders an integer gets when it's divided by an arbitrary set of divisors, you can uniquely determine the integer's remainder when it is divided by the least common multiple of those divisors.
Note:
For example, knowing the remainder of n when it's divided by 3 and the remainder when it's divided by 5 allows you to determine the remainder of n when it's divided by LCM(3,5) = 15. After LK.
Author: PEB
Christofides algorithm
(algorithm)
Definition:
(1) A heuristic algorithm to find a near-optimal solution to the traveling salesman problem. Step 1: find a minimum spanning tree T. Step 2: find a perfect matching M among vertices with odd degree. Step 3: combine the edges of M and T to make a multigraph G. Step 4: find an Euler cycle in G by skipping vertices already seen. (2) An algorithm to find the chromatic number of a graph.
Generalization (I am a kind of ...)
heuristic.
Aggregate child (... is a part of or used in me.)
minimum spanning tree, perfect matching, multigraph, Euler cycle.
Author: PEB
More information
(1) Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976. Also CMU Tech. Report CS-93-13, 1976. Also Sympos. on New Directions and Recent Results in Algorithms and Complexity, J. F. Traub ed., page 441, Academic Press, New York, NY, 1976. (2) Nicos Christofides, An algorithm for the chromatic number of a graph, Computer J., 14(1):38-39, February 1971.
chromatic index
(definition)
Definition:
The minimum number of colors needed to color the edges of a graph.
Note:
From Algorithms and Theory of Computation Handbook, page 7-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
chromatic number
(definition)
Definition:
The minimum number of colors needed to color the vertices of a graph such that no two adjacent vertices have the same color.
Note:
From Algorithms and Theory of Computation Handbook, pages 7-19 and 7-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
circuit
(definition)
Definition:
(1) An acyclic network of inputs, logic gates, and outputs. Contrasted with a Turing machine, it has no memory. (2) A cycle in a graph.
Note:
From Algorithms and Theory of Computation Handbook, page 27-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Authors: CRC-A,PEB
circuit complexity
(definition)
Definition:
The study of the size, depth, and other attributes of circuits that decide specified languages or compute specified functions.
Note:
From Algorithms and Theory of Computation Handbook, page 27-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
circuit value problem
(definition)
Definition:
Given an encoding α of a boolean circuit α, inputs x1, ... , xn and a designated output y, the problem of deciding if output y of α is true on input x1, ... , xn.
Note:
From Algorithms and Theory of Computation Handbook, pages 27-21 and 45-23, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
circular list
(data structure)
Definition:
A variant of a linked list in which the nominal tail is linked to the head. The entire list may be accessed starting at any item and following links until one comes to the starting item again.
Author: BB
circular queue
(data structure)
Definition:
An implementation of a bounded queue using an array.
Author: PEB
clique
(definition)
Definition:
A set of vertices in an undirected graph in which there is an edge between every pair of vertices. In other words, a subgraph that is complete.
Generalization (I am a kind of ...)
complete graph.
Note:
Standard pronunciation should be "cleek", to rhyme with antique, boutique, critique, oblique, physique, pique, technique, unique, etc. Definition after Lior Malka, 31 July 2003.
Author: PEB
clique problem
(classic problem)
Definition:
Find the largest clique in an undirected graph.
Author: PEB
clustering
(definition)
Definition:
The tendency for entries in a hash table using open addressing to be stored together, even when the table has ample empty space to spread them out.
Note:
In machine learning, "clustering" means to group together objects that are similar, usually to determine meaningful classes or concepts. After Keith Cassell, 29 Dec 2005. Clustering leads to inefficiency because the chances are higher that the place you want to put an item is already filled. The effect is like having a high load factor in the areas with clustering, even though the overall load factor may be quite low.
Author: PEB
clustering free
(definition)
Definition:
When a collision resolution scheme spreads out entries in a hash table.
Author: PEB
coalesced chaining
(data structure)
Definition:
A scheme in which linked lists within the hash table handle collisions. An item that collides is put in the next empty place in the array and added to the end of a list embedded in the array items. Any open addressing method to compute possible new positions may be used to find the "next" empty place.
Generalization (I am a kind of ...)
chaining, collision resolution scheme.
Aggregate parent (I am a part of or used in ...)
hash table.
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 leaves the search list intact.
Author: PEB
coarsening
(definition)
Definition:
To alter a problem, typically restricting it to a less complex feasible region or objective function, so that the resulting problem can be efficiently solved, usually by dynamic programming.
Note:
From Algorithms and Theory of Computation Handbook, page 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
codeword
(definition)
Definition:
Sequence of bits of a code corresponding to a symbol.
Note:
From Algorithms and Theory of Computation Handbook, page 12-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
coding tree
(data structure)
Definition:
A full binary tree that represents a coding, such as produced by Huffman coding. Each leaf is an encoded symbol. The path from the root to a leaf is its codeword.
Generalization (I am a kind of ...)
full binary tree, trie.
Aggregate parent (I am a part of or used in ...)
Huffman coding.
Author: PEB
Collatz problem
(classic problem)
Definition:
Consider the function: if N is odd, 3 × N + 1; else N/2. Does beginning with any positive integer and repeatedly applying the function always yields 1?
Note:
First posed by the German mathematician Lothar Collatz in 1937. Began appearing in print in the 1950's. The sequence of integers generated are called "hailstones", since they may rise and fall but (presumably) always fall to the ground (the integer 1). Also called the Syracuse problem and many other names.
Author: PEB
More information
MathWorld's Collatz problem entry.
Jeff Lagarias, The 3x+1 Problem and its Generalizations, American Mathematical Monthly, 92:3-23, 1985.
This paper gives the history of the problem, including various names, many references, and a survey of what is (was) known. The web version also has links to related sites.
collective recursion
(algorithmic technique)
Definition:
A special form of tail recursion, where the results are produced during the recursive calls and nothing is returned. The recursion may be optimized away by executing the call in the current stack frame, rather than creating a new stack frame, or by deallocating the entire recursion stack at once rather than a little at each return.
Note:
The following program prints the values greater than limit in a list. int overlimit(list l, int limit)
{
if (null == l) {
return;
}
if (limit < head(l)) {
printf("%d\n", head(l));
}
overlimit(tail(l), limit);
} At the return, the compiler can deallocate all the memory for the recursion stack at once.
Author: PEB
collision
(definition)
Definition:
When two or more items should be kept in the same location, especially in hash tables, that is, when two or more different keys hash to the same value.
Author: PEB
collision resolution scheme
(algorithm)
Definition:
A way of handling collisions, that is, when two or more items should be kept in the same location, especially in a hash table. The general ways are keeping subsequent items within the table and computing possible locations (open addressing), keeping lists for items that collide (chaining), or keeping one special overflow area.
Specialization (... is a kind of me.)
direct chaining, open addressing, separate chaining.
Aggregate parent (I am a part of or used in ...)
hash table.
Note:
The special overflow area can be any searchable data structure, even another (smaller) hash table.
Author: PEB
combination
(algorithm)
Definition:
Choose m of n elements, where m ≤ n.
Note:
A combination is a subset with exactly m elements. There are n!/(n-m)!m! combinations of n (distinguishable) elements taken m at a time. Why? To begin, there are n! permutations. Permutations that only differ in the order of the n-m elements not taken are the same combination, so divide by (n-m)!. The order of the m elements taken doesn't matter either, so divide by m!, too.
Author: PEB
comb sort
(algorithm)
Definition:
An in-place sort algorithm that repeatedly reorders different pairs of items. On each pass swap pairs of items separated by the increment or gap, if needed, and reduce the gap (divide it by about 1.3). The gap starts at about 3/4 of the number of items. Continue until the gap is 1 and a pass had no swaps.
Generalization (I am a kind of ...)
diminishing increment sort.
Note:
Bubble sort can be seen as a variant of comb sort where the gap is always 1. Since items may move large distances at first, comb sort is quite efficient. Comb sort does a single "bubbling" pass (ala bubble sort) over each set for each gap or increment, whereas Shell sort completely sorts each set. J. Incerpi and R. Sedgewick (1985) point out that bidirectional "bubbling" (ala bidirectional bubble sort) is more symmetric than the typical comb sort.
Author: PEB
More information
W. Dobosiewicz, An efficient variation of bubble sort, Information Processing letters 11(1):5-6, 1980.
Richard Box and Stephen Lacey, A fast, easy sort, Byte, 16(4):315-ff, April 1991.
Commentz-Walter
(algorithm)
Definition:
A multiple string matching algorithm that compares from the end of the pattern, like Boyer-Moore, using a finite state machine, like Aho-Corasick.
Generalization (I am a kind of ...)
string matching.
Author: PEB
More information
Beate Commentz-Walter, A string matching algorithm fast on the average in Maurer (ed.), Proc 6th International Coll. on Automata, Languages, and Programming, pages 118-132, Springer-Verlag, 1979.
Beate Commentz-Walter, A string matching algorithm fast on the average, Technical Report TR 79.09.007, IBM Germany, Heidelberg Scientific Center, 1979.
Communicating Sequential Processes
(definition)
Definition:
C. A. R. Hoare's algebraic theory to formalize the notion of concurrent computation. Commonly known as CSP.
Author: SKS
commutative
(definition)
Definition:
A function where f(A, B) = f(B, A).
Note:
Multiplication is associative, e.g., 2 × (3 × 4) = (2 × 3) × 4, and commutative, e.g., 2 × 3 = 3 × 2. Subtraction is neither associative, e.g., 2 - (3 - 4) ≠ (2 - 3) - 4, nor commutative, e.g., 2 - 3 ≠ 3 - 2. Because of rounding floating point addition on a computer is not associative, e.g., (1000000 + .00001) + .00001 ≠ 1000000 + (.00001 + .00001) (actual values depend on the details of the computer addition), but is commutative, e.g., 1000000 + .00001 = .00001 + 1000000.
Cartesian product is associative, e.g., {1, 2} × ({a, b} × {X, Y}) = ({1, 2} × {a, b}) × {X, Y}, but is not commutative, e.g., {1, 2} × {a, b} ≠ {a, b} × {1, 2}.
Author: PEB
compact DAWG
(data structure)
Definition:
A directed acyclic word graph (DAWG) representing the suffixes of a given string in which each edge is labeled with the longest possible string. The strings along a path from the root to a node are the substring which the node represents.
Note:
This is a variant of a directed acyclic word graph, or DAWG, in which a node with one child is merged with its parent and the edge labels are concatenated. A Patricia tree merges single-child nodes also, but does not combine common subtrees.
Author: PEB
More information
Andrew W. Appel and Guy J. Jacobson, The World's Fastest Scrabble Program, CACM, 31(5):572-578, May 1988. Good description of the basic DAWG.
compact trie
(data structure)
Definition:
A trie in which nonbranching subtrees leading to leaf nodes are cut off.
Generalization (I am a kind of ...)
trie.
Note:
The name comes from reTRIEval and is pronounced, "tree." See the historical note at trie.
Author: PEB
comparison sort
(definition)
Definition:
Any sort algorithm using comparisons between keys, and nothing else about the keys, to arrange items in a predetermined order. An alternative is a restricted universe sort such as counting sort or bucket sort.
Note:
From Algorithms and Theory of Computation Handbook, page 3-23, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
competitive analysis
(definition)
Definition:
An analysis in which the performance of an on-line algorithm is compared to the best that could have been achieved if all the inputs had been known in advance.
Note:
From Algorithms and Theory of Computation Handbook, page 10-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
competitive ratio
(definition)
Definition:
The worst case of the ratio between the cost incurred by an on-line algorithm and the best-case cost.
Note:
From Algorithms and Theory of Computation Handbook, page 10-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
complement
(definition)
Definition:
(1) Of a boolean, 0 if 1, or 1 if 0. See not. (2) Of a set A, a set having all the members which are in the universe, but not in A.
Note:
The complement can be seen as the difference of a set and the universe, or the universal set. That is, A' = U - A. If the universe is {1, 2, 3, 4}, then the complement of {1, 2} is {3, 4}, and the complement of {3} is {1, 2, 4}.
Author: PEB
complete binary tree
(data structure)
Definition:
A binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.
Generalization (I am a kind of ...)
complete tree, binary tree.
Specialization (... is a kind of me.)
binary heap.
Note:
A complete binary tree has 2k nodes at every depth k < n and between 2n and 2n+1-1 nodes altogether. It can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2, with one-based indexing. If child index is greater than the number of nodes, the child does not exist.
After LK. Thanks to Adrienne G. Bloss (bloss@roanoke.edu) September 2003. This kind of tree is called "complete" by authors that mention it (Budd page 332, Ege, Carrano & Prichard page 427, Goodrich & Tamassia page 302, [HS83, page 226], [Knuth97], [Stand98, page 249]). Some authors call perfect binary trees "complete".
Author: PEB
complete graph
(definition)
Definition:
An undirected graph with an edge between every pair of vertices.
Generalization (I am a kind of ...)
undirected graph, dense graph, connected graph.
Specialization (... is a kind of me.)
clique.
Note:
A complete graph has n(n-1)/2 edges, where n is the number of vertices.
Author: PEB
completely connected graph
(definition)
Definition:
See either connected graph or complete graph.
Author: PEB
complete tree
(data structure)
Definition:
A tree in which all leaf nodes are at some depth n or n-1, and all leaves at depth n are toward the left.
Author: PEB
complexity
(definition)
Definition:
The intrinsic minimum amount of resources, for instance, memory, time, messages, etc., needed to solve a problem or execute an algorithm.
Note:
Any measure of execution must implicitly or explicitly refer to some computation model. Usually this is some notion of the limiting factor. For one problem or machine, the number of floating point multiplications may be the limiting factor, while for another, it may be the number of messages passed across a network. Other measures that may be important are compares, item moves, disk accesses, memory used, or elapsed ("wall clock") time.
Author: PEB
complexity class
(definition)
Definition:
Any of a set of computational problems with the same bounds (Θ(n)) on time and space, for deterministic and nondeterministic machines.
Specialization (... is a kind of me.)
P, NP, NP-complete, NP-hard, BPP, canonical complexity class.
Aggregate child (... is a part of or used in me.)
Turing machine.
Note:
From Algorithms and Theory of Computation Handbook, page 27-2, 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
Scott Aaronson's Complexity Zoo
computable
(definition)
Definition:
A function that can be computed by an algorithm --- equivalently, by a Turing machine.
Note:
From Algorithms and Theory of Computation Handbook, page 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
concurrent flow
(definition)
Definition:
A multi-commodity flow in which the same fraction of the demand of each commodity is satisfied.
Note:
From Algorithms and Theory of Computation Handbook, page 7-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
concurrent read, concurrent write
(definition)
Definition:
A parallel memory model in which multiple processors can read simultaneously from a single memory location, and multiple processors can write simultaneously to a single memory location.
Also known as CRCW.
Author: PMS
concurrent read, exclusive write
(definition)
Definition:
A parallel memory model in which multiple processors can read simultaneously from a single memory location, but only one processor can write to any one memory location at one time.
Also known as CREW.
Author: PMS
confluently persistent data structure
(definition)
Definition:
A fully persistent data structure that allows meld or merge operations to combine two different versions.
Author: PEB
More information
James R. Driscoll, Daniel D. Sleator, and Robert E. Tarjan, Fully Persistent Lists with Catenation, Journal of the ACM, 41(5):943-949, 1994.
conjunction
(definition)
Definition:
The boolean and function.
Author: PEB
connected components
(definition)
Definition:
The set of maximally connected components of an undirected graph.
Generalization (I am a kind of ...)
partition.
Note:
If a graph is connected, it has only one connected component. Often the term "component" is used, with the "connected" property understood.
Let G=(V, E) be a graph and G1=(V1, E1)..., Gm=(Vm, Em) be its connected components. Every vertex is in exactly in one connected component, that is, the components partition(1) V. Formally, for all i ≠ j, Vi∩ Vj=ø. Further, V=V1∪...∪ Vm and E=E1∪...∪ Em.
Author: AL
connected graph
(definition)
Definition:
An undirected graph that has a path between every pair of vertices.
Note:
After LK.
Author: PEB
constant function
(definition)
Definition:
A function that always gives the same value.
Note:
A 0-ary or nullary function that is pure (no state or interactions with external variables) must be a constant function.
Author: PEB
Cook reduction
(definition)
Definition:
A reduction computed by a deterministic polynomial time oracle Turing machine.
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
Cook's theorem
(definition)
Definition:
The language SAT of satisfiable Boolean formulas is NP-complete.
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
CORDIC
(algorithm)
Definition:
Compute trigonometric functions by iterative complex rotations. The advantage is that all computations can be done with addition, subtraction, and binary shifts.
Author: PEB
More information
The Internet Archive Wayback Machine copy of Shaoyun's CORDIC Bibliography Site at U. Texas in the late 1990's. It include Peter Knoppers' implementation in C.
Jack E. Volder, The CORDIC trigonometric computing technique, IRE Trans. Electron. Comput., EC-8, 3:330-334, September 1959.
Available in Earl E. Swartzlander, Jr., Computer Arithmetic, IEEE Computer Society Press, 1990.
counting sort
(algorithm)
Definition:
A 2-pass sort algorithm that is efficient when the range of keys is small and there many duplicate keys. The first pass counts the occurrences of each key in an auxiliary array, and then makes a running total so each auxiliary entry is the number of preceding keys. The second pass puts each item in its final place according to the auxiliary entry for that key.
Generalization (I am a kind of ...)
histogram sort.
Note:
A bucket sort uses fixed-size buckets. A histogram sort sets up buckets of exactly the right size in a first pass. A counting sort is a histogram sort with one bucket per possible key value. A pigeonhole sort is a counting sort that moves items to the auxiliary array instead of counting them.
Author: ASK
covering
(definition)
Definition:
Given a finite collection of subsets of a finite ground set, to find an optimal subcollection whose union covers the ground set.
Note:
From Algorithms and Theory of Computation Handbook, page 32-39, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
critical path problem
(classic problem)
Definition:
Find the longest path from any source to any sinks in a directed acyclic graph which has weights, or numeric values, on vertices.
Note:
This can be solved with a variant of the DAG shortest paths algorithm by assigning an initial distance of negative infinity (-∞), updating the distance and predecessor if dist(v) + weight(u) > dist(u), and recording the greatest distance found so far.
Author: PEB
CSP
(definition)
Definition:
C. A. R. Hoare's algebraic theory to formalize the notion of concurrent computation. An acronym for Communicating Sequential Processes.
Author: SKS
CTL
(definition)
Definition:
A propositional, branching-time temporal logic for which formulas can be checked in linear time. An acronym for Computation Tree Logic.
Note:
CTL differs from CTL* in that in CTL path quantifiers (E and A) always appear with temporal operators (F, G, X, U, etc.). Therefore CTL formulas are state formulas.
Author: PEB
cube root
(algorithm)
Definition:
This describes a "long hand" or manual method of calculating or extracting cube roots. Calculation of a cube root by hand is a little like long-hand division or manual square root.
Suppose you need to find the cube root of 55,742,968. Set up a "division" with the number under the radical. Mark off triples of digits, starting from the decimal point. (The decimal point is a period (.), and a comma (,) marks triples of digits.) ____________
\/ 55,742,968.
Look at the leftmost digit(s) (55 in this case). What is the largest number whose cube is less than or equal to it? It is 3, whose cube is 27. Write 3 above, write the cube below and subtract. __3_________
\/ 55,742,968.
-27
----
28
Now bring down the next three digits (742). __3_________
\/ 55,742,968.
-27
----
28742
Coming up with the next "divisor" is more involved than for square roots. First bring down 3 times the square of the number on top (3 × 3²=27) leaving room for two more digits (27_ _).
__3_________
\/ 55,742,968.
-27
----
27_ _) 28742
What is the largest number that we can put in the next position and multiply times the divisor and still be less than or equal to what we have? (Algebraically, what is d such that d × 2700 ≤ 28742?) 10 might work (since 10 × 2700 = 27000), but we can only use a single digit, so we'll try 9. __3___9_____
\/ 55,742,968.
-27
----
27_ _) 28742
The second step in making the divisor is adding 3 times the previous number on top (3) times the last digit (9) times 10 (3 × 3 × 9 = 81 × 10 = 810) and the square of the last digit (9² = 81). 2700
810
+ 81
-----
3591
Our new divisor is 3591. __3___9_____
\/ 55,742,968.
-27
----
3591) 28742
Multiply by the last digit (9 × 3591 = 32319) and subtract. But that is too big! So we'll try 8 as the next digit instead. __3___8_____
\/ 55,742,968.
-27
----
27_ _) 28742
We repeat the second step of adding 3 times the previous number on top (3) times the last digit (8) times 10 (3 × 3 × 8 = 72 × 10 = 720) and the square of the last digit (8² = 64). 2700
720
+ 64
-----
3484
Our new divisor is 3484. __3___8_____
\/ 55,742,968.
-27
----
3484) 28742
Now multiply by the last digit (8 × 3484 = 27872) and subtract. __3___8_____
\/ 55,742,968.
-27
----
3484) 28742
-27872
------
870
We are ready to start over on the next digit. Bring down the next three digits. The divisor starts as 3 times the square of the number on top (3 × 38²=4332) leaving room for two more digits (4332_ _). __3___8_____
\/ 55,742,968.
-27
----
3484) 28742
-27872
------
4332_ _) 870968
It looks like 2 is the next digit. __3___8___2_
\/ 55,742,968.
-27
----
3484) 28742
-27872
------
4332_ _) 870968
Add 3 times the previous number on top (38) times the last digit (2) times 10 (3 × 38 × 2 = 228 × 10 = 2280) and the square of the last digit (2² = 4). 433200
2280
+ 4
-------
435484
Our new divisor is 435484. __3___8___2_
\/ 55,742,968.
-27
----
3484) 28742
-27872
------
435484 ) 870968
Now multiply by the last digit (2 × 435484 = 870968) and subtract. __3___8___2_
\/ 55,742,968.
-27
----
3484) 28742
-27872
------
435484 ) 870968
-870968
-------
0
So the cube root of 55742968 is 382. You can continue to get as many decimal places as you need: just bring down more triples of zeros. Why does this work? Consider (10A + B)³ = 1000A³ + 3 × 100A²B + 3 × 10AB² + B³ and think about finding the volume of a cube. The volume of the three thin plates is 3 × 100A²B. The volume of the three skinny sticks is 3 × 10AB². The tiny cube is B³. If we know A and the volume of the cube, S, what B should we choose? We previously subtracted A³ from S. To scale to 1000A³, we bring down three more digits (a factor of 1000) of the length of S. We write down 3 times A squared (3A²), but shifted two places (100 × 3A² or 3 × 100A²). We estimate B. We add 30 times A times B (30 × AB or 3 × 10AB) and B squared. Multiplying that by B gives us 3 × 100A²B + 3 × 10AB² + B³. When we subtract that from the remainder (remember we already subtracted A³), we have subtracted exactly (10A + B)³. That is, we have improved our knowledge of the cube root by one digit, B. We take whatever remains, scale again by 1000, by bringing down three more digits, and repeat the process.
Note:
In computers and hand-held calculators, square root, sine, cosine, and other transcendental functions are calculated with sophisticated functions, such as Taylor series, CORDIC, or Newton-Raphson method, sometimes called Newton's method. This lesson explains, for instance, possible difficulties in convergence.
Author: PEB
cuckoo hashing
(data structure)
Definition:
A dictionary implemented with two hash tables, T1 and T2, and two different hash functions, h1 and h2. Each key, k, is either in T1[h1(k)] or T2[h2(k)]. A new key, k, is stored in T1[h1(k)]. If that location is already occupied by another key, l, the other key is moved to T2[h2(l)]. Keys are moved back and forth until a key moves to an empty location or a limit is reached. If the limit is reached, new hash functions are chosen, and the tables are rehashed. For tables that are a bit less than half full and with carefully chosen universal hashing functions, performance is good. A key is deleted by removing it from a table.
Generalization (I am a kind of ...)
hash table.
Aggregate parent (I am a part of or used in ...)
dictionary.
Aggregate child (... is a part of or used in me.)
array, hash function.
Note:
The name comes from the European cuckoo, whose young pushes other, competing eggs out of the nest.
Author: PEB
More information
Rasmus Pagh and Flemming Friche Rodler, Cuckoo Hashing, Proceedings of ESA 2001, Lecture Notes in Computer Science, vol. 2161, pages 121-?, 2001.
Generalized in Úlfar Erlingsson, Mark Manasse, and Frank McSherry, A cool and practical alternative to traditional hash tables, proc 7th Workshop on Distributed Data and Structures (WDAS'06), Santa Clara, CA, January 2006.
cut
(definition)
Definition:
A nonempty, proper subset of vertices of a graph.
Note:
After [Leda98].
Author: PEB
cutting plane
(definition)
Definition:
A valid inequality for an integer polyhedron that separates the polyhedron from a given point outside it.
Note:
From Algorithms and Theory of Computation Handbook, page 32-39, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
cutting stock problem
(classic problem)
Definition:
Find the best arrangement of shapes on rectangles to minimize waste or the number of rectangles. This is a two-dimensional variant of the bin packing problem. It is NP-complete.
Specialization (... is a kind of me.)
strip packing is a one-dimensional variant.
Note:
This problem arises often in manufacturing. For instance, deciding how to cut pieces for pants from cloth or shapes from sheet metal.
Author: PEB
cutting theorem
(definition)
Definition:
For any set H of n hyperplanes in Rk, and any parameter r, 1 ≤ r≤ n, there always exists a (1/r)-cutting of size O(rk). In two dimensions, a (1/r)-cutting of size s is a partition of the plane into s disjoint triangles, some of which are unbounded, such that no triangle in the partition intersects more than n/r lines in H. In Rk, triangles are replaced by simplices. Such a cutting can be computed in O(nrk-1) time.
Note:
From Algorithms and Theory of Computation Handbook, page 20-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
cut vertex
(definition)
Definition:
A vertex whose deletion along with incident edges results in a graph with more components than the original graph.
Also known as articulation point.
Note:
After Algorithms and Theory of Computation Handbook, page 6-6, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC. With input from Paul Tanenbaum <pjt@arl.army.mil> (3 Sept 2002).
Author: CRC-A
cycle
(definition)
Definition:
A path that starts and ends at the same vertex and includes at least one edge.
Generalization (I am a kind of ...)
(nonsimple) path.
Specialization (... is a kind of me.)
Hamiltonian cycle, Euler cycle.
Aggregate parent (I am a part of or used in ...)
graph.
Note:
Also known as "circuit" or "closed path". A cycle is usually assumed to be a simple path ignoring the start (and end) vertex. That is, it include vertices other than the start/end at most once.
Having at least one edge means that there are at least two vertices in the path: the start/end and one other. It also means the path length is at least one. One way to find a cycle is to do a depth-first search, checking for repeated vertices. One step in finding all cycles is to look for strongly connected components.
Author: PEB
cyclic redundancy check
(algorithm)
Definition:
(1) A method to detect and correct errors by adding bits derived from a block or string of bits to the block. (2) An algorithm to compute bits characteristic of a block based on the algebra of polynomials over the integers, modulo 2. (3) The characteristic bits of a block.
Also known as CRC.
Note:
Large blocks may be probabilistically compared by precalculating the CRC for each block, then comparing their CRCs. If the CRCs are different, the blocks are different. If the CRCs match, there is a small chance that the blocks are actually different. This probability may be made arbitrarily smaller with more CRC bits. Many transmission errors may be detected, and some corrected, by recalculating the CRC and comparing it with the transmitted CRC. Contributed by Arvind <uk_arvind@mail.utexas.edu> May 2002.
Author: PEB
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
|
