CS Unplugged activity

The Muddy City: lesson plan

A short teacher-led plan for The Muddy City: connect every house in a muddy town using as few paving stones as possible. About 50 minutes. Leaving it for a sub? Use the box below.

For a sub: the 2-minute version

Skip everything below this box. Nothing to set up.

Optional, if you can project: type https://learn.porttack.com/go/muddy into the browser’s address bar (not a search box), press Enter, then use the right arrow key to step through. Stop at the slide titled Now the Whole City, then hand out the sheets. Unsure about a slide? Skip the slides: the sheet explains everything.

Hand out the worksheet, one per student. Names on top.
Say: “The mayor wants to pave just enough roads so everyone can reach everyone’s house, using as few paving stones as possible. Shade lightly first; you can change your mind.”
If the teacher left more puzzles, hand the next one to each student who finishes: a new muddy town to pave.
Restless room? Let neighbors work in pairs. Talking about the puzzle is fine.
Collect every sheet, finished or not.

Slides are optional. The sheet explains everything. The NP-complete box near the end is optional reading for curious students.

Before the sub day (teacher, or whoever preps the sub folder): print one copy of the worksheet per student, plus keep-going sheets from the New set page: set Copies to your class size and Sets per student to 2 (front and back). That covers a full period even for your fastest students.

Students will be able to

Find a cheapest set of roads that connects every house.
Follow a step-by-step method (pave the cheapest road unless it makes a loop).
Notice that a city with n houses always needs n − 1 roads.

Before class

Print one worksheet per student.
Print keep-going sheets from the New set page: Copies = class size, Sets per student = 2 (front and back).
Optional: the slides.

The lesson

1. Hook (5 minutes)

Show the slides up to A Tiny Town: three houses, three possible roads. Ask which two roads to pave. (The 2 and the 3: 5 stones.)

2. The city (15 minutes)

Students solve the big city on the sheet. Let them try their own way first; don’t give away the method. Ask a few students to share totals: different totals mean someone can still improve.

3. The graph and the method (10 minutes)

Students do the graph version, then try the method on the sheet: pave the cheapest road first, skip any road that joins two houses already connected. Did it match their best total?

4. Keep going (as students finish)

The three towns at the end of the sheet, then keep-going sheets.

5. Wrap-up (5 minutes)

Ask: “How many roads does a city with 10 houses need?” (9.) “Why not 10?” (The tenth would make a loop you don’t need.)