 3.1.1E: List all the steps used by Algorithm I to find the maximum of the l...
 3.1.2E: ?2E Determine which characteristics of an algorithm described in th...
 3.1.3E: ?3E Devise an algorithm that finds the sum of all the integers in a...
 3.1.4E: Describe an algorithm that takes as input a list of n integers and ...
 3.1.5E: Describe an algorithm that takes as input a list of n integers in n...
 3.1.6E: Describe an algorithm that takes as input a list of n integers and ...
 3.1.7E: Describe an algorithm that takes as input a list of n integers and ...
 3.1.8E: Describe an algorithm that takes as input a list of n distinct inte...
 3.1.9E: A palindrome is a string that reads the same forward and backward. ...
 3.1.11E: ?11E Describe an algorithm that interchanges the values of the vari...
 3.1.12E: Describe an algorithm that uses only assignment statements that rep...
 3.1.13E: ?13E List all the steps used to search for 9 in the sequence 1, 3, ...
 3.1.14E: List all the steps used to search for 7 in the sequence given in Ex...
 3.1.15E: Describe an algorithm that inserts an integer x in the appropriate ...
 3.1.16E: Describe an algorithm for finding the smallest integer in a finite ...
 3.1.17E: Describe an algorithm that locates the first occurrence of the larg...
 3.1.18E: Describe an algorithm that locates the last occurrence of the small...
 3.1.19E: Describe an algorithm that produces the maximum, median, mean, and ...
 3.1.20E: Describe an algorithm for finding both the largest and the smallest...
 3.1.21E: Describe an algorithm that puts the first three terms of a sequence...
 3.1.22E: Describe an algorithm to find the longest word in an English senten...
 3.1.23E: Describe an algorithm that determines whether a function from a fin...
 3.1.24E: Describe an algorithm that determines whether a function from a fin...
 3.1.25E: Describe an algorithm that will count the number of 1s in a bit str...
 3.1.26E: Change Algorithm 3 so that the binary search procedure compares x t...
 3.1.27E: The ternary search algorithm locates an element in a list of increa...
 3.1.28E: Specify the steps of an algorithm that locates an element in a list...
 3.1.29E: Devise an algorithm that finds a mode in a list of nondecreasing in...
 3.1.30E: Devise an algorithm that finds all modes. (Recall that a list of in...
 3.1.31E: Devise an algorithm that finds the first term of a sequence of inte...
 3.1.32E: In a list of elements the same elements may appear several times. A...
 3.1.33E: Devise an algorithm that finds the first term of a sequence of posi...
 3.1.34E: ?34E Use the bubble sort to sort 6, 2.3, 1, 5, 4, showing the lists...
 3.1.35E: ?35E Use the bubble sort to sort 3, 1,5, 7, 4. showing the lists ob...
 3.1.36E: Use the bubble sort to sort d, f, k, m, a, b, showing the lists obt...
 3.1.37E: Adapt the bubble sort algorithm so that it stops when no interchang...
 3.1.38E: ?38E Use the insertion sort to sort the list in Exercise 34, showin...
 3.1.39E: Use the insertion sort to sort the list in Exercise 35, showing the...
 3.1.40E: Use the insertion sort to sort the list in Exercise 36, showing the...
 3.1.41E: Sort these lists using the selection sort.a) 3, 5, 4, 1, 2_________...
 3.1.42E: ?42E Write the selection sort algorithm in pseudocode.
 3.1.43E: Describe an algorithm based on the linear search for determining th...
 3.1.44E: ?44E Describe an algorithm based on the binary search for determini...
 3.1.45E: How many comparisons does the insertion sort use to sort the list 1...
 3.1.46E: How many comparisons does the insertion sort use to sort the list n...
 3.1.47E: Show all the steps used by the binary insertion sort to son the lis...
 3.1.48E: Compare the number of comparisons used by the insertion sort and th...
 3.1.49E: Express the binary insertion sort in pseudocode.
 3.1.50E: The binary insertion sort is a variation of the insertion sort that...
 3.1.51E: When a list of elements is in close to the correct order, would it ...
 3.1.52E: ?52E Use the greedy algorithm to make change using quarters, dimes,...
 3.1.53E: Use the greedy algorithm to make change using quarters, dimes, nick...
 3.1.54E: Use the greedy algorithm to make change using quarters, dimes, and ...
 3.1.55E: Use the greedy algorithm to make change using quarters. dimes, and ...
 3.1.57E: Use Algorithm 7 to schedule the largest number of talks in a lectur...
 3.1.58E: Show that a greedy algorithm that schedules talks in a lecture hall...
 3.1.59E: a) Devise a greedy algorithm that determines the fewest lecture hal...
 3.1.60E: Suppose we have three men m1, m2, and m3 and three women w1, w2, an...
 3.1.61E: Write the deferred acceptance algorithm in pseudocode.
 3.1.62E: Show that the deferred acceptance algorithm terminates.
 3.1.63E: Show that the deferred acceptance always terminates with a stable a...
 3.1.65E: Show that the following problem is solvable. Given two programs wit...
 3.1.66E: Show that the problem of deciding whether a specific program with a...
Solutions for Chapter 3.1: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 3.1
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 3.1 includes 63 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions. Since 63 problems in chapter 3.1 have been answered, more than 163914 students have viewed full stepbystep solutions from this chapter.

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

Augmented matrix [A b].
Ax = b is solvable when b is in the column space of A; then [A b] has the same rank as A. Elimination on [A b] keeps equations correct.

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

Diagonalization
A = S1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k SI.

Exponential eAt = I + At + (At)2 12! + ...
has derivative AeAt; eAt u(O) solves u' = Au.

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

Incidence matrix of a directed graph.
The m by n edgenode incidence matrix has a row for each edge (node i to node j), with entries 1 and 1 in columns i and j .

Kronecker product (tensor product) A ® B.
Blocks aij B, eigenvalues Ap(A)Aq(B).

Left inverse A+.
If A has full column rank n, then A+ = (AT A)I AT has A+ A = In.

Linearly dependent VI, ... , Vn.
A combination other than all Ci = 0 gives L Ci Vi = O.

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.

Multiplicities AM and G M.
The algebraic multiplicity A M of A is the number of times A appears as a root of det(A  AI) = O. The geometric multiplicity GM is the number of independent eigenvectors for A (= dimension of the eigenspace).

Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.

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.

Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.

Schur complement S, D  C A } B.
Appears in block elimination on [~ g ].

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

Skewsymmetric matrix K.
The transpose is K, since Kij = Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.

Standard basis for Rn.
Columns of n by n identity matrix (written i ,j ,k in R3).

Toeplitz matrix.
Constant down each diagonal = timeinvariant (shiftinvariant) filter.