12 Python Chapter 1 — algorithms and problem solving

Python Chapter 1 — algorithms and problem solving

← Index · Solutions

Priority key · Priorities guide emphasis; they do not remove taught scope.

Exam recall

Specify inputs, returned output, order and boundaries before choosing variables. “All” requires retaining every match; printing is not returning.

Turn the English into a contract priority/high

Before coding, identify inputs, output, conditions, order, restrictions and edge cases. Underline action words: return, display, count, sum, list, modify. “Return all longest words in their original order” is different from “return the longest length” and from “print one longest word”.

Wording	Implementation consequence
More than / greater than	>
At least / not less than	>=
All matching items	Build a collection, not just the first match.
Number of items	Increment a count, not a total of values.
In original order	Traverse in order; do not sort unless explicitly appropriate.
Without changing the input	Build separate output or use non-mutating traversal.

An algorithm is a finite, unambiguous sequence of effective steps for solving the stated problem. Decomposition splits it into manageable subproblems; abstraction keeps relevant details and hides irrelevant ones. Sequence, selection and iteration describe control flow. Pseudocode communicates the algorithm without depending on Python syntax; indentation and clear bounds still matter.

Modular development separates responsibilities into functions/modules with clear interfaces. Incremental development adds and tests a small working part at a time. These can be used together: implement and test a parsing function before adding the calculation and output functions. Use names that describe state, indentation that exposes control flow, and comments explaining intent or a non-obvious boundary rather than restating every assignment.

Design state before syntax priority/high

The algorithm is the bridge between the question and Python syntax. If you cannot say what a variable represents, it is hard to know whether its update is correct. Write a short state meaning, such as “total of accepted values already processed”, and check whether each branch preserves that meaning.

Requirement → input/output contract → state needed → processing steps → code
“All longest words” → list of words → maximum length + result list
                   → find length, then collect matches → two scans

Choose state from the required output, not from a memorised program that looks similar. A count, a sum, and a list of matches require different updates even if their conditions are identical.

Ask what must remain true as you process input. A running maximum stores the largest value seen so far. A counter stores how many processed items meet a condition. A result list stores the accepted items in encounter order. This meaning tells you when each variable must change.

Do not initialise a maximum to 0 if all valid numbers can be negative. Use the first item after handling empty input, or choose a justified sentinel. Sorting to find a maximum is unnecessary and can change order; a scan is sufficient.

Worked example — all longest words priority/high

Contract: input is a list of strings; return a new list of every word of maximum length in original order, preserving duplicates. Empty input returns an empty list.

Steps: first determine maximum length, then collect matches. A length can safely start at 0 because string lengths are nonnegative.

def longest_words(words):
    maximum = 0  # String lengths cannot be negative.
    for word in words:
        if len(word) > maximum:
            maximum = len(word)  # Keep the greatest length seen so far.
    result = []  # Collect actual words, not their lengths.
    for word in words:
        if len(word) == maximum:  # A separate scan preserves all ties in order.
            result.append(word)
    return result

For ["red", "blue", "gold"], maximum progresses 0→3→4→4, then the second pass returns ["blue", "gold"]. Empty input executes neither loop and returns []. For ["", ""], both empty strings are valid longest words and both are returned. Returning the list lets the caller use it; printing inside the function does not meet the same contract.

Practice

Exam focus: HCI 2025 Q8 requires functions with different outputs: factors, a perfect-number test and a list of perfect numbers. HCI 2024 Q9 requires grid computations with particular outputs. The shared skill is decoding each contract. Before reading a solution, annotate the original 2025 Q8, PDF p.6 with each function’s input and return type; do not assume all three return the same kind of result.

Paper-and-pen check: use one normal example, one edge case, and one example designed to distinguish a tempting wrong interpretation. For “all matches”, include two matches; for “preserve order”, choose an input whose order sorting would change.

12A — original. Specify inputs, output and steps for positions(values, target), which returns every zero-based index where target occurs, preserving index order. Give expected results for ([3, 1, 3], 3) and ([], 3). Then implement it.

12B — original. Write smallest_values(values) for a list of numbers. Return all occurrences of the minimum in original order; empty input returns []. Explain why initialising the minimum to 0 fails for [5, 7].

Hints

12A: the output contains positions, not values. 12B: use the first value only after the empty case is handled.

Revision checklist

• 12.1 Identify inputs, outputs, constraints and required return types before coding.
• 12.2 Decompose a scenario into functions with clear interfaces.
• 12.3 Use modular and incremental approaches and distinguish their purposes.
• 12.4 Express sequence, selection and iteration in unambiguous pseudocode.
• 12.5 Trace an unfamiliar algorithm rather than relying on familiar variable names.
• 12.6 Separate printed output from returned values.
• 12.7 Use meaningful names, indentation and useful comments.
• 12.8 Plan normal and edge cases before implementing the complete solution.
• 12.9 Check that all requested functions, demonstrations and outputs are supplied.

Visual revision mindmap

Open this mindmap and its text version · All 21 mindmaps

Your mindmap framework

Centre: Python Chapter 1 — algorithms and problem solving. Build the six branches below. For each subbranch, add a short definition, a labelled sample and one exam trap from memory; then check the chapter.

flowchart LR
    C["12 • Revision map"]
    C --> B0["Decode the contract"]
    C --> B1["Decompose the problem"]
    C --> B2["Choose state"]
    C --> B3["Express the algorithm"]
    C --> B4["Verify the solution"]
    C --> B5["Visual checks and mistakes"]

• Decode the contract

  • Input types and valid domain.
  • Return versus print versus mutate.
  • Output shape: count, value, tuple or list.
  • All matches, ties, duplicates and required order.

• Decompose the problem

  • Identify smaller responsibilities.
  • Functions with clear inputs and outputs.
  • Modular: separate responsibilities.
  • Incremental: implement and test a small version, then extend.

• Choose state

  • Counter, sum or product.
  • Current minimum/maximum.
  • Result collection.
  • Give each variable a meaning that remains true after updates.

• Express the algorithm

  • Sequence, selection and iteration.
  • Clear pseudocode and bounds.
  • Derive steps before Python syntax.
  • Avoid unnecessary sorting or input mutation.

• Verify the solution

  • Normal and smallest valid input.
  • Empty input where allowed.
  • Equality, negative values, ties and duplicates.
  • Check all requested functions, outputs and demonstrations.

• Visual checks and mistakes

  • Requirement → state → updates → returned result.
  • Trace all-longest-words in two passes.
  • Compare expected output against a tempting wrong interpretation.
  • Avoid: first match for all; maximum initialised to 0 for negative-only input.

Close the notes and test the map: explain one branch aloud, sketch its sample, then answer a linked practice question. Mark any missing link to revisit.

Source trail

9569 §§1.1,1.3,1.5; school Python Introduction.

HCI 2022 Q8–9; 2023 Q8; 2024 Q9; 2025 Q8.

Source guide records provenance and original-paper locations.