← The Muddy City: Minimal Spanning Trees
Flashcards
The Muddy City: Minimal Spanning Trees
Generated from the original open resource by CS Unplugged. Built only from the resource — nothing invented. Free, no login.
The Muddy City: Minimal Spanning Trees
| Front | Back |
|---|---|
| What is the "Muddy City" activity about? | Finding the cheapest way to pave streets so every house can be reached from every other house using only paved roads. |
| What are the two conditions the mayor set for paving? | (1) Every house must be reachable from every other house via paved roads, and (2) the paving must be done at minimum total cost. |
| What do the numbers between houses on the map represent? | The cost (number of paving stones) required to pave that route. |
| What is a minimal spanning tree? | A network design that connects all points (like houses) using the minimum total length of connections. |
| What is a "graph" in computer science terms? | An abstract representation of relationships using circles (points/houses) and connecting lines (roads), with numbers showing distances or costs. |
| How is a computer science "graph" different from a math class "graph"? | A computer science graph shows relationships between objects (like a network), while a math graph (like a bar graph) displays numerical data. |
| What is Kruskal's Algorithm? | A method for solving minimal spanning tree problems by adding connections in increasing order of size, but only if they join previously unconnected parts of the network. |
| Who is Kruskal's Algorithm named after? | J.B. Kruskal, who published the algorithm in 1956. |
| What is a "greedy algorithm"? | An algorithm that builds a solution step by step, always choosing the next best (e.g., shortest) option available at each step. |
| If there are n houses, how many connections are needed for an optimal solution? | Exactly n − 1 connections. |
| Why shouldn't you add more than n − 1 connections? | Adding more would create unnecessary alternative routes between houses, increasing cost without benefit. |
| Can there be more than one optimal solution to a muddy city problem? | Yes, different orders of adding equal-length paths can create different solutions with the same total minimum cost. |
| What strategy do children often use to solve the Muddy City puzzle? | Starting with an empty map and gradually adding paving stones for the shortest paths first, avoiding paths that connect already-linked houses. |
| What is an alternative (less efficient) strategy for solving the puzzle? | Starting with all paths paved, then removing paths that aren't needed (redundant connections). |
| What are some real-world examples of minimal spanning tree problems? | Utility networks (electricity, gas, water), computer networks, telephone networks, oil pipelines, and airline routes. |
| What is a limitation of the muddy city algorithm for real-world networks like flight paths? | It only minimizes total length/cost of connections and does not consider the convenience of the route between two specific points. |
| What is the "traveling salesperson problem"? | A related graph problem that seeks the shortest route that visits every point in a network. |
| What skills does the Muddy City activity focus on? | Puzzle solving, optimization, and planning. |
Original licensed under CC BY-NC-SA 4.0. This teaching material is provided free by OER.ai.