4.4.1.1–4.4.1.2 - Solving problems and tracing algorithms (Python)

Problems and algorithms

A solution begins with a precise statement of what the inputs mean and which outputs would satisfy the problem.

An instruction such as “sort the cards” names a goal, but leaves the method unspecified. An algorithm says which cards to compare, how to move them and when to stop. The input domain matters: a method for a non-empty list cannot silently assume that an empty list contains a first value. A program implements an algorithm in a programming language; a correct algorithm can still be implemented incorrectly.

Logic problems can be solved by listing possibilities and eliminating those that contradict the constraints. Suppose Ada, Ben and Cora each use one of lockers 1, 2 and 3, with no sharing. Ada does not use 1; Ben's number is lower than Cora's; Cora does not use 3. Cora cannot use 1 because no smaller number is available for Ben. Therefore Cora uses 2, Ben uses 1 and Ada uses 3. Checking means applying every constraint to the proposed result, including uniqueness; finding a plausible arrangement alone is insufficient.

The same approach helps with program requirements. “Admit people aged at least 16” means that 16 is accepted, 15 is rejected and larger ages are accepted. Clarify whether impossible ages are guaranteed absent or must be validated before writing the selection.

Pseudocode and traces

Pseudocode expresses the method without depending on Python's exact syntax, and a hand trace follows that method one instruction at a time.

Four constructs are enough for many simple algorithms. Sequence executes instructions in order. Assignment replaces a variable's value. Selection chooses a branch using a condition. Iteration repeats instructions. Here the arrow means assignment, equality tests values, array positions start at 1, and a FOR loop includes both endpoints:

total ← 0
count ← 0
FOR i ← 1 TO LENGTH(values)
    IF values[i] >= 6 THEN
        total ← total + values[i]
        count ← count + 1
    ENDIF
ENDFOR
OUTPUT total, count

For values [4, 7, 7, 2], record the state after each whole iteration. Do not reset total inside the loop or update it when the condition is false.

The output is 14, 2. The repeated 7 is a separate input and must be counted again. A trace table should state when its rows are recorded: before a loop body, after the body or after the condition. If using a flowchart in your notebook, connect input/output, processing and decision symbols in the same order, label each decision branch and show the loop's return edge. Its meaning must agree with the pseudocode.

Translating into Python

Translation preserves the algorithm's state changes while using the high-level language's actual constructs.