ISBN9780073383095
Solutions for Chapter 3.1: Cardinality of Sets
3.1.3E) ?3E Devise an algorithm that finds the sum of all the integers in a list.
3.1.34E) ?34E Use the bubble sort to sort 6, 2.3, 1, 5, 4, showing the lists obtained at each step.
3.1.35E) ?35E Use the bubble sort to sort 3, 1,5, 7, 4. showing the lists obtained at each step.
3.1.36E) Use the bubble sort to sort d, f, k, m, a, b, showing the lists obtained at each step.
3.1.42E) ?42E Write the selection sort algorithm in pseudocode.
3.1.45E) How many comparisons does the insertion sort use to sort the list 1, 2, …, n?
3.1.47E) Show all the steps used by the binary insertion sort to son the list 3, 2, 4, 5, 1, 6.
3.1.49E) Express the binary insertion sort in pseudocode.
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 assignment.
Summary of Chapter 3.1: Cardinality of Sets
The concepts developed in this section have important applications to computer science. A function is called uncomputable if no computer program can be written to find all its values, even with unlimited time and memory.
This 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: Cardinality of Sets includes 63 full step-by-step solutions. This expansive textbook survival guide covers the following chapters and their solutions. Since 63 problems in chapter 3.1: Cardinality of Sets have been answered, more than 892784 students have viewed full step-by-step solutions from this chapter.
-
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.
-
Characteristic equation det(A - AI) = O.
The n roots are the eigenvalues of A.
-
Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.
-
Column space C (A) =
space of all combinations of the columns of A.
-
Cyclic shift
S. Permutation with S21 = 1, S32 = 1, ... , finally SIn = 1. Its eigenvalues are the nth roots e2lrik/n of 1; eigenvectors are columns of the Fourier matrix F.
-
Diagonalization
A = S-1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k S-I.
-
Distributive Law
A(B + C) = AB + AC. Add then multiply, or mUltiply then add.
-
Fast Fourier Transform (FFT).
A factorization of the Fourier matrix Fn into e = log2 n matrices Si times a permutation. Each Si needs only nl2 multiplications, so Fnx and Fn-1c can be computed with ne/2 multiplications. Revolutionary.
-
Full row rank r = m.
Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.
-
Gauss-Jordan method.
Invert A by row operations on [A I] to reach [I A-I].
-
Hermitian matrix A H = AT = A.
Complex analog a j i = aU of a symmetric matrix.
-
Hessenberg matrix H.
Triangular matrix with one extra nonzero adjacent diagonal.
-
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.
-
Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.
-
Positive definite matrix A.
Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.
-
Rank r (A)
= number of pivots = dimension of column space = dimension of row space.
-
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.
-
Solvable system Ax = b.
The right side b is in the column space of A.
-
Transpose matrix AT.
Entries AL = Ajj. AT is n by In, AT A is square, symmetric, positive semidefinite. The transposes of AB and A-I are BT AT and (AT)-I.
-
Tridiagonal matrix T: tij = 0 if Ii - j I > 1.
T- 1 has rank 1 above and below diagonal.