Algorithms, traces and correctness evidence
| English | 中文 | Pinyin |
|---|---|---|
| algorithm/ˈælɡərɪθəm/ | 算法 | suàn fǎ |
| boundary test/ˈbaʊndəri test/ | 边界测试 | biān jiè cè shì |
What would explain this observation?
- An algorithm 算法 can work for one example and fail at a boundary. Testing should be designed from the specification, not only the happy path.
- Start with a prediction. State the quantities or features you would compare, then decide what evidence could distinguish two explanations.
Build the model
- An algorithm is a finite, unambiguous procedure for a task. A trace records state changes. A loop invariant describes a property preserved by each iteration and helps justify correctness.
- algorithm: A finite procedure solving a stated task; boundary test 边界测试: A test at a limit of the allowed input range.
What must hold before applying ordinary binary search to a list?
State input conditions and expected outputs. Use boundary cases, empty collections where allowed, duplicates and invalid values. Distinguish a wrong algorithm from a wrong implementation or an incomplete requirement.
Match each technical term to its precise meaning.
Use the definitions to distinguish related quantities and processes.
Choose evidence that can test it
- State input conditions and expected outputs. Use boundary cases, empty collections where allowed, duplicates and invalid values. Distinguish a wrong algorithm from a wrong implementation or an incomplete requirement.
- Trace a search over a small fictional sorted list. State the indexing convention. For binary search, update bounds so the remaining interval shrinks and reject unsorted input unless sorting is part of the task.
Which two habits make the investigation or model in this case more defensible?
Trace a search over a small fictional sorted list. State the indexing convention. For binary search, update bounds so the remaining interval shrinks and reject unsorted input unless sorting is part of the task.
Work from known quantities
- State the known values and their units. Choose the relation because its assumptions fit this case, then rearrange before substitution.
- Known: a linear search of an eight-item list can require eight comparisons when the sought item is last or absent. Doubling the list length doubles the worst-case comparison count under this model. Binary search reduces the interval by roughly half each step but requires a suitable ordered structure.
A linear search scans all 14 items without a match. How many item comparisons occur? Use the same sequence: known quantities → model → relation → substitution → unit and interpretation.
A linear search scans all 14 items without a match. How many item comparisons occur?
The result is 14 comparisons. Known: a linear search of an eight-item list can require eight comparisons when the sought item is last or absent. Doubling the list length doubles the worst-case comparison count under this model. Binary search reduces the interval by roughly half each step but requires a suitable ordered structure.
Check the conclusion and its limits
- A successful sample test does not prove correctness for all valid inputs. Do not import Cambridge-specific pseudocode syntax into an IB course without a course source.
- Return to the original observation. Explain what the result supports, which conditions it assumes, and one way to test a competing explanation.
One successful sample test proves an algorithm correct for every valid input. This claim is false: A successful sample test does not prove correctness for all valid inputs. Do not import Cambridge-specific pseudocode syntax into an IB course without a course source.
Algorithms, traces and correctness evidence: State input conditions and expected outputs. Use boundary cases, empty collections where allowed, duplicates and invalid values. Distinguish a wrong algorithm from a wrong implementation or an incomplete requirement.
One successful sample test proves an algorithm correct for every valid input.
A successful sample test does not prove correctness for all valid inputs. Do not import Cambridge-specific pseudocode syntax into an IB course without a course source.
A finite procedure solving a stated task: write the technical term.
algorithm means A finite procedure solving a stated task.