## Transcribed Text

Homework
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 5.1 Homework
1) Let A = {1, 2, 3, 4, 5} and B = {MA, NH, NV, TX, AK, ME}.
Define a relation R from A to B that is a function and contains at least 4 ordered pairs.
What is the domain of this function?
What is the range of this function?
This problem is similar to example 2 and problems 5.1.1 and 5.1.2.
2) Define functions f: ℝ → ℝ and g: ℝ → ℝ by f(a) = 5a - 3 and g(b) = 4 - 2b. Find the following:
(f○g)(0)
(g○f)(1)
(f○g)(x)
(g○f)(x)
This problem is similar to example 9 and problems 5.1.9 and 5.1.10.
3) Let A = {2, 3, 5, 7, 11, 13, 17, 23} and B = {a, e, i, o, u, y}. Using at least 5 ordered pairs, define the following:
A function from A to B that is one-to-one.
A function from A to B that is not one-to-one.
A function from A to B that is onto.
A function from A to B that is not onto.
A function from B to A that acts as the inverse of the function you created in part a) of this problem.
This problem is similar to example 12 and problems 5.1.11 and 5.1.12.
4) The function f: ℝ → ℝ defined by f(x) = x³ is onto because for any real number r, we have that ∛r is a real number and f(∛r)=r. Consider the same function defined on the integers g: ℤ → ℤ by g(n) = n³. Explain why g is not onto ℤ and give one integer that g cannot output. This problem is similar to examples 10 and 12.
5) Let A = {x| x is a nation}
B = {Asia, Africa, North America, South America, Antarctica, Europe, Australia}
Let f:A→B be the function that outputs the continent to which a nation belongs. For example, f(Iceland) = Europe and f(Greenland) = North America. Explain why f is not a one-to-one function and give an example to prove it. This problem is similar to example 16 and problems 5.1.11b and 5.1.12b.
Section 5.2
1) Suppose a health insurance company identifies each member with a 7-digit account number. Define the hashing function h which takes the first 3 digits of an account number as 1 number and the last 4 digits as another number; adds them, and then applies the mod-41 function.
How many linked lists does this create?
Compute h(4686158)
Compute h(9813284)
This problem is similar to example 10 and problems 5.2.24–5.2.26.
2) Compute the check digit c for the following ISBNs.
031676948-c
140123517-c
This problem is similar to problems 5.2.49 and 5.2.50.
Section 5.3 Homework
1) The picture below shows the graph of r(x) in red and the graph of b(x) in blue. Does this graph show that r is O(b) or that b is O(r)? Explain.
Homework
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.

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.