 4.8.1: Find the value of z when each of the algorithm segments in 1 and 2 ...
 4.8.2: Find the value of z when each of the algorithm segments in 1 and 2 ...
 4.8.3: Consider the following algorithm segment: if x y > 0 then do y := 3...
 4.8.4: Find the values of a and e after execution of the loops in 4 and 5:
 4.8.5: Find the values of a and e after execution of the loops in 4 and 5:
 4.8.6: Make a trace table to trace the action of Algorithm 4.8.1 for the i...
 4.8.7: Make a trace table to trace the action of Algorithm 4.8.1 for the i...
 4.8.8: The following algorithm segment makes change; given an amount of mo...
 4.8.9: Find the greatest common divisor of each of the pairs of integers i...
 4.8.10: Find the greatest common divisor of each of the pairs of integers i...
 4.8.11: Find the greatest common divisor of each of the pairs of integers i...
 4.8.12: Find the greatest common divisor of each of the pairs of integers i...
 4.8.13: Use the Euclidean algorithm to handcalculate the greatest common d...
 4.8.14: Use the Euclidean algorithm to handcalculate the greatest common d...
 4.8.15: Use the Euclidean algorithm to handcalculate the greatest common d...
 4.8.16: Use the Euclidean algorithm to handcalculate the greatest common d...
 4.8.17: Make a trace table to trace the action of Algorithm 4.8.2 for the i...
 4.8.18: Make a trace table to trace the action of Algorithm 4.8.2 for the i...
 4.8.19: Prove that for all positive integers a and b, a  b if, and only if...
 4.8.20: a. Prove that if a and b are integers, not both zero, and d = gcd(a...
 4.8.21: Complete the proof of Lemma 4.8.2 by proving the following: If a an...
 4.8.22: a. Prove: If a and d are positive integers and q and r are integers...
 4.8.23: a. Prove that if a, d, q, and r are integers such that a = dq + r a...
 4.8.24: An alternative to the Euclidean algorithm uses subtraction rather t...
 4.8.25: Exercises 2529 refer to the following definition
 4.8.26: Exercises 2529 refer to the following definition
 4.8.27: Exercises 2529 refer to the following definition
 4.8.28: Exercises 2529 refer to the following definition
 4.8.29: Exercises 2529 refer to the following definition
Solutions for Chapter 4.8: Application: Algorithms
Full solutions for Discrete Mathematics with Applications  4th Edition
ISBN: 9780495391326
Solutions for Chapter 4.8: Application: Algorithms
Get Full SolutionsSince 29 problems in chapter 4.8: Application: Algorithms have been answered, more than 44043 students have viewed full stepbystep solutions from this chapter. Discrete Mathematics with Applications was written by and is associated to the ISBN: 9780495391326. Chapter 4.8: Application: Algorithms includes 29 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4.

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!

Characteristic equation det(A  AI) = O.
The n roots are the eigenvalues of A.

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.

Column space C (A) =
space of all combinations of the columns of A.

Companion matrix.
Put CI, ... ,Cn in row n and put n  1 ones just above the main diagonal. Then det(A  AI) = ±(CI + c2A + C3A 2 + .•. + cnA nl  An).

Eigenvalue A and eigenvector x.
Ax = AX with x#O so det(A  AI) = o.

Elimination.
A sequence of row operations that reduces A to an upper triangular U or to the reduced form R = rref(A). Then A = LU with multipliers eO in L, or P A = L U with row exchanges in P, or E A = R with an invertible E.

Free columns of A.
Columns without pivots; these are combinations of earlier columns.

Identity matrix I (or In).
Diagonal entries = 1, offdiagonal entries = 0.

Independent vectors VI, .. " vk.
No combination cl VI + ... + qVk = zero vector unless all ci = O. If the v's are the columns of A, the only solution to Ax = 0 is x = o.

Left inverse A+.
If A has full column rank n, then A+ = (AT A)I AT has A+ A = In.

Lucas numbers
Ln = 2,J, 3, 4, ... satisfy Ln = L n l +Ln 2 = A1 +A~, with AI, A2 = (1 ± /5)/2 from the Fibonacci matrix U~]' Compare Lo = 2 with Fo = O.

Orthogonal matrix Q.
Square matrix with orthonormal columns, so QT = Ql. Preserves length and angles, IIQxll = IIxll and (QX)T(Qy) = xTy. AlllAI = 1, with orthogonal eigenvectors. Examples: Rotation, reflection, permutation.

Partial pivoting.
In each column, choose the largest available pivot to control roundoff; all multipliers have leij I < 1. See condition number.

Random matrix rand(n) or randn(n).
MATLAB creates a matrix with random entries, uniformly distributed on [0 1] for rand and standard normal distribution for randn.

Rank one matrix A = uvT f=. O.
Column and row spaces = lines cu and cv.

Row space C (AT) = all combinations of rows of A.
Column vectors by convention.

Sum V + W of subs paces.
Space of all (v in V) + (w in W). Direct sum: V n W = to}.

Transpose matrix AT.
Entries AL = Ajj. AT is n by In, AT A is square, symmetric, positive semidefinite. The transposes of AB and AI are BT AT and (AT)I.

Wavelets Wjk(t).
Stretch and shift the time axis to create Wjk(t) = woo(2j t  k).