Algorithms
Introduced| English | Meaning |
|---|---|
| algorithm/ˈælɡərɪθəm/ | A finite sequence of precise steps for solving a problem or carrying out a task. |
| flowchart/ˈfləʊtʃɑːt/ | A diagram showing the sequence of steps and decisions in a process or algorithm. |
| pseudocode/ˈsuːdəʊkəʊd/ | A language-independent description of an algorithm using structured, programming-like statements. |
| tracing/ˈtreɪsɪŋ/ | tracing |
| binary search/ˈbaɪnəri sɜːtʃ/ | A search of ordered data that repeatedly compares with the middle item and discards half of the remaining search range. |
| linear search/ˈlɪnɪə sɜːtʃ/ | Checking items in sequence until the required item is found or the list ends. |
| efficiency/ɪˈfɪʃənsi/ | The fraction of total energy or power input converted to useful output. |
Say which inputs the procedure must handle
- An algorithm 算法 describes unambiguous steps for a task. A procedure solving a stated finite task must terminate and give the correct result for every allowed input.
- A successful trace on one input shows that case, not a proof for all inputs. Boundary and empty-input cases can expose errors that a typical example misses.
Which are required for a sequence of steps to be an algorithm? Choose all that apply.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
A procedure solving the stated finite task needs unambiguous steps, correct results and termination on allowed inputs. Pseudocode and flowcharts are representations, not requirements to use a particular programming language.
Represent choices and updates clearly
- A flowchart 流程图 uses a decision diamond, process rectangle, input/output parallelogram and start/stop terminal, connected by directed flow arrows.
- Pseudocode 伪代码 describes the steps without requiring one implementation language. State assignment meaning, index origin, loop bounds and branch conditions before tracing.
Match each flowchart shape to what it means.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Use process rectangles, decision diamonds and start/stop terminals as given; input/output is normally shown by a parallelogram. Label decision branches and flow directions.
Record the actual variable values
- Tracing 追踪 follows the stated updates in order. A temporary variable may preserve a value that would otherwise be overwritten.
- Show low, high, middle and compared value for a binary search; show every changed variable for an arithmetic loop. Judge what the procedure does, not only its intended purpose.
A specified binary-search convention. Use zero-based inclusive bounds and floor of their average for the middle. Searching for 7 in [1,3,5,7,9,11] compares index 2/value 5, index 4/value 9, then index 3/value 7. The comparison count is three under this convention.
Linear against binary search
Halving beats checking one at a time, and the gap widens with the list.
Using zero-based inclusive bounds and floor((low+high)/2), how many comparisons does binary search use to find 7 in [1,3,5,7,9,11]?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Middle indices are 2, 4, then 3, with values 5, 9 and 7. Three comparisons under the specified convention.
Compare work under its assumptions
- A linear search 线性查找 can stop early but may inspect all n items. A binary search 二分查找 repeatedly halves a sorted search range and needs consistent bound updates.
- Efficiency 效率 describes how required work scales with input size under a defined model. Sorting first has its own cost; an unsorted input cannot rely on binary search's ordering guarantee.
For an already sorted million-item list, approximately how many middle-value comparisons can binary search need in the worst case?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Each comparison halves the remaining search range; about 20 comparisons suffice for a million ordered items. This excludes any cost of sorting beforehand.
A binary search works on an unsorted list, just more slowly.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Without the required ordering, discarding a half can miss a present item. Some cases may happen to succeed, but correctness is not guaranteed.
Check zero and the last allowed index. Sheet 4.4 examines a sum loop using i less than n, which misses the last term. Its Euclidean trace also explains termination: each positive divisor is replaced by a smaller nonnegative remainder until zero is reached.