Algorithms and Data Structures Glossary (Starting with "L")
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
L
 labeled graph
 language
 lastin, firstout
 Las Vegas algorithm
 lattice
 layered graph
 LCM: see least common multiple
 LCS
 leaf
 least common multiple
 leftist tree
 left rotation
 LempelZivWelch
 levelorder traversal
 Levenshtein distance
 lexicographical order
 LIFO: see stack
 linear
 linear congruential generator
 linear hash
 linear hashing
 linear insertion sort: see insertion sort
 linear order: see total order
 linear probing
 linear probing sort
 linear product
 linear program
 linear quadtree
 linear search
 link
 linked list
 list
 list contraction
 littleo notation
 L_{m} distance
 load factor
 local alignment
 localitysensitive hashing
 local optimum
 logarithmic
 longest common subsequence
 longest common substring
 Lotka's law
 lower bound
 lower triangular matrix
 lowest common ancestor
 lreduction
 lucky sort
 LZW compression: see LempelZivWelch
labeled graph
(definition)
Definition:
A graph which has labels associated with each edge or each vertex.
Note:
Adapted from [Wier98, page 466].
Author: PEB
language
(definition)
Definition:
A set of strings over some fixed alphabet. A characterization of inputs which may or may not be solved by algorithms.
Also known as formal language.
Note:
From Algorithms and Theory of Computation Handbook, page 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
lastin, firstout
(definition)
Definition:
A policy that the most recently arrived item is processed first. A stack implements this.
Note:
A depthfirst search checks newly encountered nodes lastin, firstout.
Author: PEB
Las Vegas algorithm
(algorithmic technique)
Definition:
A randomized algorithm that always produces correct results, with the only variation from one run to another being its running time.
Specialization (... is a kind of me.)
random searchGrover's algorithm, Czech, Havas, and Majewski's orderpreserving minimal perfect hashing.
Note:
From Algorithms and Theory of Computation Handbook, 1521, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC. A Monte Carlo algorithm gives more precise results the longer you run it. A Las Vegas algorithm always gives the right answer, but the run time is indeterminate.
Author: CRCA
lattice
(definition)
Definition:
A point lattice generated by taking integer linear combinations of a set of basis vectors.
Note:
From Algorithms and Theory of Computation Handbook, page 3239, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
layered graph
(definition)
Definition:
A connected graph where "layers" L_{0} ... L_{k} partition the vertices. Each edge, which has a nonnegative integral weight, connects only vertices in successive layers. The width is the greatest number of vertices in any layer, i.e., MAX_{i=0}^{k} L_{i}.
Generalization (I am a kind of ...)
connected graph.
Specialization (... is a kind of me.)
bipartite graph.
Note:
A bipartite graph is a layered graph with two layers. A. Fiat, D.P. Foster, H.J. Karloff, Y. Rabani, Y. Ravid, and S. Vishwanathan. Competitive Algorithms for Layered Graph Traversal. SIAM J. Comput., to appear. Preliminary version appeared in FOCS '91. Contributed by Giovanni Fiaschi <Giovanni.Fiaschi@marconi.com> June 2000.
Author: PEB
LCS
(classic problem)
Definition:
Either longest common subsequence or longest common substring.
Note:
The longest common substring is contiguous, while the longest common subsequence need not be.
Author: PEB
leaf
(definition)
Definition:
A node in a tree without any children.
Also known as external node, terminal node.
Aggregate parent (I am a part of or used in ...)
tree.
Note:
Every node in a tree is either a leaf or an internal node. The root may be a leaf.
Author: PEB
least common multiple
(definition)
Definition:
The least integer which is a multiple of given integers. For instance, LCM(6, 10) = 30.
Also known as LCM.
Author: PEB
leftist tree
(data structure)
Definition:
A priority queue implemented with a variant of a binary tree. Every node has a count which is the distance to the nearest leaf. In addition to the heap property, leftist trees are kept so the right descendant of each node has the shorter distance to a leaf.
Generalization (I am a kind of ...)
priority queue.
Aggregate child (... is a part of or used in me.)
binary tree, heap property.
Note:
These are called "leftist" because the left subtrees are usually taller than the right subtrees.
Author: PEB
left rotation
(algorithm)
Definition:
(1) In a binary search tree, pushing a node N down and to the left to balance the tree. N's right child replaces N, and the right child's left child becomes N's right child. (2) In an array, moving all items to the next lower location. The first item is moved to the last location, which is now vacant. (3) In a list, removing the head and inserting it at the tail.
Also known as rotate left.
Note:
Also known as left single rotation, in contrast to double left rotation.
Author: BB
LempelZivWelch
(algorithm)
Definition:
A compression algorithm that codes strings of characters with codes of a fixed number of bits. Every new string in the input is added to a table until it is full. The codes of existing strings are output instead of the strings.
Also known as LZW compression.
Author: GS
More information
J. Ziv and A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, May 1977. Terry Welch, A Technique for HighPerformance Data Compression, Computer, June 1984.
levelorder traversal
(algorithm)
Definition:
Process all nodes of a tree by depth: first the root, then the children of the root, etc. Equivalent to a breadthfirst search from the root.
Note:
For instance, if the "processing" is just printing, a tree is printed as "root, all children of the root, all grandchildren (children of children) of the root, etc." Here is pseudocode for an inefficient levelorder traversal of a binary tree:
levelorderAux(tree, level) begin if tree is null, return;
if level is 1, then print(tree.root); else if level greater than 1, then levelorderAux(tree.left_subtree, level1); levelorderAux(tree.right_subtree, level1); endif end levelorder(tree) begin for d = 1 to height(tree) levelorderAux(tree, d); endfor end See [Stand98, p. 251].
Author: PEB
Levenshtein distance
(definition)
Definition:
(1) The smallest number of insertions, deletions, and substitutions required to change one string or tree into another. (2) A Θ(m × n) algorithm to compute the distance between strings, where m and n are the lengths of the strings.
Also known as edit distance.
Generalization (I am a kind of ...)
string matching with errors.
Aggregate child (... is a part of or used in me.)
edit operation.
Note:
(1) From Algorithms and Theory of Computation Handbook, page 1435, 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
Wikipedia entry which has links to implementations. March 2003 pictures of Levenshtein at a reception.
Vladimir I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Doklady Akademii Nauk SSSR, 163(4):845848, 1965 (Russian). English translation in Soviet Physics Doklady, 10(8):707710, 1966. (Doklady is Russian for "Report". Sometimes transliterated in English as Doclady or Dokladi.)
lexicographical order
(definition)
Definition:
Alphabetical or "dictionary" order.
Note:
For instance, ordering cities by name rather than, say, by country or population (attributes of the named entity). The exact order, for example AZaz vs. aAzZ etc., depends on the locale and application.
Author: PEB
linear
(definition)
Definition:
(1) Any function which is a constant times the argument plus a constant: f(x)=c_{1}x + c_{0}. (2) In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by a linear function of the problem size, n. More formally m(n) = O(n).
Note:
Strictly speaking, a linear function is polynomial with the highest exponent being 1. However polynomial usually means exponents greater than 1.
Author: PEB
linear congruential generator
(algorithm)
Definition:
A class of algorithms that are pseudorandom number generators. The next number is generated from the current one by r_{n+1} = (A × r_{n} + B)mod M, where A and M are relatively prime numbers.
Note:
When implemented in software, A and B may be chosen so as to have integer overflow on nearly every step, and therefore have a less predictable sequence and avoid the mod operation. The loworder bits tend to be less random than highorder bits. This is improved by discarding some of the loworder bits. Therefore, the range of random numbers is less than the range of the integer used in the computation. Better algorithms are available, but they are more complex.
Author: BB
More information
Karl Entacher's thorough review and comparison of many linear congruential generators.
linear hash
(algorithm)
Definition:
A numeric function that maintains the order of input keys while changing their spacing.
Formal Definition: A hash function f for keys in S such that k1, k2 ∈ S ∧ k1 > k2 → f(k1) > f(k2).
Also known as orderpreserving hash.
Generalization (I am a kind of ...)
hash function.
Specialization (... is a kind of me.)
orderpreserving minimal perfect hashing.
Aggregate parent (I am a part of or used in ...)
grid file, hash heap.
Author: PEB
linear hashing
(data structure)
Definition:
A dynamic hashing table that grows one slot at a time. It has a family of hash functions, h_{i}, where the range of h_{i+1} is twice the range of h_{i}. Slots below a pointer, p, have been split. That is, key, k, is in slot h_{i}(k) if h_{i}(k) > p. Otherwise it is in h_{i+1}(k). To maintain the load factor, slot p can be split (rehashed with h_{i+1}) and p incremented. When p reaches the end, the ranges are doubled (i is incremented), and p starts over.
Also known as incremental hashing.
Generalization (I am a kind of ...)
dynamic hashing.
Note:
This is called incremental hashing in P. J. Plauger, "Hash It", ("STATE OF THE ART" column) Embedded Systems Programming, September 1998, 117120. The article has a nearly complete implementation in C++. Stefan Edelkamp uses "incremental hashing" to mean a hash function where subsequent characters are independent.
Author: PEB
More information
W. Litwin, Linear hashing: A new tool for file and table addressing, Proc. 6th Conference on Very Large Databases, pages 212223, 1980. PerÅke Larson, Dynamic Hash Tables, CACM 31(4):446457, April 1988.
linear probing
(data structure)
Definition:
A hash table in which a collision is resolved by putting the item in the next empty place in the array following the occupied place. Even with a moderate load factor, primary clustering tends to slow retrieval.
Aggregate parent (I am a part of or used in ...)
linear probing sort.
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 still intact.
Author: PEB
linear probing sort
(algorithm)
Definition:
Distribute each of n elements to one of m locations in an array (m>n) based on an interpolation of the element's key. In case of collisions, put the element in the next empty location. The array has extra space at the end for overflow. The second pass packs the elements back into an array of size n.
Generalization (I am a kind of ...)
distribution sort.
Aggregate child (... is a part of or used in me.)
linear probing.
Note:
The sort may fail if the overflow is exceeded. The distribution phase may be seen as putting the elements in a linear probing hash table using the interpolation function as the hash function.
Author: PEB
linear product
(definition)
Definition:
For two vectors X and Y, and with respect to two suitable operations and is a vector Z=Z_{0} Z_{1} ... Z_{m+n} where Z_{k}=_{i+j=k}X_{i} Y_{j} (k=0, ... , m+n).
Note:
From Algorithms and Theory of Computation Handbook, page 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
linear program
(definition)
Definition:
A problem expressible in the following form. Given an n × m real matrix A, mvector b and nvector c, determine min_{x}{c· x  Ax ≥ b and x ≥ 0} where x ranges over all nvectors and the inequalities are interpreted componentwise, i.e., x ≥ 0 means that the entries of x are nonnegative.
Note:
From Algorithms and Theory of Computation Handbook, page 3418 (also pages 3133 and 3239), 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
Programación Lineal, a site in Spanish about linear programming.
linear quadtree
(data structure)
Definition:
A quadtree implemented as a single array of nodes.
Generalization (I am a kind of ...)
quadtree.
Author: PEB
linear search
(algorithm)
Definition:
Search an array or list by checking items one at a time.
Also known as sequential search.
Generalization (I am a kind of ...)
search.
Specialization (... is a kind of me.)
transpose sequential search.
Aggregate child (... is a part of or used in me.)
movetofront heuristic.
Note:
Average run time is Θ (n/2) when the item is found.
Author: PEB
link
(definition)
Definition:
A reference, pointer, or access handle to another part of the data structure. Often, a memory address.
Author: PEB
linked list
(data structure)
Definition:
A list implemented by each item having a link to the next item.
Also known as singly linked list.
Specialization (... is a kind of me.)
doubly linked list, ordered linked list, circular list.
Note:
The first item, or head, is accessed from a fixed location, called a "head pointer." An ordinary linked list must be searched with a linear search. Average search time may be improved using a movetofront heuristic or keeping it an ordered linked list. An external index, such as a hash table, inverted index, or auxiliary search tree may be used as a "cross index" to help find items quickly. A linked list can be used to implement other data structures, such as a queue, a stack, or a sparse matrix.
Author: PEB
More information
an introduction, a Java applet animation (Java).
list
(data structure)
Definition:
A collection of items accessible one after another beginning at the head and ending at the tail.
Generalization (I am a kind of ...)
bag.
Specialization (... is a kind of me.)
linked list, doubly linked list, circular list, selforganizing list, ordered linked list.
Aggregate parent (I am a part of or used in ...)
orthogonal lists.
Note:
A list may have additional access methods. A list may be ordered. A list can be seen as an ordered bag. A list may be kept as the leading items of an array, but inserting items other than at the end takes time.
Author: PEB
list contraction
(definition)
Definition:
Contracting a list by removing some of the items.
Note:
From Algorithms and Theory of Computation Handbook, page 4739, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
littleo notation
(definition)
Definition:
A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = o(g(n)) means f(n) becomes insignificant relative to g(n) as n approaches infinity. The notation is read, "f of n is little oh of g of n".
Formal Definition: f(n) = o(g(n)) means for all c > 0 there exists some k > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ k. The value of k must not depend on n, but may depend on c.
Generalization (I am a kind of ...)
bigO notation.
Note:
As an example, 3n + 4 is o(n²) since for any c we can choose k > (3+ √(9+16c))/2c. 3n + 4 is not o(n). o(f(n)) is an upper bound, but is not an asymptotically tight bound.
Strictly, the character is the lowercase Greek letter omicron.
Author: PEB
More information
Little o is a Landau Symbol.
L_{m} distance
(definition)
Definition:
The generalized distance between two points. In a plane with point p_{1} at (x_{1}, y_{1}) and p_{2} at (x_{2}, y_{2}), it is (x_{1}  x_{2}^{m} + y_{1}  y_{2}^{m})^{1/m}.
Also known as Minkowski distance.
Note:
This is easily generalized to higher dimensions. Euclidean distance is L_{2} distance. Rectilinear, Manhattan or Hamming distance is L_{1} distance. L_{∞} distance is max(x_{1}  x_{2}, y_{1}  y_{2}). Adapted from [CLR90, page 912].
Author: PEB
More information
More formal definitions of distance measures. Wikipedia definition of distance in the mathematical or physical sense.
load factor
(definition)
Definition:
The number of elements in a hash table divided by the number of slots. Usually written α (alpha).
Note:
The higher the load factor, the slower the retrieval. With open addressing, the load factor cannot exceed 1. With chaining, the load factor often exceeds 1. After [CLR90, page 224].
Author: PEB
local alignment
(definition)
Definition:
The detection of local similarities among two or more strings.
Note:
From Algorithms and Theory of Computation Handbook, page 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
localitysensitive hashing
(algorithm)
Definition:
A probabilistic algorithm to quickly find points in a high dimensional space near a query point. Preprocessing: put every point in multiple hash tables. Each table has its own localitysensitive hash function and uses buckets (or chaining) since many collisions are expected. The hash functions come from a family of functions. Finding: look up the query point in each hash table, and compute the distance from the query point of every point in the bucket.
Generalization (I am a kind of ...)
point access method.
Aggregate child (... is a part of or used in me.)
hash function, bucket.
Note:
This algorithm is for high dimensional spaces. For instance, a 1000 x 1000 image can be characterized by a vector in 1,000,000dimensional space, one dimension for each pixel. To understand the algorithm, let the "hash functions" be random sets of the coordinates. If many coordinates of a point match the query point, it is likely to be close to the query point, at least closer than those that don't match.
Author: PEB
More information
Alexandr Andoni's LocalitySensitive Hashing home page. Locality sensitive hashing in Wikipedia.
Alexandr Andoni and Piotr Indyk, NearOptimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions, CACM, 51(1):117122, January 2008.
local optimum
(definition)
Definition:
A solution to a problem that is better than all other solutions that are slightly different, but worse than the global optimum.
Note:
Some search methods may get trapped in a local optimum and miss the global optimum.
Author: PEB
logarithmic
(definition)
Definition:
(1) Any function that is a constant times the logarithm of the argument: f(x)=c log x. (2) In complexity theory, when the measure of computation, m(n) (usually execution time or memory space), is bounded by a logarithmic function of the problem size, n. More formally m(n) = O(log n). (3) Sometimes imprecisely used to mean polylogarithmic.
Generalization (I am a kind of ...)
sublinear time algorithm.
Author: PEB
longest common subsequence
(classic problem)
Definition:
The problem of finding a maximum length (or maximum weight) subsequence of two or more strings.
Also known as heaviest common subsequence.
Note:
The longest common substring is contiguous, while the longest common subsequence need not be. From Algorithms and Theory of Computation Handbook, page 1317, 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
Dan Hirschberg's pseudocode as an example of dynamic programming. Longestcommon subsequence problem in Wikipedia.
longest common substring
(classic problem)
Definition:
Find the longest substring of two or more strings.
Note:
The longest common substring is contiguous, while the longest common subsequence need not be.
Author: PEB
More information
Dan Hirschberg's pseudocode as an example of dynamic programming.
Lotka's law
(definition)
Definition:
The number of authors making n contributions is about 1/n^{a} of those making one contribution, where a is often nearly 2.
Note:
A power law; often nearly an inverse square law. Contributed by Christiane Fritze <h0444who@rz.huberlin.de> July 2000.
Author: PEB
More information
A short biography of Alfred James Lotka.
Alfred J. Lotka, The Frequency Distribution of Scientific Productivity, Journal of the Washington Academy of Sciences, 16(12):317323, 1926.
lower bound
(definition)
Definition:
A function or growth rate below which solving a problem is impossible.
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
lower triangular matrix
(data structure)
Definition:
A matrix that is only defined at (i,j) when i ≥ j.
Generalization (I am a kind of ...)
matrix.
Specialization (... is a kind of me.)
strictly lower triangular matrix.
Note:
For example It may be more compactly represented in an array by storing entry (i,j) in location i(i1)/2 + j (onebased indexing).
Author: PEB
lowest common ancestor
(definition)
Definition:
The deepest node in a tree that is an ancestor of two given leaves.
Note:
From Algorithms and Theory of Computation Handbook, page 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
lreduction
(definition)
Definition:
A Karp reduction that preserves approximation properties of optimization problems.
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
lucky sort
(algorithm)
Definition:
The best possible sort algorithm: it is so lucky that the input is already sorted, and it need do nothing!
Note:
Defined more for humorous, rather than serious, purposes. Time complexity is Θ(0) (zero): it takes no time.
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
