Computer Science · 12th Grade

Active learning ideas

Network Optimization: Connecting Points Efficiently

Active learning helps students grasp Network Optimization because abstract graph theory comes alive when they physically manipulate edges and weights. These hands-on strategies build intuition for why greedy algorithms succeed in this domain, turning algorithmic steps into memorable, visual decisions.

• Common Core State Standards
• CSTA: 3B-AP-12
• CCSS.ELA-LITERACY.RST.11-12.3

• 25–35 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Case Study Analysis
• 35 min · Small Groups

Problem Solving: City Network Design Challenge

Give student groups a map of 7 fictional cities with labeled road distances. Groups design the minimum-cost road network linking all cities, first by intuition and then by systematically applying Kruskal's approach: sort edges, add the cheapest one that does not form a cycle. Groups compare their intuitive solution to the algorithmic result.

How can we connect all points in a network using the least amount of resources?

Facilitation Tip

During City Network Design Challenge, circulate with a checklist to confirm students label each connection with its weight and total cost as they build.

What to look for

Present students with a small, weighted graph (e.g., 5-6 nodes). Ask them to apply Kruskal's algorithm step-by-step, drawing the graph at each stage and listing the edges added. Verify they select the lowest weight edge that does not create a cycle.

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management

Activity 02

• Simulation Game
• 30 min · Whole Class

Simulation Game: Human Prim's Algorithm

Designate students as nodes in a graph drawn on the board. One student starts as the tree, and the class collectively selects the cheapest edge connecting a tree node to a non-tree node at each step. Students physically move to the tree side of the room as their node is added, and the class tracks total cost after each step.

Analyze real-world scenarios where efficient network connections are critical.

Facilitation Tip

In Human Prim’s Algorithm, assign each student a node to track their own local minimum edge to avoid confusion in crowded groups.

What to look for

Pose the scenario: 'Imagine you are tasked with connecting three remote research stations in Antarctica with the least amount of heated cable. How would you approach this problem? What information would you need, and what strategy would you use to find the most efficient connection plan?'

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 03

• Think-Pair-Share
• 25 min · Pairs

Think-Pair-Share: When Greedy Fails

Present two optimization problems side by side: a minimum spanning tree problem where greedy works and a Traveling Salesman problem where it does not. Pairs trace through both with a small graph, then discuss what property of the MST problem allows greedy to succeed where it fails for TSP.

Propose a simple method to find the most cost-effective way to link several locations.

Facilitation Tip

For When Greedy Fails, supply two small graphs with tied weights so students can see identical total costs despite different edge selections.

What to look for

Provide students with a diagram of 4 cities and the costs to build direct roads between them. Ask them to identify the minimum cost to connect all four cities and list the specific roads they would build. They should briefly explain why their selection is the most cost-effective.

• Understand
• Apply
• Analyze
• Self-Awareness
• Relationship Skills

Activity 04

• Gallery Walk
• 25 min · Pairs

Gallery Walk: Real-World Network Design Cases

Post 5 case studies of real infrastructure projects including fiber optic network layout, airline hub connections, and power grid expansion. Students annotate which are MST problems, what the edge weights represent, and what practical constraints might make a pure MST solution insufficient in each case.

How can we connect all points in a network using the least amount of resources?

Facilitation Tip

During Gallery Walk, post sentence stems like ‘This design saves X meters of cable because…’ to guide written feedback.

What to look for

Present students with a small, weighted graph (e.g., 5-6 nodes). Ask them to apply Kruskal's algorithm step-by-step, drawing the graph at each stage and listing the edges added. Verify they select the lowest weight edge that does not create a cycle.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

A few notes on teaching this unit

Teachers should emphasize the greedy choice property by having students repeatedly ask, ‘What’s the cheapest edge I can add without creating a cycle?’ before moving on. Avoid rushing to the algorithm’s name; instead, let students verbalize the rule in their own words first. Research shows that drawing each intermediate step cements understanding far more than rushing through the steps.

Successful learning looks like students confidently choosing the next edge in Kruskal’s or Prim’s based on weight and cycle rules, explaining why a given set of connections is minimal, and recognizing when multiple valid solutions exist. They should also articulate why an MST does not guarantee the shortest path between two nodes.

---

Watch Out for These Misconceptions

• During City Network Design Challenge, students may assume only one cheapest network exists.

  After students complete their designs, display two student solutions with the same total cost but different edges, then ask the class to compare why both are valid.

• During Human Prim’s Algorithm, students might think the MST gives the shortest route from the start node to every other node.

  After the simulation, pose the Antarctica scenario and have students calculate both the MST total length and the actual shortest path from Station A to Station B to highlight the difference.

• During When Greedy Fails, students might generalize that greedy always works in optimization problems.

  After the discussion, present the Traveling Salesman problem on four nodes and ask students to run a greedy version to see why it fails, then contrast with Kruskal’s guaranteed success.

---

Methods used in this brief

• Case Study Analysis
• Simulation Game
• Think-Pair-Share
• Gallery Walk