 11.2.26E: a) Use Huffman coding to encode these symbols with frequencies a: 0...
 11.2.22E: Given the coding scheme a: 001. b: 0001. e: 1. r: 0000. s: 0100, t:...
 11.2.1E: Build a binary search tree for the words banana, peach, apple, pear...
 11.2.3E: How many comparisons are needed to locate or to add each of these w...
 11.2.2E: Build a binary search tree for the words oenology, phrenology, camp...
 11.2.5E: Using alphabetical order, construct a binary search tree for the wo...
 11.2.7E: How many weighings of a balance scale are needed to find a counterf...
 11.2.4E: How many comparisons are needed to locate or to add each of the wor...
 11.2.10E: One of four coins may be counterfeit. If it is counterfeit it may b...
 11.2.9E: How many weighings of a balance scale are needed to find a counterf...
 11.2.11E: Find the least number of comparisons needed to sort four elements a...
 11.2.18E: Show that the tournament sort requires ?(n log n) comparisons to so...
 11.2.15E: Describe the tournament sort using pseudocode.
 11.2.16E: Assuming that n, the number of elements to be sorted, equals 2k for...
 11.2.14E: Use the tournament sort to sort the list 17, 4. 1,5. 13, 10. 14. 6.
 11.2.17E: How many comparisons does the tournament sort use to find the secon...
 11.2.13E: Complete the tournament sort of the list 22. 8. 14. 17. 3. 9. 27. 1...
 11.2.20E: Construct the binary tree with prefix codes representing these codi...
 11.2.19E: Which of these codes are prefix codes?a) a:11, e: 00, t: 10. s: 01_...
 11.2.25E: Construct two different Huffman codes for these symbols and frequen...
 11.2.27E: Construct a Huffman code for the letters of the English alphabet wh...
 11.2.21E: What are the codes for a, e, i, k, o, p, and u if the coding scheme...
 11.2.24E: Use Huffman coding to encode these symbols with given frequencies: ...
 11.2.23E: Use Huffman coding to encode these symbols with given frequencies: ...
 11.2.29E: Using the symbols 0, 1, and 2 use ternary (m = 3) Huffman coding to...
 11.2.28E: Describe the mary Huffman coding algorithm in pseudocode.
 11.2.30E: Consider the three symbols A, B, and C with frequencies A: 0.80, B:...
 11.2.31E: Given n + 1 symbols x1, x2,…, xn, xn+1 appearing 1, f1, f2,…. fn ti...
 11.2.32E: Show that Huffman codes are optimal in the sense that they represen...
 11.2.34E: Draw a game tree for nim if the starting position consists of three...
 11.2.33E: Draw a game tree for nim if the starting position consists of two p...
 11.2.36E: Suppose that in a variation of the game of nim we allow a player to...
 11.2.35E: Suppose that we vary the pay off to the winning player in the game ...
 11.2.37E: Draw the subtree of the game tree for tictactoe beginning at each...
 11.2.38E: Suppose that the first four moves of a tictactoe game are as show...
 11.2.39E: Show that if a game of nim begins with two piles containing the sam...
 11.2.41E: How many children does the root of the game tree for checkers have?...
 11.2.40E: Show that if a game of nim begins with two piles containing differe...
 11.2.43E: Draw the game tree for the game of tictactoe for the levels corre...
 11.2.44E: Use pseudocode to describe an algorithm for determining the value o...
 11.2.42E: How many children does the root of the game tree for nim have and h...
Solutions for Chapter 11.2: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 11.2
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. This expansive textbook survival guide covers the following chapters and their solutions. Since 41 problems in chapter 11.2 have been answered, more than 197946 students have viewed full stepbystep solutions from this chapter. Chapter 11.2 includes 41 full stepbystep solutions.

Change of basis matrix M.
The old basis vectors v j are combinations L mij Wi of the new basis vectors. The coordinates of CI VI + ... + cnvn = dl wI + ... + dn Wn are related by d = M c. (For n = 2 set VI = mll WI +m21 W2, V2 = m12WI +m22w2.)

Cofactor Cij.
Remove row i and column j; multiply the determinant by (I)i + j •

Condition number
cond(A) = c(A) = IIAIlIIAIII = amaxlamin. In Ax = b, the relative change Ilox III Ilx II is less than cond(A) times the relative change Ilob III lib II· Condition numbers measure the sensitivity of the output to change in the input.

Factorization
A = L U. If elimination takes A to U without row exchanges, then the lower triangular L with multipliers eij (and eii = 1) brings U back to A.

Full column rank r = n.
Independent columns, N(A) = {O}, no free variables.

Fundamental Theorem.
The nullspace N (A) and row space C (AT) are orthogonal complements in Rn(perpendicular from Ax = 0 with dimensions rand n  r). Applied to AT, the column space C(A) is the orthogonal complement of N(AT) in Rm.

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

Iterative method.
A sequence of steps intended to approach the desired solution.

Kirchhoff's Laws.
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.

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

Matrix multiplication AB.
The i, j entry of AB is (row i of A)·(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .

Multiplication Ax
= Xl (column 1) + ... + xn(column n) = combination of columns.

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

Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.

Random matrix rand(n) or randn(n).
MATLAB creates a matrix with random entries, uniformly distributed on [0 1] for rand and standard normal distribution for randn.

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 picture of Ax = b.
Each equation gives a plane in Rn; the planes intersect at x.

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

Symmetric factorizations A = LDLT and A = QAQT.
Signs in A = signs in D.

Triangle inequality II u + v II < II u II + II v II.
For matrix norms II A + B II < II A II + II B II·