 5.4.1E: Trace Algorithm 1 when it is given n = 5 as input. That is, show al...
 5.4.2E: Trace Algorithm 1 when it is given n = 6 as input. That is, show al...
 5.4.3E: Trace Algorithm 3 when it finds gcd(8,13). That is. show all the st...
 5.4.4E: Trace Algorithm 3 when it finds gcd(12. 17). That is. show all the ...
 5.4.5E: Trace Algorithm 4 when it is given m = 5, n = 11, and b = 3 as inpu...
 5.4.6E: Trace Algorithm 4 when it is given m =7, n = 10, and b = 2 as input...
 5.4.7E: Give a recursive algorithm for computing nx whenever n is a positiv...
 5.4.8E: Give a recursive algorithm for finding the sum of the first n posit...
 5.4.9E: Give a recursive algorithm for finding the sum of the first n odd p...
 5.4.10E: Give a recursive algorithm for finding the maximum of a finite set ...
 5.4.11E: Give a recursive algorithm for finding the minimum of a finite set ...
 5.4.13E: Give a recursive algorithm for finding n! mod m whenever n and m ar...
 5.4.14E: Give a recursive algorithm for finding a mode of a list of integers...
 5.4.15E: Devise a recursive algorithm for computing the greatest common divi...
 5.4.16E: Prove that the recursive algorithm for finding the sum of the first...
 5.4.17E: Describe a recursive algorithm for multiplying two non negative in...
 5.4.18E: Prove that Algorithm 1 for computing n! when n is a non negative i...
 5.4.19E: Prove that Algorithm 3 for computing gcd(a, b) when a and b are pos...
 5.4.20E: Prove that the algorithm you devised in Exercise 17 is correct.
 5.4.21E: Prove that the recursive algorithm that you found in Exercise 7 is ...
 5.4.22E: Prove that the recursive algorithm that you found in Exercise 10 is...
 5.4.23E: Devise a recursive algorithm for computing n2 where n is a nonnegat...
 5.4.24E: Devise a recursive algorithm to find a2n, where a is a real number ...
 5.4.25E: How does the number of multiplications used by the algorithm in Exe...
 5.4.26E: Use the algorithm in Exercise 24 to devise an algorithm for evaluat...
 5.4.27E: How does the number of multiplications used by the algorithm in Exe...
 5.4.28E: How many additions are used by the recursive and iterative algorith...
 5.4.29E: Devise a recursive algorithm to find the n th term of the sequence ...
 5.4.30E: Devise an iterative algorithm to find the nth term of the sequence ...
 5.4.31E: Is the recursive or the iterative algorithm for finding the sequenc...
 5.4.32E: Devise a recursive algorithm to find the nth term of the sequence d...
 5.4.33E: Devise an iterative algorithm to find the 71th term of the sequence...
 5.4.34E: Is the recursive or the iterative algorithm for finding the sequenc...
 5.4.35E: Give iterative and recursive algorithms for finding the nth term of...
 5.4.36E: Give a recursive algorithm to find the number of partitions of a po...
 5.4.37E: Give a recursive algorithm for finding the reversal of a bit string...
 5.4.38E: Give a recursive algorithm for finding the string wi, the concatena...
 5.4.39E: Prove that the recursive algorithm for finding the reversal of a bi...
 5.4.40E: Prove that the recursive algorithm for finding the concatenation of...
 5.4.41E: Give a recursive algorithm for tiling a 2n × 2n checkerboard with o...
 5.4.43E: Give a recursive algorithm for computing values of the Ackermann fu...
 5.4.44E: Use a merge sort to sort 4,3,2,5, 1,8,7,6 into increasing order. Sh...
 5.4.45E: Use a merge sort to sort b, d, a, f, g, h, z, p, o, k into alphabet...
 5.4.46E: How many comparisons are required to merge these pairs of lists usi...
 5.4.47E: Show that for all positive integers m and n there are sorted lists ...
 5.4.48E: What is the least number of comparisons needed to merge any two lis...
 5.4.49E: Prove that the merge sort algorithm is correct.The quick sort is an...
 5.4.50E: Sort 3, 5, 7, 8, 1,9, 2, 4, 6 using the quick sort.
 5.4.51E: Let a1 ,a2 ,........an be a list of n distinct real numbers.How man...
 5.4.52E: Describe the quick sort algorithm using pseudocode.
 5.4.53E: What is the largest number of comparisons needed to order a list of...
 5.4.54E: What is the least number of comparisons needed to order a list of f...
 5.4.55E: Determine the worstcase complexity of the quick sort algorithm in ...
Solutions for Chapter 5.4: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 5.4
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. Chapter 5.4 includes 53 full stepbystep solutions. Since 53 problems in chapter 5.4 have been answered, more than 221052 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions.

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!

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

Column picture of Ax = b.
The vector b becomes a combination of the columns of A. The system is solvable only when b is in the column space C (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).

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

Dimension of vector space
dim(V) = number of vectors in any basis for V.

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.

Full column rank r = n.
Independent columns, N(A) = {O}, no free variables.

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

Hessenberg matrix H.
Triangular matrix with one extra nonzero adjacent diagonal.

Norm
IIA II. The ".e 2 norm" of A is the maximum ratio II Ax II/l1x II = O"max· Then II Ax II < IIAllllxll and IIABII < IIAIIIIBII and IIA + BII < IIAII + IIBII. Frobenius norm IIAII} = L La~. The.e 1 and.e oo norms are largest column and row sums of laij I.

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.

Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.

Saddle point of I(x}, ... ,xn ).
A point where the first derivatives of I are zero and the second derivative matrix (a2 II aXi ax j = Hessian matrix) is indefinite.

Similar matrices A and B.
Every B = MI AM has the same eigenvalues as A.

Triangle inequality II u + v II < II u II + II v II.
For matrix norms II A + B II < II A II + II B II·

Unitary matrix UH = U T = UI.
Orthonormal columns (complex analog of Q).

Vector addition.
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.

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