- 3.3.28E: Analyze the worst-case time complexity of the algorithm you devised...
- 3.3.1E: Give a big-O estimate for the number of operations (where an operat...
- 3.3.2E: Give a big-O estimate for the number additions used in this segment...
- 3.3.3E: Give a big-O estimate for the number of operations, where an operat...
- 3.3.4E: Give a big-O estimate for the number of operations, where an operat...
- 3.3.5E: How many comparisons are used by the algorithm given in Exercise 16...
- 3.3.6E: a) Use pseudocode to describe the algorithm that puts the first fou...
- 3.3.7E: Suppose that an element is known to be among the first four element...
- 3.3.9E: Give a big-O estimate for the number of comparisons used by the alg...
- 3.3.10E: a) Show that this algorithm determines the number of 1 bits in the ...
- 3.3.11E: a) Suppose we have n subsets S1. S2,…, Sn of the set {1, 2, …, n}. ...
- 3.3.12E: Consider the following algorithm, which takes as input a sequence o...
- 3.3.13E: The conventional algorithm for evaluating a polynomial anxn + an-1x...
- 3.3.14E: There is a more efficient algorithm (in terms of the number of mult...
- 3.3.15E: What is the largest n for which one can solve within one second u p...
- 3.3.16E: What is the largest n for which one can solve within a day using an...
- 3.3.17E: What is the largest n for which one can solve within a minute using...
- 3.3.18E: How much time does an algorithm take to solve a problem of size n i...
- 3.3.19E: How much time does an algorithm using 250 operations need if each o...
- 3.3.20E: What is the effect in the time required to solve a problem when you...
- 3.3.21E: What is the effect in the time required to solve a problem when you...
- 3.3.23E: Analyze the average-case performance of the linear search algorithm...
- 3.3.24E: An algorithm is called optimal for the solution of a problem with r...
- 3.3.25E: Describe the worst-case time complexity, measured in terms of compa...
- 3.3.26E: Describe the worst-case time complexity, measured in terms of compa...
- 3.3.27E: Analyze the worst-case time complexity of the algorithm you devised...
- 3.3.29E: Analyze the worst-case time complexity of the algorithm you devised...
- 3.3.30E: Analyze the worst-case time complexity of the algorithm you devised...
- 3.3.31E: Analyze the worst-case time complexity of the algorithm you devised...
- 3.3.32E: Determine the worst-case complexity in terms of comparisons of the ...
- 3.3.33E: Determine the worst-case complexity in terms of comparisons of the ...
- 3.3.34E: How many comparisons does the selection sort (see preamble to Exerc...
- 3.3.35E: Find a big-O estimate for the worst-case complexity in terms of num...
- 3.3.36E: Show that the greedy algorithm for making change for n cents using ...
- 3.3.37E: Find the complexity of a brute-force algorithm for scheduling the t...
- 3.3.38E: Find the complexity of the greedy algorithm for scheduling the most...
- 3.3.39E: Describe how the number of comparisons used in the worst case chang...
- 3.3.40E: Describe how the number of comparisons used in the worst case chang...
- 3.3.41E: An n x n matrix is called upper triangular if aij = 0 whenever i > ...
- 3.3.42E: Give a pseudocode description of the algorithm in Exercise 41 for m...
- 3.3.43E: An matrix is called upper triangular if whenever .How many multipli...
- 3.3.44E: What is the best order to form the product ABC if A, B, and C are m...
- 3.3.45E: What is the best order to form the product ABCD if A, B, C. and D a...
- 3.3.46E: In this exercise we deal with the problem of string matching.a) Exp...
Solutions for Chapter 3.3: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications | 7th Edition
ISBN: 9780073383095
This expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7th. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. Since 44 problems in chapter 3.3 have been answered, more than 101518 students have viewed full step-by-step solutions from this chapter. Chapter 3.3 includes 44 full step-by-step 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).
-
Affine transformation
Tv = Av + Vo = linear transformation plus shift.
-
Diagonalization
A = S-1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k S-I.
-
Distributive Law
A(B + C) = AB + AC. Add then multiply, or mUltiply then add.
-
Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra -eij in the i, j entry (i #- j). Then Eij A subtracts eij times row j of A from row i.
-
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.
-
Fibonacci numbers
0,1,1,2,3,5, ... satisfy Fn = Fn-l + Fn- 2 = (A7 -A~)I()q -A2). Growth rate Al = (1 + .J5) 12 is the largest eigenvalue of the Fibonacci matrix [ } A].
-
Four Fundamental Subspaces C (A), N (A), C (AT), N (AT).
Use AT for complex A.
-
Free variable Xi.
Column i has no pivot in elimination. We can give the n - r free variables any values, then Ax = b determines the r pivot variables (if solvable!).
-
Identity matrix I (or In).
Diagonal entries = 1, off-diagonal entries = 0.
-
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).
-
Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.
-
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+ (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).
-
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.
-
Row space C (AT) = all combinations of rows of A.
Column vectors by convention.
-
Similar matrices A and B.
Every B = M-I AM has the same eigenvalues as A.
-
Spectrum of A = the set of eigenvalues {A I, ... , An}.
Spectral radius = max of IAi I.
-
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·
-
Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.