Step 7 of 8 · Worked example · TEACH

← Algorithms, Optimisation & Project Scheduling

0 of 3 done

Work through the example to CHECK to open the problems.

Reach CHECK to open the problems.Higher Level · Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 7

Follow the worked example and explain why each modelling and calculation step is valid.

Connect all sites with minimum total cable length, without requiring a route from one source. Select a suitable algorithm and justify the choice.

Connect all the sites with the least total cable length. No route from one particular source is needed.

Select a suitable algorithm and justify the choice.

Read it once, slowly. Then copy it onto your page.
  • What is going on? Sites to be cabled together. Two demands: every site is connected, and the total cable is as short as possible.
  • What is ruled out? No route from one source is wanted. Nobody asks how far each site is from a hub, only how much cable in all.
  • What do they want? An algorithm, named, and a reason it fits. No lengths are given, so there is no number to find.
Céim

Higher Level Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 7 of 8

Choosing, Comparing & Justifying Algorithms

Choose an algorithm by matching its objective and assumptions to the network problem.

Why it matters

In an exam, a shortest route and a cheapest connecting network require different reasoning even when they use the same graph.

The worked example

Connect all the sites with the least total cable length. No route from one particular source is needed. Select a suitable algorithm and justify the choice.

How the worked example goes

  1. Read

    • What is going on? Sites to be cabled together. Two demands: every site is connected, and the total cable is as short as possible.
    • What is ruled out? No route from one source is wanted. Nobody asks how far each site is from a hub, only how much cable in all.
    • What do they want? An algorithm, named, and a reason it fits. No lengths are given, so there is no number to find.
  2. Understand

    • How do I picture it?
    • Each site is a vertex. Each possible cable is an undirected edge, weighted by its length. Assume every site can be reached.
    • Picture three sites with possible cables AB = 2, BC = 2, AC = 3. Two cables join all three.
  3. Reduce

    • Least total cable, every site joined, no source. Which algorithm fits? Kruskal or Prim: Both build a minimum spanning tree: every site joined at the least total length.
    • So what is the method?
    • Name the objective first: minimise total cable length, every site joined. No source, no destination: it is not a route problem.
  4. Solve

    • Why do Kruskal and Prim give the least?
    • Kruskal adds the shortest cables first, skipping any that close a loop. Prim grows one network, adding the shortest cable from it to a new site.
    • Each step is safe: the shortest cable leaving any group of joined sites always belongs to some minimum tree.
  5. Check

    • What if we used Dijkstra?
    • Back to the three sites. Dijkstra from A: d(B) = 2 by AB; d(C) = 3 by AC, since 3 < 2 + 2.
    • Dijkstra's cables: AB + AC = 2 + 3 = 5