Algorithms and Data Structures Glossary (Starting with "F")

Free glossaries at TanslationDirectory.com

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

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

F

facility location
factor: see substring
factorial
fast fourier transform
fathoming
feasible region
feasible solution
feedback edge set
feedback vertex set
Ferguson-Forcade algorithm
FFT: see fast fourier transform
Fibonaccian search
Fibonacci heap
Fibonacci number
Fibonacci tree
FIFO: see queue
filial-heir 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 child-next sibling binary tree: see binary tree representation of trees
first come, first served
first-in, first-out
Fisher-Yates shuffle
fixed-grid method
flash sort
flow
flow conservation
flow function
flow network
Floyd-Warshall algorithm
Ford-Bellman: see Bellman-Ford algorithm
Ford-Fulkerson 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 × n-1 × ... × 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 × (n-1)! 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) = ∫ ₀^∞ e^-xx^1-1dx = ∫ ₀^∞ e^-xdx = 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 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

feasible region

(definition)

Definition: The set of all possible solutions of an optimization problem.

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

feasible solution

(definition)

Definition: Any element of the feasible region of an optimization problem.

Author: CRC-A

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:171-181, 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 q-p (F(n-1)) 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):596-615, 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(Φⁿ/√ 5), where Φ=(1+√ 5)/2.

Formal Definition: The n^th Fibonacci number is

F(n) = F(n-1) + F(n-2), where F(1)=1 and F(2)=1, or
F(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 pair-wise multiplication be
(A,B)(C,D) = (AC+AD+BC,AC+BD)
This is just (AX+B)*(CX+D) mod X²-X-1, 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(N-1))
which can be computed in log N steps by repeated squaring.

As an example, here is a table of pair-wise 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(N-1)
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 n-1 and a right subtree of order n-2. 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):39-45, 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 read-only and shifts only from left to right. After 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: 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 read-only input and a write-only 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 first-in, first-out.

Note: Written more fully this is, "the FIRST item to COME here is the FIRST one SERVED."

Author: PEB

first-in, first-out

(definition)

Definition: A policy that items are processed in order of arrival. A queue implements this.

Note: Same as first come, first served. A breadth-first search checks newly encountered nodes first-in, first-out. Often written as FIFO.

Author: PEB

Fisher-Yates 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 pseudo-random 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.

fixed-grid 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 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

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

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

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

Floyd-Warshall algorithm

(algorithm)

Definition: An algorithm to solve the all pairs shortest path problem in a weighted, directed graph by multiplying an adjacency-matrix representation of the graph multiple times. The edges may have negative weights, but no negative weight cycles. The time complexity is Θ (V³).

Author: SKS

Ford-Fulkerson method

(algorithm)

Definition: Given a flow function and its corresponding residual graph (a maximum-flow 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 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

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.

Author: CRC-A

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):545-566, 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 Baeza-Yates, Compression: A Key for Next-Generation Text Retrieval Systems, IEEE Computer, 33(11):37-44, 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 8-22, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

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

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/ε.

Author: CRC-A

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, n-ary 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⁰⁺. 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

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

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

Free Newsletter

Menu

Advertisements

Algorithms and Data Structures Glossary(Starting with "F")

F

facility location

factorial

fast fourier transform

fathoming

feasible region

feasible solution

feedback edge set

feedback vertex set

Fibonaccian search

Fibonacci heap

Fibonacci number

Fibonacci tree

Find

finitary tree

finite state machine

finite state transducer

first come, first served

first-in, first-out

Fisher-Yates shuffle

fixed-grid method

flow

flow conservation

flow function

flow network

Floyd-Warshall algorithm

Ford-Fulkerson method

forest

forest editing problem

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

Algorithms and Data Structures Glossary
(Starting with "F")