The Muddy City: Minimal Spanning Trees — Quiz

Multiple-Choice Questions

1. What problem was the mayor trying to solve in the story?
A) Building a swimming pool before winter
B) Paving enough streets to connect all houses at minimum cost
C) Removing all the mud from the city
D) Building the tallest building in the city

2. What do the numbers between houses on the map represent?
A) The number of houses on that street
B) The cost (number of paving stones) to pave that route
C) The distance in miles between cities
D) The population of each house

3. In the example solutions shown, what was the minimum total cost to pave the city?
A) 20 paving stones
B) 21 paving stones
C) 23 paving stones
D) 25 paving stones

4. What does the activity tell us about optimal solutions to the muddy city problem?
A) There is only ever one correct solution
B) There can be more than one solution with the same total cost
C) The solution always uses all the roads
D) The bridge must always be paved

5. What is the abstract representation of a city (with circles and lines) called by computer scientists and mathematicians?
A) A chart
B) A diagram
C) A graph
D) A map

6. What strategy is described as the good, guaranteed way to find an optimal solution?
A) Starting with all paths paved and removing the shortest ones first
B) Randomly guessing which roads to pave
C) Adding paths in increasing order of length, without linking houses that are already linked
D) Paving only the roads next to the mayor's house

**7. If a city has n houses, how many connections will an optimal solution always have?**
A) n + 1
B) n
C) n − 1
D) 2n

8. What is the name given to the simple method of adding connections in increasing order of size, without creating unnecessary links?
A) Newton's algorithm
B) Kruskal's algorithm
C) Dewdney's algorithm
D) Harel's algorithm

Short-Answer Questions

9. Explain why the mayor did not want to pave every street in the city, even though that would let everyone travel to any other house.

10. Name two real-world examples (other than roads) mentioned in the resource where minimal spanning trees can be useful.

11. The resource says the muddy city algorithm may not be very useful for networks like flight paths or roads between cities, even though it finds the shortest total length. Explain why, based on the text.

---

Answer Key

1. B
2. B
3. C
4. B
5. C
6. C
7. C
8. B

1. The mayor wanted to save money to build a swimming pool, so paving needed to be done at minimum total cost rather than paving every street.

1. Any two of: computer networks, telephone networks, oil pipelines, airline routes (utility networks such as electricity, gas, or water are also acceptable).

1. Because the algorithm only minimizes the total length of the connections — it guarantees you can get between any two points, but it does not take into account the convenience of the route.