Lab 14: Chocolate Town

In class we experimented with Muddy City (see below), a graph where the purpose was to find the lowest cost set of connections, so there is some paved pathway between every house and every other house.

This week is Thanksgiving, so lab can optionally be done on your own, or be done in lab as usual, except for Thursday labs which must be done on your own. Those of you electing to do the lab in-person get the advantage of working with a partner, and can choose your own partner for the day.

• Pre-lab outlines are required and due as usual by Monday.

• There will be no quiz or peer reflection form for week 14 lab.

Lab Prep Outline Questions

Referring to the Muddy City problem, answer the questions below for your lab preparation outlines. Submit your outline to the same Reading Outline Submission Form that we have been using. For these questions consider not only the graphs used in class and shown here, but other possibly much larger graphs.

1. The solution to the above Muddy City problem in Computer Science is called a Minimum Spanning Tree. What sorts of networks like this exist in real life? Come up with at least 3 besides the one given as a hint. [Hint: one of them is the electrical grid.]

2. What is the relationship between the number of connections needed in a solution and the number of houses (n)? Provide an intuitive explanation for your answer.

3. What role does sorting / searching play in the solution to the above problem?

Lab Activity

1. As usual, post your previously-created outlines onto your shared slides. Use your answers to select the best set of 4 real-life examples of Minimum Spanning Trees, drawing from your outline answers.

2. Think of a UPS delivery truck setting out from the warehouse for the day to drop off packages in Muddy City. Each address would be a node, and the distance between them would be the vertices. Finding the shortest path to visit all addresses would take the least amount of time and save gas. Is this the same problem? Why or why not?

3. Again we will consider a connected graph, but this time it is Chocolate Town (see below, adapted from CS Unplugged). Over time in Chocolate Town, everyone has gotten addicted to chocolate. People have woken up in the middle of the night, have been unable to get chocolate, and had to be hospitalized, and this happened multiple times. The city council met (with a chocolate platter snack) and someone suggested putting chocolate vending machines on every corner, since people could make it a block before needing chocolate. Someone else indicated that maybe only a vending machine was needed on every-other intersection.

   1. What is an algorithm (for this and any other such graph) to find the smallest possible number of chocolate vending machines to put at intersections so that everyone is at most one “block” away from a chocolate source?

   2. If you can't find the algorithm, what are guidelines (heuristics) that can help get you at least part way to the solution?

   3. What is the smallest number of chocolate vending machines needed that you were able to find with your algorithm? Show your solution.

To work on this online, use this link and save a version for yourself. Then you can drag-and-drop chocolate vending machines.