- 6.3.1: For a sequence s : a1, a2, . . . , an of n 3 distinct numbers, writ...
- 6.3.2: For a sequence s : a1, a2, . . . , an of n numbers, write an algori...
- 6.3.3: For a sequence s : a1, a2, . . . , an of n numbers, write an algori...
- 6.3.4: For a sequence s : a1, a2, . . . , an of n 3 numbers, write an algo...
- 6.3.5: Write an algorithm that computes the sum of the absolute values of ...
- 6.3.6: For a sequence s : a1, a2, . . . , an of n 2 numbers, write an algo...
- 6.3.7: For a real number a and nonnegative integer n, define an recursivel...
- 6.3.8: (a) For a positive integer n and n+1 constants cn, cn1, . . . , c1,...
- 6.3.9: For a positive integer n and n+1 constants cn, cn1, . . . , c1, c0 ...
Solutions for Chapter 6.3: Analysis of Algorithms
Full solutions for Discrete Mathematics | 1st Edition
Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).
Basis for V.
Independent vectors VI, ... , v d whose linear combinations give each vector in V as v = CIVI + ... + CdVd. V has many bases, each basis gives unique c's. A vector space has many bases!
A matrix can be partitioned into matrix blocks, by cuts between rows and/or between columns. Block multiplication ofAB is allowed if the block shapes permit.
Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn - l . Cx = convolution c * x. Eigenvectors in F.
When random variables Xi have mean = average value = 0, their covariances "'£ ij are the averages of XiX j. With means Xi, the matrix :E = mean of (x - x) (x - x) T is positive (semi)definite; :E is diagonal if the Xi are independent.
Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then S-I AS = A = eigenvalue matrix.
Fast Fourier Transform (FFT).
A factorization of the Fourier matrix Fn into e = log2 n matrices Si times a permutation. Each Si needs only nl2 multiplications, so Fnx and Fn-1c can be computed with ne/2 multiplications. Revolutionary.
Hermitian matrix A H = AT = A.
Complex analog a j i = aU of a symmetric matrix.
Jordan form 1 = M- 1 AM.
If A has s independent eigenvectors, its "generalized" eigenvector matrix M gives 1 = diag(lt, ... , 1s). The block his Akh +Nk where Nk has 1 's on diagonall. Each block has one eigenvalue Ak and one eigenvector.
Kronecker product (tensor product) A ® B.
Blocks aij B, eigenvalues Ap(A)Aq(B).
Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.
Matrix multiplication AB.
The i, j entry of AB is (row i of A)·(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .
Multiplicities AM and G M.
The algebraic multiplicity A M of A is the number of times A appears as a root of det(A - AI) = O. The geometric multiplicity GM is the number of independent eigenvectors for A (= dimension of the eigenspace).
Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.
In each column, choose the largest available pivot to control roundoff; all multipliers have leij I < 1. See condition number.
Pseudoinverse A+ (Moore-Penrose inverse).
The n by m matrix that "inverts" A from column space back to row space, with N(A+) = N(AT). A+ A and AA+ are the projection matrices onto the row space and column space. Rank(A +) = rank(A).
Rank one matrix A = uvT f=. O.
Column and row spaces = lines cu and cv.
Rank r (A)
= number of pivots = dimension of column space = dimension of row space.
Symmetric matrix A.
The transpose is AT = A, and aU = a ji. A-I is also symmetric.
Tridiagonal matrix T: tij = 0 if Ii - j I > 1.
T- 1 has rank 1 above and below diagonal.