Algorithms and Data Structures Glossary (Starting with "I")
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
I
 ideal merge
 ideal random shuffle
 implication
 implies
 inclusionexclusion principle
 inclusive or: see or
 incompressible string
 incremental hashing: see linear hashing
 indegree
 independent set
 index file
 information theoretic bound
 inorder traversal
 inplace sort
 insertion sort
 integer linear program
 integer multicommodity flow
 integer polyhedron
 interactive proof system
 interiorbased representation
 internal node
 internal sort
 interpolation search
 interpolationsequential search
 interpolation sort: see histogram sort
 intersection
 interval tree
 intractable
 introsort: see introspective sort
 introspective sort
 inverse Ackermann function
 inverse suffix array
 inverted file index
 inverted index
 irreflexive
 isomorphic
 iteration
ideal merge
(algorithm)
Definition:Merge n sorted streams into one output stream. To begin the streams are sorted by the value of the head element of each. Then the head of the first stream, which is the least since the streams were sorted, is removed and written to the output. That stream is inserted back into the list of streams according to its new head. Taking the head of the first stream and reinserting that stream is repeated until all elements have been processed. Using linear search to insert a stream into the list, the execution time is Θ(M N) where M is the total number of elements. Keeping the streams in a heap, the execution time is Θ(M log N).
Note:
Ideal merge was first mentioned by Art S. Kagel as part of the implementation of the UnShuffle sort.
Author: ASK
ideal random shuffle
(algorithm)
Definition:
A permutation algorithm, or shuffle, that has exactly the same chance of producing any permutation.
Generalization (I am a kind of ...)
randomized algorithm.
Specialization (... is a kind of me.)
FisherYates shuffle.
Note:
Attaching random tags then sorting (see permutation) may not work: if tags may be duplicated, a deterministic sort will not randomly switch the order of elements with duplicate tags.
Author: PEB
More information
Historical Note
Formerly called "perfect shuffle". Renamed in January 2009 when Dave Bayer pointed out that the term is almost universally used to mean dividing a list of elements (or deck of cards) exactly in half then precisely interleaving the two halves. This has been the use of "perfect shuffle" for decades.
implication
(definition)
Definition:
The boolean implies function.
Author: PEB
implies
(definition)
Definition:
Implication: 0 → 0 = 1, 0 → 1 = 1, 1 → 0 = 0, 1 → 1 = 1.
Author: PEB
inclusionexclusion principle
(definition)
Definition:
A rule that allows to compute the probability of exactly r occurrences of events A_{1}, A_{2}, ... , A_{n}.
Note:
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
incompressible string
(definition)
Definition:
A string whose Kolmogorov complexity equals its length, so that it has no shorter encodings.
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
indegree
(definition)
Definition:
The number of edges coming into a vertex in a directed graph.
Author: PEB
independent set
(definition)
Definition:
A set of vertices in a graph such that for any pair of vertices, there is no edge between them.
Author: SKS
index file
(data structure)
Definition:
A file which stores keys and an index into another file. The index file may have additional structure, e.g., be a Btree.
Note:
An index file is helpful if records are large: the keys and indexes can be extracted, sorted, and the original file accessed faster than the original file could be rearranged into sorted order. Also if the file needs to be accessed by different keys at the same time, it cannot be sorted by all of them. So a index file is maintained for each different key.
Author: PEB
information theoretic bound
(definition)
Definition: lower bounds on the execution of a computation based on the rate at which information can be accumulated.
Note:
From Algorithms and Theory of Computation Handbook, page 125, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
inorder traversal
(algorithm)
Definition:
Process all nodes of a tree by recursively processing the left subtree, then processing the root, and finally the right subtree.
Generalization (I am a kind of ...)
tree traversal, depthfirst search.
Aggregate parent (I am a part of or used in ...)
treesort (1).
Note:
For instance, if the "processing" is just printing, a tree is printed as "(left subtree) root (right subtree)." Here is pseudocode for a binary tree:
inorder(tree) begin if tree is null, return;
inorder(tree.left_subtree); print(tree.root); inorder(tree.right_subtree); end
Author: PEB
inplace sort
(algorithm)
Definition:
A sort algorithm in which the sorted items occupy the same storage as the original ones. These algorithms may use o(n) additional memory for bookkeeping, but at most a constant number of items are kept in auxiliary memory at any time.
Also known as sort in place.
Generalization (I am a kind of ...)
sort.
Specialization (... is a kind of me.)
American flag sort, quicksort, insertion sort, selection sort, Shell sort, diminishing increment sort, J sort, gnome sort.
Authors: PEB,CM
insertion sort
(algorithm)
Definition:
Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted. Run time is O(n^{2}) because of moves.
Also known as linear insertion sort.
Generalization (I am a kind of ...)
sort.
Specialization (... is a kind of me.)
binary insertion sort.
Note:
Sorting can be done in place by moving the next item into place by repeatedly swapping it with the preceding item until it is in place  a linear search and move combined. This implementation is given in C. J. Shaw and T. N. Trimble, Algorithm 175 Shuttle Sort, CACM, 6(6):312313, June 1963.
If comparing items is very expensive, use binary search to reduce the number of comparisons needed to find where the item should be inserted, then open a space by moving all later items down one. However a binary search is likely to make this not a stable sort.
Author: PEB
More information
demonstration of several sort algorithms, with particular emphasis on insertion sort; more demonstrations; a animation (Java) of insertion sort.
integer linear program
(definition)
Definition:
A linear program with additional constraints that all of the variables must take on integer values. Solving such problems is NPhard.
Note:
From Algorithms and Theory of Computation Handbook, page 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
integer multicommodity flow
(definition)
Definition:
A multicommodity flow in which the flow of each commodity through each edge must take an integer value. The term is also used to capture the multicommodity flow problem in which each demand is routed along a single path.
Note:
From Algorithms and Theory of Computation Handbook, page 721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
integer polyhedron
(definition)
Definition:
A polyhedron, all of whose extreme points are integer valued.
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
interactive proof system
(definition)
Definition:
A protocol in which one or more provers try to convince another party, called the verifier, that the prover(s) possess certain true knowledge, such as the membership of a string x in a given language, often with the goal of revealing no further details about this knowledge. The prover(s) and verifier are formally defined as probabilistic Turing machines with special "interaction tapes" for exchanging messages.
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
interiorbased representation
(definition)
Definition:
A representation of a region that is based on its interior (i.e., the cells that compose it).
Note:
From Algorithms and Theory of Computation Handbook, page 1824, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
internal node
(definition)
Definition:
A node of a tree that has one or more child nodes, equivalently, one that is not a leaf.
Also known as nonterminal node.
Note:
See [CLR90, page 93] or [HS83, page 220].
Authors: LJW,PEB
internal sort
(definition)
Definition:
Any sort algorithm which uses exclusively main memory during the sort. This assumes highspeed random access to all memory.
Note:
Although virtual memory may hide the use of disk, an internal sort is written as if all memory is equally accessible. From Algorithms and Theory of Computation Handbook, page 323, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
interpolation search
(algorithm)
Definition:
Search a sorted array by estimating the next position to check based on a linear interpolation of the search key and the values at the ends of the search interval.
Also known as extrapolation search.
Note:
You probably use this when looking something up in the telephone book or dictionary. For instance, "cold fusion" is probably near the front, so you open maybe 1/4 of the way in. What you find there helps you decide whether to turn many pages or just a few. Compare this with a linear search, where you check each entry in order from the beginning, or a binary search, where you always divide the search interval exactly in half.
Average run time is O(log log n) assuming the keys are uniformly distributed. Worst case for any distribution is O(n).
Perl, Itai, and Avni note that "When the difference between the indices of two successive iterations is small, it may be advantageous to switch to sequential search ..." Unless the data is very uniform, there are millions of records, or comparisons are very timeconsuming, a binary search may be no slower: interpolation is usually timeconsuming on a computer and a binary search only takes log(n) comparisons anyway.
Author: PEB
More information
Yehoshua Perl, Alon Itai, and Haim Avni, Interpolation searcha log logN search, CACM 21(7):550553, July 1978.
interpolationsequential search
(algorithm)
Definition:
An approximate location is interpolated from the first and last items of a sorted array, then a linear search finds the actual location.
Author: PEB
intersection
(definition)
Definition:
The intersection of two sets is a set having those members which are in both sets.
Note:
The intersection of {2, 3, 5} and {7, 5, 2} is {5, 2}.
Author: PEB
intractable
(definition)
Definition:
A problem for which no algorithm can exist which computes all instances of it in polynomial time.
Author: PEB
introspective sort
(algorithm)
Definition:
A variant of quicksort which switches to heapsort for pathological inputs, that is, when execution time is becoming quadratic.
Also known as introsort.
Author: PEB
More information
abstract and link to Musser's paper
David R. Musser, Introspective Sorting and Selection Algorithms, SoftwarePractice and Experience, 8:983993, 1997.
inverse Ackermann function
(algorithm)
Definition:
A function of two parameters whose value grows very, very slowly.
Formal Definition: α(m,n) = min{i≥ 1: A(i, m/n) > log_{2} n} where A(i,j) is Ackermann's function.
Also known as α.
Note:
This is not strictly the inverse of Ackermann's function. Rather, this grows as slowly as Ackermann's function grows quickly. After [CLR90, page 452].
Author: PEB
inverse suffix array
(data structure)
Definition:
For each position in a string, the inverse suffix array has its index in the string's suffix array.
Formal Definition: Given a suffix array, sa, and the corresponding inverse suffix array, isa, isa[i] = j iff sa[j] = i.
Generalization (I am a kind of ...)
array.
Note:
Consider the string "good". In onebased indexing, the suffix array is [4, 1, 3, 2]. The inverse suffix array is [2, 4, 3, 1].
Many algorithms to build suffix arrays use an inverse suffix array. A suffix array can be built from the inverse suffix array in linear time. An inverse suffix array can be turned into a suffix array in place in linear time, too.
Author: PEB
inverted file index
(data structure)
Definition:
An inverted index that only indicates the text in which a word appears, not where the word appears within the text.
Generalization (I am a kind of ...)
inverted index.
Note:
See the example at inverted index.
Author: PEB
More information
Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro, and Ricardo BaezaYates, Compression: A Key for NextGeneration Text Retrieval Systems, IEEE Computer, 33(11):3744, November 2000, (page 42). Justin Zobel and Alistair Moffat, Inverted Files for Text Search Engines, ACM Computing Surveys, 38(2), article 6, July 2006.
inverted index
(data structure)
Definition:
An index into a set of texts of the words in the texts. The index is accessed by some search method. Each index entry gives the word and a list of texts, possibly with locations within the text, where the word occurs.
Specialization (... is a kind of me.)
block addressing index, full inverted index, inverted file index.
Note:
Suppose we want to search the texts "i love you," "god is love," "love is blind," and "blind justice." (The words of the text are all lower case for simplicity.) If we index by (text, character within the text), the index with location in text is: blind (3,8);(4,0) god (2,0) i (1,0) is (2,4);(3,5) justice (4,6) love (1,2);(2,7);(3,0) you (1,7) The word "blind" is in document 3 ("love is blind") starting at character 8, so has an entry (3,8) . To find, for instance, documents with both "is" and "love," first look up the words in the index, then find the intersection of the texts in each list. In this case, documents 2 and 3 have both words. We can quickly find documents where the words appear close to each other by comparing the character within the text. The index may have the word number, instead of the character number. It may also have weights, frequencies, or other indicators.
Author: PEB
More information
Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro, and Ricardo BaezaYates, Compression: A Key for NextGeneration Text Retrieval Systems, IEEE Computer, 33(11):3744, November 2000, (page 42). Justin Zobel and Alistair Moffat, Inverted Files for Text Search Engines, ACM Computing Surveys, 38(2), article 6, July 2006.
irreflexive
(definition)
Definition:
A binary relation R for which there is no element a such that a R a.
Note:
The relation "less than" is irreflexive since no number is less than itself.
Author: PEB
More information
After Eric W. Weisstein's World of Mathematics entry irreflexive.
isomorphic
(definition)
Definition:
Two graphs are isomorphic if there is a onetoone correspondence between their vertices and there is an edge between two vertices of one graph if and only if there is an edge between the two corresponding vertices in the other graph.
Author: SKS
iteration
(algorithmic technique)
Definition:
Solve a problem by repeatedly working on successive parts of the problem.
Author: PEB
More information
See dynamic algorithms for an example of one tradeoff between speed and clarity for a recursive vs. an iterative implementation.
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
