 7.3.7.3.1: How many comparisons are needed for a binary search in a set of 64 ...
 7.3.7.3.2: How many comparisons are needed to locate the maximum and minimum e...
 7.3.7.3.3: Multiply (1 1 1O)z and (101O)z using the fast multiplication algori...
 7.3.7.3.4: Express the fast multiplication algorithm in pseudocode
 7.3.7.3.5: Determine a value for the constant C in Example 4 and use it to est...
 7.3.7.3.6: How many operations are needed to mUltiply two 32 x 32 matrices usi...
 7.3.7.3.7: Suppose that fen) = f(n/3) + 1 when n is divisible by 3, and f(l) =...
 7.3.7.3.8: Suppose that fen) = 2f(n/2) + 3 when n is even, and f(1) = 5. Find ...
 7.3.7.3.9: Suppose that fen) = f(n/5) + 3n2 when n is divisible by 5, and f(l)...
 7.3.7.3.10: Find f(n) when n = 2k, where f satisfies the recurrence relation fe...
 7.3.7.3.11: Estimate the size of f in Exercise 10 if f is an increasing function.
 7.3.7.3.12: Find f(n) when n = 3k, where f satisfies the recurrence relation fe...
 7.3.7.3.13: Estimate the size of f in Exercise 12 if f is an increasing function.
 7.3.7.3.14: Suppose that there are n = 2k teams in an elimination tournament, w...
 7.3.7.3.15: How many rounds are in the elimination tournament described in Exer...
 7.3.7.3.16: Solve the recurrence relation for the number of rounds in the tourn...
 7.3.7.3.17: Suppose that the votes of n people for different candidates (where ...
 7.3.7.3.18: Suppose that each person in a group of n people votes for exactly t...
 7.3.7.3.19: a) Set up a divideandconquer recurrence relation for the number o...
 7.3.7.3.20: a) Set up a divideandconquer recurrence relation for: the number ...
 7.3.7.3.21: Suppose that the function f satisfies the recurrence relation fen) ...
 7.3.7.3.22: Suppose that the function f satisfies the recurrence relation fen) ...
 7.3.7.3.23: This exercise deals with the problem offinding the largest sum of c...
 7.3.7.3.24: Apply the algorithm described in Example 12 for finding the closest...
 7.3.7.3.25: Apply the algorithm described in Example 12 for finding the closest...
 7.3.7.3.26: Use pseudocode to describe the recursive algorithm for solving the ...
 7.3.7.3.27: Construct a variation of the algorithm described in Example 12 alon...
 7.3.7.3.28: Suppose someone picks a number x from a set of n numbers. A second ...
 7.3.7.3.29: Show that if a = bd and n is a power of b, then f(n) = f(l)nd + end...
 7.3.7.3.30: Use Exercise 29 to show that if a = bd, then f(n) is O(nd log n).
 7.3.7.3.31: Show that if a =1= bd and n is a power of b, then fen) = C]nd + C2n...
 7.3.7.3.32: Use Exercise 31 to show that if a < bd, then fen) is O(nd)
 7.3.7.3.33: Use Exercise 31 to show that if a> bd, then fen) is o (n]ogb a).
 7.3.7.3.34: Find f(n) when n = 4k, where f satisfies the recurrence relation f(...
 7.3.7.3.35: Estimate the size of f in Exercise 34 if f is an increasing function.
 7.3.7.3.36: Find f(n) when n = 2k, where f satisfies the recurrence relation f(...
 7.3.7.3.37: Estimate the size of f in Exercise 36 if f is an increasing function.
Solutions for Chapter 7.3: Advanced Counting Techniques
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 7.3: Advanced Counting Techniques
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6. Chapter 7.3: Advanced Counting Techniques includes 37 full stepbystep solutions. Since 37 problems in chapter 7.3: Advanced Counting Techniques have been answered, more than 38927 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720.

Associative Law (AB)C = A(BC).
Parentheses can be removed to leave ABC.

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

Complete solution x = x p + Xn to Ax = b.
(Particular x p) + (x n in nullspace).

Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then SI 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 Fn1c can be computed with ne/2 multiplications. Revolutionary.

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

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

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

lAII = l/lAI and IATI = IAI.
The big formula for det(A) has a sum of n! terms, the cofactor formula uses determinants of size n  1, volume of box = I det( A) I.

Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

Normal equation AT Ax = ATb.
Gives the least squares solution to Ax = b if A has full rank n (independent columns). The equation says that (columns of A)·(b  Ax) = o.

Pivot columns of A.
Columns that contain pivots after row reduction. These are not combinations of earlier columns. The pivot columns are a basis for the column space.

Positive definite matrix A.
Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.

Pseudoinverse A+ (MoorePenrose 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).

Reduced row echelon form R = rref(A).
Pivots = 1; zeros above and below pivots; the r nonzero rows of R give a basis for the row space of A.

Spanning set.
Combinations of VI, ... ,Vm fill the space. The columns of A span C (A)!

Spectrum of A = the set of eigenvalues {A I, ... , An}.
Spectral radius = max of IAi I.

Stiffness matrix
If x gives the movements of the nodes, K x gives the internal forces. K = ATe A where C has spring constants from Hooke's Law and Ax = stretching.

Vandermonde matrix V.
V c = b gives coefficients of p(x) = Co + ... + Cn_IXn 1 with P(Xi) = bi. Vij = (Xi)jI and det V = product of (Xk  Xi) for k > i.