Algorithms and Data Structures Glossary (Starting with "F")
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
F
 facility location
 factor: see substring
 factorial
 fast fourier transform
 fathoming
 feasible region
 feasible solution
 feedback edge set
 feedback vertex set
 FergusonForcade algorithm
 FFT: see fast fourier transform
 Fibonaccian search
 Fibonacci heap
 Fibonacci number
 Fibonacci tree
 FIFO: see queue
 filialheir chain: see binary tree representation of trees
 Find
 find k^{th} least element: see select k^{th} element
 finitary tree
 finite Fourier transform
 finite state automaton: see finite state machine
 finite state machine
 finite state machine minimization
 finite state transducer
 first childnext sibling binary tree: see binary tree representation of trees
 first come, first served
 firstin, firstout
 FisherYates shuffle
 fixedgrid method
 flash sort
 flow
 flow conservation
 flow function
 flow network
 FloydWarshall algorithm
 FordBellman: see BellmanFord algorithm
 FordFulkerson method
 forest
 forest editing problem
 formal language: see language
 formal methods
 formal verification
 forward index
 fractional knapsack problem
 fractional solution
 free edge
 free tree
 free vertex
 frequency count heuristic
 full array
 full binary tree
 full inverted index
 fully dynamic graph problem
 fully persistent data structure
 fully polynomial approximation scheme
 function
 functional data structure: see active data structure
facility location
(classic problem)
Definition:
Given a set of demand points, a distance function, and a parameter p, find a set of p supply objects (points, lines, segments, etc.) which minimizes some distance objective function. The function may be the maximum distance between any demand point and the nearest supply, so no demand point is too far from a supply, or the sum of distances to the nearest supply.
Note:
Adapted from [AS98, page 428].
Author: PEB
factorial
(definition)
Definition:
The factorial of an integer n ≥ 0, written n!, is n × n1 × ... × 2 × 1. In particular, 0! = 1.
Generalization (I am a kind of ...)
gamma function.
Specialization (... is a kind of me.)
Stirling's approximation.
Aggregate parent (I am a part of or used in ...)
permutation, combination.
Note:
For instance 5! = 120. Factorial is often used as a (poor) example of recursion, since n! = n × (n1)! for n > 1, however a simple loop is usually faster and just as clear.
Why is 0! = 1? Using the gamma function definition, 0! = Γ(0+1) = ∫ _{0}^{∞} e^{x}x^{11}dx = ∫ _{0}^{∞} e^{x}dx = 1.
Author: PEB
fast fourier transform
(algorithm)
Definition:
An algorithm to convert a set of uniformly spaced points from the time domain to the frequency domain.
Also known as FFT.
Note:
Used to convert a complicated wave into its component sine waves.
Author: PS
fathoming
(algorithmic technique)
Definition:
Pruning a search tree.
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
feasible region
(definition)
Definition:
The set of all possible solutions of an optimization problem.
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
feasible solution
(definition)
Definition:
Any element of the feasible region of an optimization problem.
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
feedback edge set
(definition)
Definition:
The smallest set of edges whose deletion results in an acyclic graph.
Author: PEB
feedback vertex set
(definition)
Definition:
The smallest set of vertices whose deletion results in an acyclic graph.
Author: PEB
More information
Helaman R. P. Ferguson and Rodney W. Forcade, Multidimensional Euclidean algorithms, Journal Fur Dir Reine Und Angewandte Mathematik 334:171181, 1982. Walter de Gruyter & Co.
Fibonaccian search
(algorithm)
Definition:
Search a sorted array by narrowing possible locations to progressively smaller intervals. Begin with two Fibonacci numbers, p (F(n)) and q (F(n+1)), such that p < n ≤ q, where n is the size of the array. The first step checks location p. The size of the next interval is p, if the key is less than the item at that location, or qp (F(n1)) if it is greater.
Aggregate child (... is a part of or used in me.)
Fibonacci number, search locations are a Fibonacci tree.
Note:
This is similar to a binary search, but only needs subtraction, instead of divide by two or shift right, to compute the next position.
Author: PEB
More information
David E. Ferguson, Fibonaccian Searching, CACM, 3(12):648, December 1960. Also [Knuth98, 3:417, Sect. 6.2.1].
Fibonacci heap
(data structure)
Definition:
A heap made of a forest of trees. The amortized cost of the operations create, insert a value, decrease a value, find minimum, and merge or join (meld) two heaps, is a constant Θ(1). The delete operation takes O(log n).
Generalization (I am a kind of ...)
heap.
Aggregate parent (I am a part of or used in ...)
priority queue, Dijkstra's algorithm.
Note:
After [CLR90, page 421].
Author: PEB
More information
Michael L. Fredman and Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, 34(3):596615, July, 1987.
Fibonacci number
(definition)
Definition:
A member of the sequence of numbers such that each number is the sum of the preceding two. The first seven numbers are 1, 1, 2, 3, 5, 8, and 13. F(n) ≈ round(Φ^{n}/√ 5), where Φ=(1+√ 5)/2.
Formal Definition: The n^{th} Fibonacci number is  F(n) = F(n1) + F(n2), where F(1)=1 and F(2)=1, or
 F(n) = (Φ^{n}  φ^{n})/√ 5, where Φ=(1+√ 5)/2 and φ=(1√ 5)/2.
