Unit 7: Trees – Assignment

Total points for Assignment: 35 points. Assignments must be submitted as a Microsoft Word document and uploaded to the Dropbox for Unit 7. All Assignments are due by Tuesday at 11:59 PM ET of the assigned Unit.

NOTE: Assignment problems should not be posted to the Discussion threads. Questions on the Assignment problems should be addressed to the instructor by sending an email or by attending office hours.

You must show your work on all problems. If a problem is worth 2 points and you only show the answer, then you will receive only 1 point credit. If you use a calculator or online website, give the source and tell me exactly what you provided as input. For example, if you used Excel to compute 16 * 16, state “I typed =16*16 into Excel and got 256. You may type your answer right into this document.

Part I. Basic Computations

1. Using the following tree, name two vertices that are considered the following. Explain in your own words how you know:

(a) parent-child (2 points).

Answer:
Explanation:

(b) sibling nodes (2 points):

Answer:
Explanation:

(c) leaf nodes (2 points)

Answer:
Explanation:

 

2. Determine if each of the following graphs is considered a tree. Explain why or why not, using what you learned in this unit.

a. (2 points) Answer:
Explanation:

b. (2 points) Answer:
Explanation:

c. (1 point) Answer:
Explanation:

3. Determine and sketch two different spanning trees for this graph:

a. (1 point)

b. (1 point)

 

4. Consider this graph:

a. Determine the total weight for this graph. Show your work. (1 point)

Answer:
Explanation:

b. Draw one spanning tree for this weighted graph and determine its weight. Show your work. (1 point)

[Hint: One way to do this is to make a copy of the graph using cut/paste, then show your spanning tree.]

Answer:

Total weight:

 

Part II. Case Study The Case of the Yip-it-tee DooDahs

This week, the cast and crew of the “Patty Madeye Mysteries” will be filming on-location at the Yip-it-tee Amusement Park. The episode will be centered around a gang of purse-snatchers (they call them selves the “Doodahs”) who prey on vistors at the Yip-it-tee Amusement Park. While customers are having fun on the water rides, the purse-snatchers help themselves to any valuables that are left behind.

The park owner has provided a detailed map of the amusement park.

• The Entrance Gate is identified by the little house (location H)
• Numbered locations identify the 7 rides in the park (see legend at the bottom)
• Food Stands are identified by the “hamburger” icons (A, C, D, F)
• Restrooms are identified as locations G, B, and E
• The Storage and Maintenance Facility is identified as location S.
• The distance between each of the 16 locations is measured in meters and listed in green letters.

 

 

Task #1: (4 points) The first scene of the episode will be focused on ride #6 (Wippee Water Slide). Your first task is to sketch a binary spanning tree (that would be a spanning tree in which each parent has no more than 2 children) using the locations as vertices and the paths as edges. Use location 6 (Wippee Water Slide) as the root of the tree.

[Hint: Remember that all 16 locations must be included somewhere in your tree.]

Answer:

Task #2. (4 points) Your next task is to describe for Patty and the filming crew all the available paths from the Entrance (Location H). Sketch a spanning tree (it does not have to be a binary tree) using Location H as the root.

Answer:

Task #3. (4 points) Determine whether it is possible to visit each of the 16 locations on this map without retracing your steps on any given path. If so, describe the path below. If not, explain how you know that such a path is not possible.

Answer:

Task #4. (8 points) The crew will need to lay cable along the paths of the park so that they can film in each of the 16 locations. Your next task is to use a minimum spanning tree to determine how much cable the film crew will need to use. Sketch the tree and compute the total weight of the tree, using the distances indicated on the graph.

[Hint: One way to do this is to print the graph, then use a highlighter to draw your spanning tree, then take a picture of your paper using your cell phone. Paste the picture into this document]

Answer