 2.3.1: Let Q: x2 > x + 1 where x is a positive integer. Assume that Q is t...
 2.3.2: Let Q: x! > 3x where x is a positive integer. Assume that Q is true...
 2.3.3: Let Q: x2 > x + 1 where x is a positive integer. Assume that Q is t...
 2.3.4: Function to return the value of x 2 for x 1. Square (positive integ...
 2.3.5: Function to return the value of x y for x, y 1. Power (positive int...
 2.3.6: Function to compute and write out quotient q and remainder r when x...
 2.3.7: For Exercises 712 use the Euclidean algorithm to find the greatest ...
 2.3.8: For Exercises 712 use the Euclidean algorithm to find the greatest ...
 2.3.9: For Exercises 712 use the Euclidean algorithm to find the greatest ...
 2.3.10: For Exercises 712 use the Euclidean algorithm to find the greatest ...
 2.3.11: For Exercises 712 use the Euclidean algorithm to find the greatest ...
 2.3.12: For Exercises 712 use the Euclidean algorithm to find the greatest ...
 2.3.13: Following is the problem posed at the beginning of this chapter. Th...
 2.3.14: Concerning the question posed in Exercise 13: a. Use the Euclidean ...
 2.3.15: In Exercises 1521, prove that the program segment is correct by fin...
 2.3.16: In Exercises 1521, prove that the program segment is correct by fin...
 2.3.17: In Exercises 1521, prove that the program segment is correct by fin...
 2.3.18: In Exercises 1521, prove that the program segment is correct by fin...
 2.3.19: In Exercises 1521, prove that the program segment is correct by fin...
 2.3.20: In Exercises 1521, prove that the program segment is correct by fin...
 2.3.21: In Exercises 1521, prove that the program segment is correct by fin...
 2.3.22: Following are four functions intended to return the value a[1] + a[...
 2.3.23: To prove that if both a and b are even, then gcd(a, b) = 2gcd(a/2, ...
 2.3.24: To prove that if a is even and b is odd, then gcd(a, b) = gcd(a/2, ...
 2.3.25: We want to prove that if a and b are both odd, and a b, then gcd(a,...
 2.3.26: To find gcd(420, 66) using the binary GCD algorithm takes the follo...
 2.3.27: Use the binary GCD algorithm to find gcd(308, 165) [see Exercise 7]
 2.3.28: Use the binary GCD algorithm to find gcd(2420, 70) [see Exercise 8]
Solutions for Chapter 2.3: More on Proof of Correctness
Full solutions for Mathematical Structures for Computer Science  7th Edition
ISBN: 9781429215107
Solutions for Chapter 2.3: More on Proof of Correctness
Get Full SolutionsChapter 2.3: More on Proof of Correctness includes 28 full stepbystep solutions. Since 28 problems in chapter 2.3: More on Proof of Correctness have been answered, more than 18916 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Mathematical Structures for Computer Science, edition: 7. Mathematical Structures for Computer Science was written by and is associated to the ISBN: 9781429215107.

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

Back substitution.
Upper triangular systems are solved in reverse order Xn to Xl.

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

Conjugate Gradient Method.
A sequence of steps (end of Chapter 9) to solve positive definite Ax = b by minimizing !x T Ax  x Tb over growing Krylov subspaces.

Dimension of vector space
dim(V) = number of vectors in any basis for V.

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.

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.

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

Hermitian matrix A H = AT = A.
Complex analog a j i = aU of a symmetric matrix.

Jordan form 1 = M 1 AM.
If A has s independent eigenvectors, its "generalized" eigenvector matrix M gives 1 = diag(lt, ... , 1s). The block his Akh +Nk where Nk has 1 's on diagonall. Each block has one eigenvalue Ak and one eigenvector.

Krylov subspace Kj(A, b).
The subspace spanned by b, Ab, ... , AjIb. Numerical methods approximate A I b by x j with residual b  Ax j in this subspace. A good basis for K j requires only multiplication by A at each step.

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.

Network.
A directed graph that has constants Cl, ... , Cm associated with the edges.

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

Permutation matrix P.
There are n! orders of 1, ... , n. The n! P 's have the rows of I in those orders. P A puts the rows of A in the same order. P is even or odd (det P = 1 or 1) based on the number of row exchanges to reach I.

Rayleigh quotient q (x) = X T Ax I x T x for symmetric A: Amin < q (x) < Amax.
Those extremes are reached at the eigenvectors x for Amin(A) and Amax(A).

Row picture of Ax = b.
Each equation gives a plane in Rn; the planes intersect at x.

Spectrum of A = the set of eigenvalues {A I, ... , An}.
Spectral radius = max of IAi I.

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

Vector addition.
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.