Algorithms, traces and correctness evidence
Введено| English | Значение |
|---|---|
| algorithm/ˈælɡərɪθəm/ | алгоритм |
| boundary test/ˈbaʊndəri test/ | граничный тест |
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.
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?
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
Binary search discards half the list by comparing with the middle, which works only if the list is ordered under the comparison rule. Duplicate values are fine, and any length works.
Match each technical term to its precise meaning.
Сложность 2/5 · 140 монет + небольшой бонус за первое выполнение сегодня
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.
In the lab: 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?
Сложность 2/5 · 140 монет + небольшой бонус за первое выполнение сегодня
Stating the conditions and assumptions lets others repeat the work exactly, and recording the supporting evidence lets them check the conclusion. Hiding disagreeing results removes the evidence that could challenge a wrong conclusion, and one measurement can never establish a wider claim.
Work from known quantities
- 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.
Your turn: A linear search scans all 14 items without a match. How many item comparisons occur?
A linear search scans all 14 items without a match. How many item comparisons occur?
Сложность 2/5 · 140 монет + небольшой бонус за первое выполнение сегодня
The result is 14 comparisons. Known: linear search over 14 items with no match. Every item must be compared before absence is certain, so comparisons = 14. An unsuccessful search always costs the full length.
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.
Not true: One successful sample test proves an algorithm correct for every valid input. One passing test shows the algorithm works on that input only. Correctness needs reasoning over all valid inputs or a proof - edge cases such as empty lists and boundary values are exactly where untested code fails.
- An algorithm is a finite, unambiguous procedure for a task.
- State input conditions and expected outputs.
- Watch for: A successful sample test does not prove correctness for all valid inputs.
One passing test shows the algorithm works on that input only.
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
True. One passing test shows the algorithm works on that input only. Correctness needs reasoning over all valid inputs or a proof - edge cases such as empty lists and boundary values are exactly where untested code fails.
A finite procedure solving a stated task: write the technical term.
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
algorithm means A finite procedure solving a stated task.