﻿ Algorithms and Data Structures Glossary (Starting with "I")
 Home Free Glossaries Free Dictionaries Post Your Translation Job! Free Articles Jobs for Translators

#### Algorithms and Data Structures Glossary(Starting with "I")

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

### I

ideal merge
ideal random shuffle
implication
implies
inclusion-exclusion principle
inclusive or: see or
incompressible string
incremental hashing: see linear hashing
in-degree
independent set
index file
information theoretic bound
in-order traversal
in-place sort
insertion sort
integer linear program
integer multi-commodity flow
integer polyhedron
interactive proof system
interior-based representation
internal node
internal sort
interpolation search
interpolation-sequential 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.

#### 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.)
Fisher-Yates 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

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

#### inclusion-exclusion principle

(definition)

Definition: A rule that allows to compute the probability of exactly r occurrences of events A1, A2, ... , An.

Note: From Algorithms and Theory of Computation Handbook, page 14-35, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### 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 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

#### in-degree

(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 B-tree.

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 1-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

#### in-order 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, depth-first 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

#### in-place 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(n2) 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):312-313, 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

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 NP-hard.

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

#### integer multi-commodity flow

(definition)

Definition: A multi-commodity flow in which the flow of each commodity through each edge must take an integer value. The term is also used to capture the multi-commodity flow problem in which each demand is routed along a single path.

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

#### integer polyhedron

(definition)

Definition: A polyhedron, all of whose extreme points are integer valued.

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

#### 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 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

#### interior-based 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 18-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

#### 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 high-speed 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 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

#### 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 time-consuming, a binary search may be no slower: interpolation is usually time-consuming on a computer and a binary search only takes log(n) comparisons anyway.

Author: PEB

Yehoshua Perl, Alon Itai, and Haim Avni, Interpolation search-a log logN search, CACM 21(7):550-553, July 1978.

#### interpolation-sequential 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

abstract and link to Musser's paper

David R. Musser, Introspective Sorting and Selection Algorithms, Software-Practice and Experience, 8:983-993, 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) > log2 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 one-based 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

Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro, and Ricardo Baeza-Yates, Compression: A Key for Next-Generation Text Retrieval Systems, IEEE Computer, 33(11):37-44, 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

Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro, and Ricardo Baeza-Yates, Compression: A Key for Next-Generation Text Retrieval Systems, IEEE Computer, 33(11):37-44, 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

After Eric W. Weisstein's World of Mathematics entry irreflexive.

#### isomorphic

(definition)

Definition: Two graphs are isomorphic if there is a one-to-one 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

See dynamic algorithms for an example of one trade-off between speed and clarity for a recursive vs. an iterative implementation.

 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