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.Ordinary 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. Nobody asks how far each site is from one hub. Only the total cable matters.
  • What do they want? An algorithm, by name, and a reason it fits. No lengths are given, so there is no number to find.
Céim

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

Choosing, Comparing & Justifying Algorithms

Choose an algorithm by deciding whether the aim is a cheapest connected network or a shortest route.

Why it matters

Minimising total cable length does not necessarily give the cheapest travel route between towns.

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. Nobody asks how far each site is from one hub. Only the total cable matters.
    • What do they want? An algorithm, by name, and a reason it fits. No lengths are given, so there is no number to find.
  2. Understand

    • How do I picture it?
    • Take three sites, A, B, C, as an example. Possible cables: AB 4, BC 4, AC 6. Each site is a vertex; each cable is an edge.
    • Two cables join all three
  3. Reduce

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

    • Write the answer.
    • Model: sites are vertices, cables are edges weighted by length.
    • Aim: least total length with every site joined. That is an MST.
  5. Check

    • What if I used Dijkstra?
    • Back to the three sites. Dijkstra from A: B by AB = 4. C by AC = 6, since 6 < 4 + 4.
    • Dijkstra's cables: AB + AC = 4 + 6 = 10