Discrete Math

General:

· Before beginning this homework, be sure to read the textbook readings and the module notes.

· For additional practice, each homework problem has some ungraded examples and sample problems from the text that you can review, and they directly correspond with your graded homework. Work on those problems if needed, and post your questions to this week’s ungraded discussion forum.

· Work within this document for your homework, and be sure to show all steps for arriving at your solution.

Section 7.1 Homework

Refer to Figure HW 7 for problems 1–5.

Figure HW 7

1) List all of the following:

a) Level-2 vertices

b) Leaves

c) Siblings of v6

d) Descendants of v6

This is similar to problems 7.1.9, 7.1.10, 7.1.14, and 7.1.15.

2) Is this an n-tree? If so, for what integer n? This is similar to problems 7.1.9, 7.1.10, 7.1.14, and 7.1.15.

3) Explain how many vertices would need to be added to each existing vertex to create a complete 3-tree. For example, writing “v0: 2” would mean that two vertices need to be added to the existing v0 vertex. Writing “v0: 0” would mean that no vertices need to be added to the existing v0 vertex.

v0: v1: v2: v3:

v4: v5: v6: v7:

v8: v9: v10: v11:

This is similar to problem 7.1.18.

4) Compute the tree T(v3).

This is similar to problems 7.1.11 and 7.1.16.

5) Give the height of each tree:

a) (T, v0)

b) T(v3)

This problem is similar problems 7.1.12 and 7.1.17.

Section 7.2 Homework

1) Construct the tree of the algebraic expression:

((x - 2) + 3) ((2 - (3 + y)) (w - 8))

This problem is similar to figure 7.6 and problems 7.2.1–7.2.10.

Note that homework problems 1–3 of the next section (section 7.3) will refer to the tree that you will have to construct in this problem.

Refer to the following Huffman code tree for problems 2 and 3:

2) Decode the message: 000110000101

This problem is similar to example 3 and problem 7.2.25.

3) Find the string that represents the word SEAT. This problem is similar to example 3 and problem 7.2.26.

Section 7.3 Homework

Here, to visit a node means to print the contents of the node. Refer to the tree that you constructed in section 7.2 homework problem 1 (above) to complete problems 1–3 below.

1) Show the results of performing a preorder search. This problem is similar to examples 1 and 2 and problems 7.3.1–7.3.5.

2) Show the results of performing an inorder search. This problem is similar to part 1 of example 3 and problems 7.3.6–7.3.9.

3) Show the results of performing a postorder search. This problem is similar to part 2 of example 3 and problems 7.3.10–7.3.14.

4) Draw the digraph of the binary positional tree that corresponds to Figure HW 7 from section 7.1 of this homework assignment. Below are images you can use to create the diagraph. You may copy/paste the arrow and alter the directions and length as needed. This problem is similar to examples 5 and 6 and problems 7.3.31 and 7.3.32.

Section 7.5 Homework

Refer to this figure for problems 1 and 2.

1) Use vertex A as the initial vertex and use Prim’s algorithm to find a minimal spanning tree. You do not need to draw the tree, but do list the edges (as an ordered pair) in the order in which they are chosen. This is similar to example 6 and problem 7.5.6.

2) Use Kruskal’s algorithm to find a minimal spanning tree. You do not need to draw the tree, but do list the edges (as an ordered pair) in the order in which they are chosen.

This is similar to examples 8 and 9 and problems 7.5.10–7.5.12.