Algorithms are designed to solve abstract problems, but their value lies in their application to real-world scenarios. The key skill is:
1. Modelling: Translate a real-world problem into an appropriate abstract model (ADT + algorithm)
2. Solving: Apply the algorithm to the model
3. Interpreting: Translate the computed solution back into real-world terms
KEY TAKEAWAY: A computed solution (e.g., shortest path of length 14) is meaningless without interpretation (e.g., “the fastest route from Melbourne CBD to the airport takes 14 minutes”).
Real-world problem
↓ (abstraction / modelling)
Abstract model (graph, ADT)
↓ (algorithm selection)
Algorithm execution
↓ (interpretation)
Real-world solution
Each step requires careful thinking:
- Abstraction: What are the entities? What are the relationships? What properties matter?
- Algorithm selection: Which algorithm solves this problem type? What are its preconditions?
- Interpretation: What does the output mean in context? Is it actionable?
Real-world problem: A telecommunications company must connect 8 cities with fibre optic cable at minimum cost. The cost of connecting each pair of cities is known.
Abstraction:
- Cities → vertices
- Possible cable routes → weighted edges (weight = cost)
- Constraint: all cities must be connected
Algorithm: Prim’s algorithm (finds MST)
Interpretation: The MST gives the set of cables to install. The total weight of the MST = minimum total cost. If MST weight = $2.4M, the company can connect all cities for \$2.4 million.
Real-world problem: Find the fastest driving route from Suburb A to Suburb B.
Abstraction:
- Intersections → vertices
- Road segments → directed weighted edges (weight = travel time in minutes)
- Non-negative weights (travel time ≥ 0)
Algorithm: Dijkstra’s algorithm
Interpretation: dist[B] = 23 means the fastest route takes 23 minutes. The path itself (sequence of vertices) gives the actual turn-by-turn route.
Real-world problem: Google must rank web pages by relevance/importance.
Abstraction:
- Web pages → vertices
- Hyperlinks → directed edges
Algorithm: PageRank
Interpretation: Pages with higher PageRank scores appear higher in search results. A PageRank of 0.05 for page X means the random surfer spends 5% of their time on X.
Real-world problem: A construction project has 12 tasks. Some tasks cannot start until others finish.
Abstraction:
- Tasks → vertices of a DAG
- Dependencies → directed edges (A→B means A must finish before B starts)
Algorithm: Topological sort (DFS on DAG)
Interpretation: The topological order gives a valid task schedule. If a cycle is detected, the schedule is impossible (circular dependency).
After computing a solution, evaluate its fitness:
- Correctness: Does the algorithm guarantee the optimal solution?
- Practicality: Is the solution implementable in the real world?
- Limitations: Does the model simplify away important real-world constraints?
EXAM TIP: When asked to apply an algorithm to a real-world problem, always: (1) identify the mapping from real-world elements to graph elements, (2) state which algorithm applies and why, (3) state what the output means in real-world terms. Marks are often given for the interpretation step.