When Scaling Breaks

Overview

Students investigate tractability through the contrast between shortest-path problems and the Traveling Salesman Problem (TSP). They use a small network to compare exact and heuristic approaches, then consider how the end of Moore’s law changes the design of technological solutions that depend on computation.

Learning intentions

• WALT explain the difference between a tractable problem and an intractable or computationally difficult problem.
• WALT model the Traveling Salesman Problem and compare exact and approximate solutions.
• WALT explain why increasing processing power does not solve every scaling problem.
• WALT evaluate responsibilities and design choices when technology cannot provide an exact answer efficiently.

Success criteria

• I can explain why shortest path and TSP are similar-looking but computationally different.
• I can calculate the number of possible TSP routes and use evidence to describe how the problem scales.
• I can compare a brute-force solution with a heuristic and justify which approach is suitable.
• I can discuss one consequence for people, organisations or the environment when computing resources are limited.

Curriculum links

• Demonstrate understanding of the application of a technical area to a specific field: computational complexity applied to logistics and route planning.
• Demonstrate understanding of consequences, responsibilities and challenges involved in technology: consequences of algorithmic choices and responsibilities of technologists.
• Undertake brief development to address an issue within a determined context: identifying a logistics need and specifications for a workable route-planning solution.
• Develop a prototype considering fitness for purpose in the broadest sense: testing and evaluating a small route-planning model against criteria such as time, accuracy and resource use.

Lesson structure (75 minutes)

1. 0–8 min · Provocation and prior knowledge. Teacher opens the hook and learning intentions slides with the question, “If computers become twice as fast, will every problem become twice as easy?” Students make an individual prediction, then share an example of a task that computers solve quickly and one that remains difficult.

2. 8–20 min · Direct teaching: tractability and Moore’s law. Teacher presents the tractability, scaling and Moore’s law slides, using the supplied ideas attributed/adapted as CSFG: Tractability. Explain that polynomial-time complexity such as n², n³ and n⁴ is generally considered tractable, while exponential or factorial complexity such as 2ⁿ, 3ⁿ and n! is generally considered intractable as n grows. Emphasise that this is a useful rule of thumb, not an absolute boundary: hardware, constants, input structure and implementation also matter. Clarify that brute-force search systematically tries possible solutions and can become impractical because the number of possibilities grows rapidly. Explain that Moore’s law describes a historical trend in transistor density and processing capability; even repeated hardware improvements do not overcome exponential growth. Students record definitions of polynomial growth, exponential growth, factorial growth, brute force, heuristic, P, NP and NP-complete in their own words. Inquiry questions: “Why might a polynomial algorithm remain usable as inputs grow?” and “Why does doubling processing speed not simply double the size of an exponential problem we can solve?”

3. 20–35 min · Algorithm Timer investigation. Teacher introduces the Algorithm Timer investigation. In pairs, students compare the estimated or measured operation counts for n², n³, 2ⁿ and n! at increasing values of n, recording how quickly each grows. Students consider how results change with 1,000, 1,000,000 and 1,000,000,000 operations per second, and then discuss whether multiple processors change the overall classification or merely provide a proportional speed-up. Students identify where each function appears to become impractical and justify their decision using evidence. Ask: “Which function benefits most from faster hardware?” and “Does parallel processing turn an exponential algorithm into a polynomial one?”

4. 35–45 min · Worked scaling examples and inquiry. Teacher models the contrasting examples: for factorial time, 20! = 2,432,902,008,176,640,000 operations, while 22! = 112,400,072,777,760,768,000, showing how a small input increase can create a huge increase in work. For exponential time, compare 2⁷⁰ with 2⁸⁰: increasing n by 10 multiplies the work by 2¹⁰ = 1,024. Students explain why these changes are more severe than a modest polynomial increase. Revisit the route-counting example: with a fixed starting point, TSP tours grow as (n−1)!: 4! = 24 for five locations, 9! = 362,880 for ten, and 19! = 121,645,100,408,832,000 for twenty. Inquiry questions: “What makes brute-force search unacceptable here?” and “Would a faster computer or several processors remove the underlying scaling problem?”

5. 45–62 min · Small-group TSP investigation. Teacher gives each pair a six-location route map on the worksheet and demonstrates the task: find the shortest tour that visits every location once and returns to the start. Students first try an exact brute-force method by listing or systematically checking routes, then try a nearest-neighbour heuristic and record distance, time and limitations. With six students, form three pairs and assign roles of navigator, checker and recorder, rotating roles halfway through. Students connect their observations to the Algorithm Timer results and explain why approximation may be necessary.

6. 62–70 min · Compare, test and critique. Teacher facilitates a pair-to-pair comparison. Students report their exact or best-known route, compare it with the heuristic result, and identify whether the heuristic guaranteed the optimum. Each student adds evidence to the worksheet under “accept, modify or reject the solution”, considering accuracy, time, scalability and practical usefulness. Discuss responsibilities including honest communication of limitations, energy use, worker conditions, accessibility, privacy and social or environmental effects.

7. 70–75 min · Formative assessment and exit response. Students complete a brief individual check: (a) classify n³, 2ⁿ and n! as generally tractable or generally intractable, with the rule-of-thumb qualification; (b) explain what happens to 2ⁿ when n increases from 70 to 80; (c) explain why faster processors and Moore’s law do not make factorial or exponential problems practically tractable; and (d) state why a heuristic may be preferred to brute force for TSP-style routing. Teacher samples responses and addresses misconceptions before the final exit response: “Explain why algorithm design, modelling and approximation become more important for TSP-style problems.”

Resources

• the complete tractability and TSP slide deck
• the tractability and route-planning worksheet
• Algorithm Timer tool or spreadsheet template
• Supplied tractability video
• Projector, speakers and internet access
• Calculators or spreadsheet software
• Pens, highlighters and timer
• Whiteboard and markers

Assessment

• Listen for accurate use of tractability, polynomial, exponential, factorial, brute force, heuristic and NP-complete during questioning and pair discussion.
• Check Algorithm Timer tables for correct comparisons of n², n³, 2ⁿ and n!, and for explanations of operations per second and multiple processors.
• Check route tables for systematic testing, valid calculations and evidence-based comparison between exact and approximate methods.
• Use the brief formative check and exit response to assess whether students can classify the example complexities, explain the n=20 versus n=22 factorial and n=70 versus n=80 exponential contrasts, and connect scaling, Moore’s law, algorithmic choices and technological consequences. Accept the tractability categories as a useful rule of thumb rather than an absolute boundary.

Differentiation

• Provide the worksheet’s formula, a partially completed route table and sentence starters such as “The heuristic is useful because…” and “It does not guarantee…”.
• Allow students to draw routes or use a spreadsheet to organise calculations; read the video prompts aloud and pause to clarify technical vocabulary.
• Extend confident students by asking them to compare nearest-neighbour with a second heuristic, or to propose a measurable stopping rule for an approximate algorithm.
• For EAL learners, pre-teach the key terms with simple examples and allow paired rehearsal before written responses. Keep roles flexible and provide a quiet written alternative to extended verbal discussion where needed.