 3.6.3.6.1: Convert these integers from decimal notation to binary notation. a)...
 3.6.3.6.2: Convert these integers from decimal notation to binary notation. a)...
 3.6.3.6.3: Convert these integers from binary notation to decimal notation. a)...
 3.6.3.6.4: Convert these integers from binary notation to decimal notation. a)...
 3.6.3.6.5: Convert these integers from hexadecimal notation to binary notation...
 3.6.3.6.6: Convert (BADFACED)1 6 from its hexadecimal expansion to its binary ...
 3.6.3.6.7: Convert (ABCDEF)1 6 from its hexadecimal expansion to its binary ex...
 3.6.3.6.8: Convert each of these integers from binary notation to hexadecimal ...
 3.6.3.6.9: Convert (101 1 0 1 11 IOI lh from its binary expansion to its hexad...
 3.6.3.6.10: Convert (1 1000 0110 001 1h from its binary expansion to its hexade...
 3.6.3.6.11: Show that the hexadecimal expansion of a positive integer can be ob...
 3.6.3.6.12: Show that the binary expansion of a positive integer can be obtaine...
 3.6.3.6.13: Give a simple procedure for converting from the binary expansion of...
 3.6.3.6.14: Give a simple procedure for converting from the octal expansion of ...
 3.6.3.6.15: Convert (734532 1 )8 to its binary expansion and (10 10 11 101 1 )2...
 3.6.3.6.16: Give a procedure for converting from the hexadecimal expansion of a...
 3.6.3.6.17: Give a procedure for converting from the octal expansion of an inte...
 3.6.3.6.18: Convert ( 12345670)8 to its hexadecimal expansion and (ABB093BABBA)...
 3.6.3.6.19: Use Algorithm 5 to find 7644 mod 645.
 3.6.3.6.20: Use Algorithm 5 to find 1 1644 mod 645.
 3.6.3.6.21: Use Algorithm 5 to find 32003 mod 99.
 3.6.3.6.22: Use Algorithm 5 to find 123 1001 mod 101.
 3.6.3.6.23: Use the Euclidean algorithm to find a) gcd(12, 1 8). b) gcd( 1 11, ...
 3.6.3.6.24: Use the Euclidean algorithm to find a) gcd(I, 5). b) gcd(100, 101)....
 3.6.3.6.25: How many divisions are required to find gcd(2 1 , 34) using the Euc...
 3.6.3.6.26: How many divisions are required to find gcd(34, 55) using the Eucli...
 3.6.3.6.27: Show that every positive integer can be represented uniquely as the...
 3.6.3.6.28: It can be shown that every integer can be uniquely represented in t...
 3.6.3.6.29: Show that a positive integer is divisible by 3 if and only if the s...
 3.6.3.6.30: Show that a positive integer is divisible by 11 if and only if the ...
 3.6.3.6.31: Show that a positive integer is divisible by 3 if and only if the d...
 3.6.3.6.32: Find the one's complement representations, using bit strings of len...
 3.6.3.6.33: What integer does each of the following one's complement representa...
 3.6.3.6.34: If m is a positive integer less than 2 n l, how is the one's compl...
 3.6.3.6.35: How is the one's complement representation of the sum of two intege...
 3.6.3.6.36: How is the one's complement representation ofthe difference of two ...
 3.6.3.6.37: Show that the integer m with one's complement representation (anI ...
 3.6.3.6.38: Answer Exercise 32, but this time find the two's complement expansi...
 3.6.3.6.39: Answer Exercise 33 if each expansion is a two's complement expansio...
 3.6.3.6.40: Answer Exercise 34 for two's complement expansions.
 3.6.3.6.41: Answer Exercise 35 for two's complement expansions
 3.6.3.6.42: Answer Exercise 36 for two's complement expansions.
 3.6.3.6.43: Show that the integer m with two's complement representation (anl a...
 3.6.3.6.44: Give a simple algorithm for forming the two's complement representa...
 3.6.3.6.45: Sometimes integers are encoded by using fourdigit binary expansion...
 3.6.3.6.46: Find the Cantor expansions of a) 2. b) 7. c) 1 9. d) 87. e) 1000. t...
 3.6.3.6.47: Describe an algorithm that finds the Cantor expansion of an integer.
 3.6.3.6.48: Describe an algorithm to add two integers from their Cantor expansi...
 3.6.3.6.49: Add (101 1 1) 2 and ( 1 1010) 2 by working through each step of the...
 3.6.3.6.50: Multiply (1 1 1O)z and (101O)z by working through each step of the ...
 3.6.3.6.51: Describe an algorithm for finding the difference of two binary expa...
 3.6.3.6.52: Estimate the number of bit operations used to subtract two binary e...
 3.6.3.6.53: Devise an algorithm that, given the binary expansions of the intege...
 3.6.3.6.54: How many bit operations does the comparison algorithm from Exercise...
 3.6.3.6.55: Estimate the complexity of Algorithm 1 for finding the base b expan...
 3.6.3.6.56: Show that Algorithm 5 uses O((log mi 10g n) bit operations to find ...
 3.6.3.6.57: Show that Algorithm 4 uses O(q log a) bit operations, assuming that...
Solutions for Chapter 3.6: The Fundamentals: Algorithms, the Integers, and Matrices
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 3.6: The Fundamentals: Algorithms, the Integers, and Matrices
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6. Chapter 3.6: The Fundamentals: Algorithms, the Integers, and Matrices includes 57 full stepbystep solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720. Since 57 problems in chapter 3.6: The Fundamentals: Algorithms, the Integers, and Matrices have been answered, more than 36144 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions.

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

Cramer's Rule for Ax = b.
B j has b replacing column j of A; x j = det B j I det A

Determinant IAI = det(A).
Defined by det I = 1, sign reversal for row exchange, and linearity in each row. Then IAI = 0 when A is singular. Also IABI = IAIIBI and

Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then SI AS = A = eigenvalue matrix.

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.

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

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

Inverse matrix AI.
Square matrix with AI A = I and AAl = I. No inverse if det A = 0 and rank(A) < n and Ax = 0 for a nonzero vector x. The inverses of AB and AT are B1 AI and (AI)T. Cofactor formula (Al)ij = Cji! detA.

Least squares solution X.
The vector x that minimizes the error lie 112 solves AT Ax = ATb. Then e = b  Ax is orthogonal to all columns of A.

Length II x II.
Square root of x T x (Pythagoras in n dimensions).

Minimal polynomial of A.
The lowest degree polynomial with meA) = zero matrix. This is peA) = det(A  AI) if no eigenvalues are repeated; always meA) divides peA).

Normal matrix.
If N NT = NT N, then N has orthonormal (complex) eigenvectors.

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

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

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

Row space C (AT) = all combinations of rows of A.
Column vectors by convention.

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

Simplex method for linear programming.
The minimum cost vector x * is found by moving from comer to lower cost comer along the edges of the feasible set (where the constraints Ax = b and x > 0 are satisfied). Minimum cost at a comer!

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.

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