Activity 37: Topological Sort and MST

Problem 1A: Topological Sort

Given this DAG (course prerequisites):

CS101 → CS201 → CS301
  ↓       ↓       ↓
CS150 → CS250 → CS350
  ↓
CS160

Tasks:

  1. Trace DFS-based topological sort starting from CS101
  2. Show the finish order of vertices
  3. Write the topological ordering (reversed finish order)
  4. Verify: does your ordering respect all dependencies?

Problem 1B: Minimum Spanning Tree

Given this weighted graph:

    A --5-- B --7-- C
    |  \    |  /    |
    4   6   3 /9    2
    |    \  |/      |
    D --8-- E --4-- F

Choose ONE algorithm to trace:

Option 1: Kruskal's Algorithm

  • List all edges sorted by weight
  • Mark which edges you add/skip
  • Draw the final MST and calculate total weight

Option 2: Prim's Algorithm (start from A)

  • Show MST growth step by step
  • At each step, show which edge you're adding and why
  • Draw the final MST and calculate total weight

Part 2: Create a Challenge

Partner up! Each person should:

  1. Design a challenge graph for your partner of your choice:

    • Topological sort: Create a DAG with 5-7 vertices
    • MST: Create a weighted graph with 5-6 vertices and 7-9 edges

  2. Design guidelines:

    • Make it interesting but solvable in 3-4 minutes
    • For topological sort: ensure it's actually a DAG (no cycles!)
    • For MST: include some close edge weights to make decisions non-trivial
    • Label your nodes/edges meaningfully! (courses, tasks, roads, etc)

  3. Write down your own solution on a separate piece of paper

Part 3: Swap and Solve

  1. Exchange challenge graphs with your partner
  2. Solve your partner's problem:
    • For topological sort: find a valid ordering
    • For MST: trace Kruskal's OR Prim's to find the MST
  3. Show your work - your partner will check it!

Part 4: Check and Discuss

  1. Swap back and check each other's solutions using your answer key
  2. Discuss:
    • Did they find a correct solution?
    • If topological sort: are there other valid orderings?
    • If MST: did you both get the same total weight?
    • What made the problem easy or tricky?

Discussion Questions to Submit on Gradescope

  1. What made a good challenge graph? What made it too easy or too hard?
  2. Which MST algorithm (Kruskal's or Prim's) felt easier to trace by hand? Why?

Blank page here!