Index

F

factor, 851

twiddle, 836

factorial function (!), 54–55

factorization, 896–901, 905

unique, 854

failure in a Bernoulli trial, 1112

fair coin, 1101

fan-out, 988

Farkas's lemma, 819 pr.

farthest-pair problem, 948

FASTER-ALL-PAIRS-SHORTEST-PATHS, 627, 628 ex.

FASTEST-WAY, 329

Fast Fourier Transform (FFT)

circuit for, 842–843

iterative implementation of, 839–842

multidimensional, 845 pr.

recursive implementation of, 834–836

using modular arithmetic, 847 pr.

feasibility problem, 601, 818 pr.

feasible linear program, 778

feasible region, 773

feasible solution, 601, 773, 778

Fermat's theorem, 877

FFT, see Fast Fourier Transform

FIB-HEAP-CHANGE-KEY, 497 pr.

FIB-HEAP-DECREASE-KEY, 489

FIB-HEAP-DELETE, 492

FIB-HEAP-EXTRACT-MIN, 483

FIB-HEAP-INSERT, 480

FIB-HEAP-LINK, 486

FIB-HEAP-PRUNE, 497 pr.

FIB-HEAP-UNION, 482

Fibonacci heap, 476–497

changing a key in, 497 pr.

creating, 480

decreasing a key in, 489–492

deletion from, 492, 496 pr.

in Dijkstra's algorithm, 599

extracting the minimum key from, 482–488

insertion into, 480–481

in Johnson's algorithm, 640

maximum degree of, 479, 493–496

minimum key of, 481

potential function for, 479

in Prim's algorithm, 573

pruning, 497 pr.

running times of operations on, 456 fig.

uniting, 481–482

Fibonacci numbers, 56, 86 pr., 494

computation of, 902 pr.

field of an object, 20

FIFO (first-in, first-out), 200

see also queue

final-state function, 917

FIND-DEPTH, 519 pr.

find path, 506

FIND-SET, 499

disjoint-set-forest implementation of, 508, 522

linked-list implementation of, 501

finished vertex, 540

finishing time, in depth-first search, 541

and strongly connected components, 555

finish time, in activity selection, 371

finite automaton, 916

for string matching, 917–922

FINITE-AUTOMATON-MATCHER, 919

finite group, 862

finite sequence, 1078

finite set, 1073

first-fit heuristic, 1049 pr.

first-in, first-out, 200

see also queue

fixed-length code, 385

floating-point data type, 22

floor function (⌊⌋), 51

in master theorem, 81–84

floor instruction, 22

flow, 644–650

aggregate, 788

blocking, 697

excess, 669

integer-valued, 666

sum, 650 ex.

total net, 645

total positive, 645

value of, 644

flow conservation, 644

flow network, 644–650

corresponding to a bipartite graph, 665

cut of, 654–657

with negative capacities, 695 pr.

FLOYD-WARSHALL, 630

FLOYD-WARSHALL', 635 ex.

Floyd-Warshall algorithm, 629–632, 634 ex.

for

and loop invariants, 18 n.

in pseudocode, 19

FORD-FULKERSON, 658

Ford-Fulkerson method, 651–664

FORD-FULKERSON-METHOD, 651

forest, 1083, 1085

depth-first, 540

disjoint-set, 505–509

formal power series, 86 pr.

formula-satisfiability problem, 996–998

forward edge, 546

forward substitution, 744–745

fractional knapsack problem, 382, 384 ex.

freeing of objects, 210–212

free list, 211

FREE-OBJECT, 212

free tree, 1083, 1085–1087

frequency domain, 822

full binary tree, 1089, 1091 ex.

relation to optimal code, 386

full node, 439

full rank, 731

full walk of a tree, 1030

fully parenthesized, 331

fully polynomial-time approximation scheme, 1023

for the maximum-clique problem, 1050 pr.

for the subset-sum problem, 1043–1049

function, 1077–1080

Ackermann's, 521

basis, 762

convex, 1109

linear, 25, 772

objective, see objective function

prefix, 923–925

quadratic, 25

suffix, 917

transition, 916

functional iteration, 55

fundamental theorem of linear programming, 816

fusion tree, 182, 433

fuzzy sorting, 163 pr.