 3.SE.1E: a) Describe an algorithm for locating the last occurrence of the la...
 3.SE.2E: ?2E a) Describe an algorithm for finding the first and second large...
 3.SE.3E: ?3E a) Give an algorithm to determine whether a bit string contains...
 3.SE.4E: ?4E a)??Suppose that a list contains integers that are in order of ...
 3.SE.5E: ?5E a) Adapt Algorithm I in Section 3.1 to find the maximum and the...
 3.SE.6E: a) Describe in detail (and in English) the steps of an algorithm th...
 3.SE.7E: ?7E Show that the worstcase complexity in terms of comparisons of ...
 3.SE.8E: ?8E Devise an efficient algorithm for finding the second largest el...
 3.SE.9E: Devise an algorithm that finds all equal pairs of sums of two terms...
 3.SE.10E: ?10E Devise an algorithm that finds the closest pair of integers in...
 3.SE.11E: ?11E Show the steps used by the shaker sort to sort the list 3, 5, ...
 3.SE.12E: Express the shaker sort in pseudocode.
 3.SE.13E: ?13E Show that the shaker sort has ?O (?n?2) complexity measured in...
 3.SE.14E: Explain why the shaker sort is efficient for sorting lists that are...
 3.SE.15E: ?15E Show that (n ? ? log ?n? + ?n?2)3 is ?? ).n
 3.SE.16E: Show that 8x3 + 12x + 100 logx is O(x3).
 3.SE.17E: ?17E Give a big?O? estimate for (x ? ?2 + ?? log?? 3) • (2? ? + ?x...
 3.SE.18E: ?18E Find a big?O? estimate for
 3.SE.19E: ?19E Show that ?x! ? is not O? ?(2?? .
 3.SE.20E: The Shaker sort or (bidirectional bubble sort) successively compare...
 3.SE.21E: Find all pairs of functions of the same order in this list of funct...
 3.SE.22E: Find all pairs of functions of the same order in this list of funct...
 3.SE.23E: Find an integer n with n > 2 for which
 3.SE.24E: Find an integer n with n > 2 for which
 3.SE.25E: ?25E Arrange the functions n ? n?, (log?? 2, ?n?l.0001, (1.0001)?n,...
 3.SE.26E: Arrange the function 2100n. , nlogn, n log n log log n, n3/2, n(log...
 3.SE.27E: ?27E Give an example of two increasing functions ?f?(?n?) and ?g?(?...
 3.SE.28E: Show that if the denominations of coins are c0, c1,…,ck, where k is...
 3.SE.29E: ?29E a) Use pseudocode to specify a bruteforce algorithm that dete...
 3.SE.30E: ?30E a) Devise a more efficient algorithm for solving the problem d...
 3.SE.31E: Find all valid partners for each man and each woman if there are th...
 3.SE.32E: Show that the deferred acceptance algorithm given in the preamble t...
 3.SE.33E: ?33E Define what it means for a matching to be female optimal and f...
 3.SE.34E: ?34E Show that when woman do the proposing in the deferred acceptan...
 3.SE.35E: In this exercise we consider matching problems where there may be d...
 3.SE.36E: In this exercise we consider matching problems where some manwoman...
 3.SE.37E: ?37E Suppose we have five jobs with specified required times and de...
 3.SE.38E: The slackness of a job requiring time t and with deadline d is d — ...
 3.SE.39E: ?39E Find an example that shows that scheduling jobs in order of in...
 3.SE.40E: Prove that scheduling jobs in order of increasing deadlines always ...
 3.SE.41E: Suppose that we have a knapsack with total capacity of w kg. We als...
 3.SE.42E: ?42E Suppose we have three processors and five jobs requiring times...
 3.SE.43E: ?43E Suppose that ?L* is the minimum makespan when ?p processors ar...
 3.SE.44E: ?44E Write out in pseudocode the greedy algorithm that goes through...
 3.SE.45E: ?45E Run the algorithm from Exercise 44 on the input given in Exerc...
 3.SE.46E: Prove that the algorithm from Exercise 44 is a 2 approximation alg...
Solutions for Chapter 3.SE: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 3.SE
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Chapter 3.SE includes 46 full stepbystep solutions. Since 46 problems in chapter 3.SE have been answered, more than 187728 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: 9780073383095.

Affine transformation
Tv = Av + Vo = linear transformation plus shift.

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

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

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

Diagonal matrix D.
dij = 0 if i # j. Blockdiagonal: zero outside square blocks Du.

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.

Fundamental Theorem.
The nullspace N (A) and row space C (AT) are orthogonal complements in Rn(perpendicular from Ax = 0 with dimensions rand n  r). Applied to AT, the column space C(A) is the orthogonal complement of N(AT) in Rm.

Hankel matrix H.
Constant along each antidiagonal; hij depends on i + j.

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

Iterative method.
A sequence of steps intended to approach the desired solution.

Kirchhoff's Laws.
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.

Linear transformation T.
Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.

Markov matrix M.
All mij > 0 and each column sum is 1. Largest eigenvalue A = 1. If mij > 0, the columns of Mk approach the steady state eigenvector M s = s > O.

Outer product uv T
= column times row = rank one matrix.

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

Reflection matrix (Householder) Q = I 2uuT.
Unit vector u is reflected to Qu = u. All x intheplanemirroruTx = o have Qx = x. Notice QT = Q1 = Q.

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.

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

Vector v in Rn.
Sequence of n real numbers v = (VI, ... , Vn) = point in Rn.