 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 133224 students have viewed full stepbystep solutions from this chapter.

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

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!

Big formula for n by n determinants.
Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or  sign.

CayleyHamilton Theorem.
peA) = det(A  AI) has peA) = zero matrix.

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

Companion matrix.
Put CI, ... ,Cn in row n and put n  1 ones just above the main diagonal. Then det(A  AI) = ±(CI + c2A + C3A 2 + .•. + cnA nl  An).

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.

Cross product u xv in R3:
Vector perpendicular to u and v, length Ilullllvlll sin el = area of parallelogram, u x v = "determinant" of [i j k; UI U2 U3; VI V2 V3].

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.

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.

Hilbert matrix hilb(n).
Entries HU = 1/(i + j 1) = Jd X i 1 xj1dx. Positive definite but extremely small Amin and large condition number: H is illconditioned.

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

Partial pivoting.
In each column, choose the largest available pivot to control roundoff; all multipliers have leij I < 1. See condition number.

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

Projection matrix P onto subspace S.
Projection p = P b is the closest point to b in S, error e = b  Pb is perpendicularto S. p 2 = P = pT, eigenvalues are 1 or 0, eigenvectors are in S or S...L. If columns of A = basis for S then P = A (AT A) 1 AT.

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

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.

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