 3.3.28E: Analyze the worstcase time complexity of the algorithm you devised...
 3.3.1E: Give a bigO estimate for the number of operations (where an operat...
 3.3.2E: Give a bigO estimate for the number additions used in this segment...
 3.3.3E: Give a bigO estimate for the number of operations, where an operat...
 3.3.4E: Give a bigO 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 bigO 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 + an1x...
 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 averagecase 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 worstcase time complexity, measured in terms of compa...
 3.3.26E: Describe the worstcase time complexity, measured in terms of compa...
 3.3.27E: Analyze the worstcase time complexity of the algorithm you devised...
 3.3.29E: Analyze the worstcase time complexity of the algorithm you devised...
 3.3.30E: Analyze the worstcase time complexity of the algorithm you devised...
 3.3.31E: Analyze the worstcase time complexity of the algorithm you devised...
 3.3.32E: Determine the worstcase complexity in terms of comparisons of the ...
 3.3.33E: Determine the worstcase 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 bigO estimate for the worstcase 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 bruteforce 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
Solutions for Chapter 3.3
Get Full SolutionsThis 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: 7. 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 164551 students have viewed full stepbystep solutions from this chapter. Chapter 3.3 includes 44 full stepbystep solutions.

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!

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

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

Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.

Fourier matrix F.
Entries Fjk = e21Cijk/n give orthogonal columns FT F = nI. Then y = Fe is the (inverse) Discrete Fourier Transform Y j = L cke21Cijk/n.

Hypercube matrix pl.
Row n + 1 counts corners, edges, faces, ... of a cube in Rn.

Indefinite matrix.
A symmetric matrix with eigenvalues of both signs (+ and  ).

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.

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

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.

Nullspace matrix N.
The columns of N are the n  r special solutions to As = O.

Orthogonal subspaces.
Every v in V is orthogonal to every w in W.

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.

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

Rotation matrix
R = [~ CS ] rotates the plane by () and R 1 = RT rotates back by (). Eigenvalues are eiO and eiO , eigenvectors are (1, ±i). c, s = cos (), sin ().

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Singular Value Decomposition
(SVD) A = U:E VT = (orthogonal) ( diag)( orthogonal) First r columns of U and V are orthonormal bases of C (A) and C (AT), AVi = O'iUi with singular value O'i > O. Last columns are orthonormal bases of nullspaces.

Solvable system Ax = b.
The right side b is in the column space of A.

Spectral Theorem A = QAQT.
Real symmetric A has real A'S and orthonormal q's.

Subspace S of V.
Any vector space inside V, including V and Z = {zero vector only}.