Sorting, packing and network algorithms
| English | 中文 | Pinyin |
|---|---|---|
| algorithm/ˈælɡərɪθəm/ | 算法 | suàn fǎ |
Is a fast packing method always optimal?
- A packing method quickly fills boxes, but a fast valid arrangement need not use the smallest number of boxes.
- This lesson studies algorithm 算法: A finite set of ordered instructions that solves a defined class of problems.
Choose the mathematical structure
- Trace the named algorithm exactly, including its tie rules. In first-fit packing, place each item in the first available bin that can hold it. First-fit decreasing sorts before applying first-fit. A heuristic may be valid without being optimal.
- State the allowed inputs and units before calculating. An equation should express the relationship, not just record a calculator entry.
Which description correctly defines algorithm?
A finite set of ordered instructions that solves a defined class of problems.
Work through a checked case
- Check the result against the starting quantities. Substitute into the original relation, or compare the graph and numerical answer where appropriate.
With bin capacity 10 and items 6,5,4,3,2 in that order, first-fit places 6 and 4 in bin 1, then 5,3,2 in bin 2. It uses 2 bins. The total size is 20, so the lower bound is ceil(20/10)=2; this arrangement is optimal for this instance.
Sorting, packing and network algorithms
Trace the named algorithm exactly, including its tie rules
Compare the model with the worked case and explain one change.
How many bins does the worked first-fit arrangement use?
The first-fit arrangement fills two bins, each with total size 10.
Test a tempting shortcut
- An example of success does not prove a heuristic is always optimal. Keep intermediate lists in a sorting trace; do not jump from input to a sorted final list. A shortest-path update must retain predecessor information if a route is requested.
- When a shortcut fails, identify the assumption it breaks. Keep an exact value until the requested final rounding.
A packing heuristic that works well on one example must always be optimal. This claim is false. Explain which definition or assumption it violates.
Find the lower bound on bins for total size 20 and capacity 10.
Every bin holds at most 10, so at least ceiling(20/10)=2 bins are needed.
A packing heuristic that works well on one example must always be optimal.
An example of success does not prove a heuristic is always optimal. Keep intermediate lists in a sorting trace; do not jump from input to a sorted final list. A shortest-path update must retain predecessor information if a route is requested.
Interpret a new situation
- For Dijkstra, choose the smallest unsettled tentative label and update its neighbours. For route-inspection problems, distinguish a closed route from an open one and identify odd vertices before pairing them.
- A complete solution gives the mathematical result and explains what it means. Check that it is possible in the stated context.
Find space remaining in a bin containing items 5,3,2 with capacity 10.
Unused capacity=10-(5+3+2)=0.
Match each part of a complete solution to its purpose.
An assumption justifies the model; a check tests the result; interpretation connects it to the question.
Use this in your course
- edexcel IAL further mathematics; official unit D1. Other-unit enrichment is identified in the scope review; it is not an extra cash-in requirement.
- Give the method before the final answer, and use the paper's calculator and formula rules. Review a wrong answer by locating the first invalid step.
A finite set of ordered instructions that solves a defined class of problems. Choose the relationship, show the method, check its assumptions and interpret the result.