 6.2.1: Which of the following graphs are trees with root r? If a graph is ...
 6.2.2: Which of the following graphs are binary trees with root r? If the ...
 6.2.3: Sketch a picture of each of the following trees. a. Tree with five ...
 6.2.4: Answer the following questions about the accompanying graph with no...
 6.2.5: In Exercises 58, draw the expression tree.3(2 * x 3 * y) + 4 * z4 + 1
 6.2.6: In Exercises 58, draw the expression tree.3(x 2) * 34 + (5 + 4)
 6.2.7: In Exercises 58, draw the expression tree.1 (2 33 (4 5)4)
 6.2.8: In Exercises 58, draw the expression tree.3(62) * 44 + 3(1 + x) * (...
 6.2.9: Write the left childright child array representation for the binary...
 6.2.10: Write the left childright child array representation for the binary...
 6.2.11: Draw the binary tree corresponding to the left childright child rep...
 6.2.12: Draw the binary tree corresponding to the left childright child rep...
 6.2.13: Write the left childright child array representation for the binary...
 6.2.14: Write the left childright child array representation for the binary...
 6.2.15: In the following binary tree representation, the left child and par...
 6.2.16: The following represents a tree (not necessarily binary) where, for...
 6.2.17: a. For the following tree, write the leftmost childright sibling ar...
 6.2.18: The following binary tree is the representation of a general tree (...
 6.2.19: For Exercises 1924, write the list of nodes resulting from a preord...
 6.2.20: For Exercises 1924, write the list of nodes resulting from a preord...
 6.2.21: For Exercises 1924, write the list of nodes resulting from a preord...
 6.2.22: For Exercises 1924, write the list of nodes resulting from a preord...
 6.2.23: For Exercises 1924, write the list of nodes resulting from a preord...
 6.2.24: For Exercises 1924, write the list of nodes resulting from a preord...
 6.2.25: Write in prefix and postfix notation: 34 + (2 y).
 6.2.26: Write in prefix and postfix notation: (x * y + 3z) * 4.
 6.2.27: Write in infix and postfix notation: * + 2 3 * 6 x 7.
 6.2.28: Write in infix and postfix notation: + x y z w.
 6.2.29: Write in prefix and infix notation: 4 7 x * z +
 6.2.30: Write in prefix and infix notation: x 2 w + y z * .
 6.2.31: Evaluate the postfix expression 8 2 2 3 * +
 6.2.32: Evaluate the postfix expression 5 3 + 1 3 + 7 *.
 6.2.33: Draw a single tree whose preorder traversal is a, b, c, d, e and wh...
 6.2.34: Draw a single tree whose inorder traversal is f, a, g, b, h, d, i, ...
 6.2.35: Find an example of a tree whose inorder and postorder traversals yi...
 6.2.36: Find two different trees that have the same list of nodes under a p...
 6.2.37: Informally describe a recursive algorithm to compute the height of ...
 6.2.38: Informally describe a recursive algorithm to compute the number of ...
 6.2.39: Prove that a simple graph is a nonrooted tree if and only if there ...
 6.2.40: What is the minimum number of nodes and arcs that need to be delete...
 6.2.41: Let G be a simple graph. Prove that G is a nonrooted tree if and on...
 6.2.42: Let G be a simple graph. Prove that G is a nonrooted tree if and on...
 6.2.43: Prove that a binary tree has at most 2d nodes at depth d.
 6.2.44: Prove that a tree with n nodes, n 2, has at least two nodes of degr...
 6.2.45: a. Draw a full binary tree of height 2. How many nodes does it have...
 6.2.46: Prove your conjecture from Exercise 45(c) three different ways. a. ...
 6.2.47: a. Prove that a full binary tree with x internal nodes has 2x + 1 t...
 6.2.48: Prove that the number of leaves in any binary tree is 1 more than t...
 6.2.49: Find an expression for the height of a complete binary tree with n ...
 6.2.50: Prove that in the pointer representation of a binary tree with n no...
 6.2.51: Find the chromatic number of a tree (see Section 6.1, Exercise 80).
 6.2.52: Let E be the external path length of a tree, that is, the sum of th...
 6.2.53: Let B(n) represent the number of different binary trees with n node...
 6.2.54: In the data structure known as a Btree of order 5, each node of th...
 6.2.55: Draw all the nonisomorphic trees with four nodes
 6.2.56: Draw all the nonisomorphic trees with five nodes.
 6.2.57: One of the most efficient sorting algorithms is HeapSort, which sor...
Solutions for Chapter 6.2: Trees and Their Representations
Full solutions for Mathematical Structures for Computer Science  7th Edition
ISBN: 9781429215107
Solutions for Chapter 6.2: Trees and Their Representations
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. Since 57 problems in chapter 6.2: Trees and Their Representations have been answered, more than 19997 students have viewed full stepbystep solutions from this chapter. Mathematical Structures for Computer Science was written by and is associated to the ISBN: 9781429215107. Chapter 6.2: Trees and Their Representations includes 57 full stepbystep solutions. This textbook survival guide was created for the textbook: Mathematical Structures for Computer Science, edition: 7.

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

Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn  l . Cx = convolution c * x. Eigenvectors in F.

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 Fn1c can be computed with ne/2 multiplications. Revolutionary.

Free variable Xi.
Column i has no pivot in elimination. We can give the n  r free variables any values, then Ax = b determines the r pivot variables (if solvable!).

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.

Hessenberg matrix H.
Triangular matrix with one extra nonzero adjacent diagonal.

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

Incidence matrix of a directed graph.
The m by n edgenode incidence matrix has a row for each edge (node i to node j), with entries 1 and 1 in columns i and j .

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

lAII = l/lAI and IATI = IAI.
The big formula for det(A) has a sum of n! terms, the cofactor formula uses determinants of size n  1, volume of box = I det( A) I.

Markov matrix M.
All mij > 0 and each column sum is 1. Largest eigenvalue A = 1. If mij > 0, the columns of Mk approach the steady state eigenvector M s = s > O.

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

Nullspace N (A)
= All solutions to Ax = O. Dimension n  r = (# columns)  rank.

Pivot columns of A.
Columns that contain pivots after row reduction. These are not combinations of earlier columns. The pivot columns are a basis for the column space.

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

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 matrix A.
A square matrix that has no inverse: det(A) = o.

Special solutions to As = O.
One free variable is Si = 1, other free variables = o.

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