Aggregate parent (I am a part of or used in ...)
Fibonacci tree, Fibonaccian search.
Note:
Fibonacci, or more correctly Leonardo of Pisa, discovered the series in 1202 when he was studying how fast rabbits could breed in ideal circumstances. Computing Fibonacci numbers with the recursive formula is an example in the notes for memoization. The N^{th} Fibonacci number can be computed in log N steps. The following method is by Bill Gosper & Gene Salamin, Hakmem Item 12, M.I.T.
Let pairwise multiplication be (A,B)(C,D) = (AC+AD+BC,AC+BD) This is just (AX+B)*(CX+D) mod X²X1, and so is associative and commutative. Note that (A,B)(1,0) = (A+B,A) which is the Fibonacci recurrence. Thus, (1,0)^N = (F(N),F(N1)) which can be computed in log N steps by repeated squaring.
As an example, here is a table of pairwise Fibonacci numbers: b^pow pow (1,0) 1 (1,0)(1,0) = (1,1) 2 (1,1)(1,0) = (2,1) 3 (2,1)(1,0) = (3,2) 4 (3,2)(1,0) = (5,3) 5 (5,3)(1,0) = (8,5) 6 (8,5)(1,0) = (13,8) 7 (13,8)(1,0) = (21,13) 8 and here are some "Fibonacci" multiplications (1,1)(1,1) = (3,2) b^2 * b^2 = b^4 (3,2)(3,2) = (9+6+6,9+4) = (21,13) b^4 * b^4 = b^8 (1,1)(5,3) = (5+3+5,5+3) = (13,8) b^2 * b^5 = b^7 They also note that for general second order recurrences G(N+1) = XG(N) + YG(N1) we have the rule (A,B)(C,D) = (AD+BC+XAC,BD+YAC) Inverses and fractional powers are given also.
Author: PR
More information
A wonderful site on Fibonacci Numbers and the Golden Section.
Fibonacci tree
(data structure)
Definition:
A variant of a binary tree where a tree of order n (n>1) has a left subtree of order n1 and a right subtree of order n2. An order 0 Fibonacci tree has no nodes, and an order 1 tree has 1 node.
Generalization (I am a kind of ...)
binary tree, AVL tree.
Aggregate parent (I am a part of or used in ...)
Fibonaccian search.
Aggregate child (... is a part of or used in me.)
Fibonacci number.
Note:
A Fibonacci tree of order n has F(n+2)1 nodes, where F(n) is the n^{th} Fibonacci number. A Fibonacci tree is the most unbalanced AVL tree allowed.
Author: PEB
More information
pictures of Fibonacci trees of various orders.
[Knuth98, 3:417, Sect. 6.2.1].
Find
(algorithm)
Definition:
An algorithm to select the k^{th} smallest element of an array and partition the array around it. First, partition around the value of the k^{th} element. If the split is not at element k, move the upper or lower boundary and partition again.
Note:
This does more swaps than MODIFIND.
Author: PEB
More information
C. A. R. Hoare, Algorithm 65, FIND, CACM, 4(7):321, July 1961. C. A. R. Hoare, Proof of a Program: FIND, CACM, 14(7):3945, January 1971.
finitary tree
(data structure)
Definition:
A tree with a finite number of children at every node.
Note:
As opposed to infinitary trees which may have an infinite number of children at some nodes.
Author: PEB
finite state machine
(definition)
Definition:
A model of computation consisting of a set of states, a start state, an input alphabet, and a transition function that maps input symbols and current states to a next state. Computation begins in the start state with an input string. It changes to new states depending on the transition function. There are many variants, for instance, machines having actions (outputs) associated with transitions (Mealy machine) or states (Moore machine), multiple start states, transitions conditioned on no input symbol (a null) or more than one transition for a given symbol and state (nondeterministic finite state machine), one or more states designated as accepting states (recognizer), etc.
Also known as finite state automaton.
Generalization (I am a kind of ...)
model of computation, Turing machine, state machine.
Specialization (... is a kind of me.)
deterministic finite state machine, nondeterministic finite state machine, Kripke structure, finite state transducer, Markov chain, hidden Markov model, Mealy machine, Moore machine.
Note:
Equivalent to a restricted Turing machine where the head is readonly and shifts only from left to right. After 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: PEB
More information
The FASTAR (Finite Automata Systems  Theoretical and Applied Research) group site links to some papers, conferences, and projects.
finite state transducer
(definition)
Definition:
A finite state machine specifically with a readonly input and a writeonly output. The input and output cannot be reread or changed.
Note:
Thanks to L. J. Buitinck for correcting the definition. 28 May 2004.
Author: PEB
first come, first served
(definition)
Definition:
See firstin, firstout.
Note:
Written more fully this is, "the FIRST item to COME here is the FIRST one SERVED."
Author: PEB
firstin, firstout
(definition)
Definition:
A policy that items are processed in order of arrival. A queue implements this.
Note:
Same as first come, first served. A breadthfirst search checks newly encountered nodes firstin, firstout. Often written as FIFO.
Author: PEB
FisherYates shuffle
(algorithm)
Definition:
Randomly permute N elements by exchanging each element e_{i} with a random element from i to N. It consumes Θ(N log N) bits and runs in linear time.
Generalization (I am a kind of ...)
ideal random shuffle, permutation.
Note:
The algorithm can be viewed as a reverse selection sort. It is described in some detail as algorithm P in [Knuth97, vol. 2, p 145].
For even a rather small number of elements (or cards), the total number of permutations is far larger than the period of most pseudorandom number generators. This implies that most permutations will never be generated. (After documentation for random.shuffle() in Python, particularly v2.6.1.)
Author: PEB
More information
R. A. Fisher and F. Yates, Example 12, Statistical Tables, London, 1938. Richard Durstenfeld, Algorithm 235: Random permutation, CACM 7(7):420, July 1964.
fixedgrid method
(definition)
Definition:
Space decomposition into rectangular cells by overlaying a grid on it.If the cells are congruent (i.e.,of the same width, height, etc.), then the grid is said to be uniform.
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
flow
(definition)
Definition:
A measure of the maximum weight along paths in a weighted, directed graph.
Author: PEB
flow conservation
(definition)
Definition:
The property that no vertex, except the source and sink, of a flow network creates or stores flow. More formally, the incoming flow is the same as the outgoing flow, or, the net flow is 0.
Note:
From Algorithms and Theory of Computation Handbook, page 710, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
flow function
(definition)
Definition:
An assignment of flow values to the edges of a flow network that satisfies flow conservation, skew symmetry, and capacity constraints.
Also known as network flow.
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
flow network
(definition)
Definition:
A weighted, directed graph with two specially marked nodes, the source s and the sink t, and a capacity function that maps edges to positive real numbers, u: E → R^{+}.
Note:
A graph with multiple sources or sinks may be converted into a flow network by adding a supersource, which has infinite capacity to all sources, or a supersink, which has infinite capacity from all sinks.
From Algorithms and Theory of Computation Handbook, page 710, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
FloydWarshall algorithm
(algorithm)
Definition:
An algorithm to solve the all pairs shortest path problem in a weighted, directed graph by multiplying an adjacencymatrix representation of the graph multiple times. The edges may have negative weights, but no negative weight cycles. The time complexity is Θ (V³).
Author: SKS
FordFulkerson method
(algorithm)
Definition:
Given a flow function and its corresponding residual graph (a maximumflow problem), select a path from the source to the sink along which the flow can be increased and increase the flow. Repeat until there are no such paths.
Note:
This algorithm was proposed in 1956. After Wilf.
Author: PEB
forest
(definition)
Definition:
A collection of one or more trees.
Formal Definition: An undirected, acyclic graph.
Note:
Different vertices of a forest need not be connected.
Author: PEB
forest editing problem
(definition)
Definition:
The problem of finding an edit script of minimum cost which transforms a given forest into another given forest.
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
formal methods
(definition)
Definition:
A group of analytical approaches having mathematically precise foundation which can serve as a framework or adjunct for human engineering and design skills and experience.
Author: PEB
formal verification
(definition)
Definition:
Establishing properties of hardware or software designs using logic, rather than (just) testing or informal arguments. This involves formal specification of the requirement, formal modeling of the implementation, and precise rules of inference to prove, say, that the implementation satisfies the specification.
Author: SKS
forward index
(data structure)
Definition:
An index into a set of texts. This is usually created as the first step to making an inverted index.
Author: PEB
fractional knapsack problem
(classic problem)
Definition:
Given materials of different values per unit volume and maximum amounts, find the most valuable mix of materials which fit in a knapsack of fixed volume. Since we may take pieces (fractions) of materials, a greedy algorithm finds the optimum. Take as much as possible of the material that is most valuable per unit volume. If there is still room, take as much as possible of the next most valuable material. Continue until the knapsack is full.
Also known as continuous knapsack problem.
Note:
The problem may equivalently be expressed in terms of weight instead of volume. This is also known as the continuous knapsack problem since amounts have continuous, rather than discrete, values.
Author: PEB
fractional solution
(definition)
Definition:
Typically, a solution to a relaxation of an optimization problem.
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
free edge
(definition)
Definition:
An edge which is not in a matching.
Author: PEB
free tree
(definition)
Definition:
A connected, acyclic, undirected graph.
Note:
This differs from the usual notion of a tree in that it does not have a root. This differs from a forest in that it is connected. After [CLR90, page 91].
Author: PEB
free vertex
(definition)
Definition:
A vertex not on a matched edge in a matching, or, one which has not been matched.
Author: PEB
frequency count heuristic
(algorithm)
Definition:
A heuristic that keeps the elements of a list ordered by number of times each element is the target of a search.
Author: PEB
full array
(definition)
Definition:
A term from combinatorial chemistry referring to trying all possible combinations of blocks. This is not a data structure, and is here to reduce confusion.
Author: PEB
More information
Dimitris K. Agrafiotis, Multiobjective Optimization of Combinatorial Libraries, IBM Journal of Research and Development, Yorktown Heights, New York, USA, 45(3/4):545566, May/July 2001. Referenced on page 548.
full binary tree
(data structure)
Definition:
A binary tree in which each node has exactly zero or two children.
Also known as proper binary tree.
Specialization (... is a kind of me.)
coding tree.
Aggregate parent (I am a part of or used in ...)
Huffman coding.
Note:
In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding is a full binary tree. A BDD is a full binary tree. After Mustafa Ege (ege@eti.cc.hun.edu.tr) Hacettepe University, comp.theory, 17 November 1998. Also [CLR90, page 95], and [Stand98, page 248].
This kind of tree is called "proper" by Goodrich & Tamassia page 231. Sahni, page 461, and Carrano & Prichard, page 429, define full binary tree the way we define a perfect binary tree.
Author: PEB
full inverted index
(data structure)
Definition:
An inverted index that includes the exact location within texts, in addition to the text in which the word appears.
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).
fully dynamic graph problem
(definition)
Definition:
Problem where the update operations include unrestricted insertions and deletions of edges.
Note:
From Algorithms and Theory of Computation Handbook, page 822, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
fully persistent data structure
(definition)
Definition:
A persistent data structure that allows updates to all versions, previous and latest.
Note:
From Algorithms and Theory of Computation Handbook, page 524, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
fully polynomial approximation scheme
(algorithmic technique)
Definition:
A set of algorithms {A_{ε}  ε > 0}, where each A_{ε} is a 1+εapproximation algorithm bounded by a polynomial in the length of the input and 1/ε.
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
function
(definition)
Definition:
(1) A computation which takes some arguments or inputs and yields an output. Any particular input yields the same output every time. More formally, a mapping from each element in the domain to an element in the range. (2) A subroutine which returns a value.
Generalization (I am a kind of ...)
relation.
Specialization (... is a kind of me.)
boolean function, constant function, unary function, binary function, trinary function, nary function, total function.
Aggregate child (... is a part of or used in me.)
signature.
Note:
(1) A relation may map an input to more than one output. Every function is a relation. The inverse of a function, a mapping from the function's outputs to its inputs, may be a relation rather than another function. Consider √(x). The domain and the range are the nonnegative real numbers, R^{0+}. For instance 4 is mapped to 2. The inverse is the function x², which maps 2 to 4. Cosine is also a function, since every angle has a specific cosine, but its inverse cos^{1}(x) is a relation, since a cosine value maps to many (for cosine, infinitely many) angles. A function which takes no arguments is a constant function, or simply, a constant. Since a function must return the same value for each input and the input cannot change (since it has no arguments), it must always return the same value. For instance, if the function one() always returns 1, we can use it instead of the constant 1. This is theoretically convenient because we can always work with functions, rather than with functions and constants. (2) A subroutine which does not return a value is called a "procedure" in some programming languages.
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
