11  Designing Algorithms

A useful theme for the chapter would be: design an algorithm before translating it into Python. Python lists hold references to objects, while NumPy arrays provide shaped storage with a common dtype. The same algorithmic ideas apply to both; the choice of representation affects which operations are convenient and their costs. The NumPy chapters already introduced vectorized operations, so this chapter can revisit their algorithmic costs.

11.0.1 Suggested learning outcomes

NoteLearning Outcomes

By the end of the chapter, students should be able to:

  • Turn a problem statement into precise inputs, outputs, assumptions, and constraints.
  • Express an algorithm using pseudocode or a flowchart.
  • Select an appropriate algorithmic pattern.
  • Explain why an algorithm works.
  • Estimate its time and memory requirements at an introductory level.
  • Implement and test the algorithm in Python.
  • Recognize common inefficient or unsafe approaches.

11.1 What is an algorithm?

  • Difference between a problem, an algorithm, and a Python implementation.
  • Properties of a good algorithm:
    • Correctness
    • Clarity
    • Termination
    • Efficiency
    • Generality
  • The same problem can have multiple correct algorithms.
  • Separating algorithm design from syntax and coding details.

11.2 Understanding the problem

  • Identify:
    • Inputs
    • Expected outputs
    • Valid and invalid input
    • Constraints
    • Special and boundary cases
  • Work small examples by hand before writing code.
  • State assumptions explicitly.
  • Write function contracts, including parameter and return-value descriptions.
  • Distinguish requirements from implementation choices.

11.3 Representing algorithms

  • Structured English.
  • Pseudocode.
  • Flowcharts, used selectively.
  • Trace tables for following changing variable values.
  • Translating pseudocode into Python.
  • Choosing meaningful variable names.
  • Breaking a large problem into smaller steps.

11.4 Fundamental algorithmic patterns

  • Sequence: perform steps in order.
  • Selection: choose between alternatives.
  • Iteration: repeat work using loops.
  • Accumulation:
    • Sum
    • Product
    • Count
    • Minimum or maximum
  • Search:
    • Find whether a value exists
    • Find its position
    • Find the first or last match
    • Find all matches
  • Filtering: select elements satisfying a condition.
  • Transformation: compute a new value for each element.
  • Pairwise processing:
    • Differences between adjacent measurements
    • Detecting transitions
    • Comparing neighboring values
  • Early termination when the result is already known.
  • Sentinel values and flags, including when to avoid them.

11.5 Efficient list and array processing

  • Traverse a sequence by value versus by index.
  • Perform a single pass when possible.
  • Avoid repeatedly calculating information that can be maintained incrementally.
  • Avoid unnecessary nested loops.
  • Avoid repeated copying or concatenation of large sequences.
  • Prefer building a result separately rather than repeatedly resizing the input.
  • Avoid adding or removing elements from a list while iterating forward over that same list: shifting positions can skip or repeat items. This is not a syntax error, and replacing an existing element without changing the length is a different operation.
  • Safe alternatives:
    • Build a new output list.
    • Use a list comprehension.
    • Mark elements for later removal.
    • Iterate over indices backward when in-place removal is genuinely required, removing only the item at the current index. Repeated deletions can still be costly because remaining elements may need to shift.
  • In-place processing versus producing a new result.
  • Memory and readability tradeoffs.
  • Python lists can grow using append; a NumPy array has a defined shape and size, and operations such as np.append create a new array rather than growing the original in place.
  • Revisit vectorized NumPy operations from the preceding chapters. Moving a linear pass into compiled code can reduce its runtime without changing its linear growth rate.

11.6 Common sequence-processing case studies

  • Computing statistics in one pass.
  • Removing invalid sensor readings.
  • Normalizing experimental measurements.
  • Detecting threshold crossings.
  • Finding peaks or sudden changes.
  • Computing moving differences or moving averages.
  • Merging or comparing two ordered datasets.
  • Removing duplicate values.
  • Rotating or reversing a sequence.
  • Checking whether data is sorted.
  • Finding the longest consecutive run satisfying a condition.

11.7 Correctness and reasoning

  • Preconditions and postconditions.
  • Informal reasoning about why an algorithm works.
  • Loop invariants introduced in accessible language:
    • “What is true before the first iteration and remains true after every iteration?”
  • Ensuring that every element is processed exactly as intended.
  • Off-by-one errors.
  • Correct treatment of the first and last elements.
  • Showing that loops and recursive algorithms terminate.
  • Comparing a trace with the intended result.

11.8 Introductory efficiency analysis

  • Why efficiency matters for engineering-scale data.
  • Input size, usually denoted by (n).
  • Counting work approximately rather than timing individual statements.
  • Growth-rate intuition:
    • Constant time: (O(1))
    • Linear time: (O(n))
    • Quadratic time: (O(n^2))
    • Logarithmic time: (O(n))
  • Count how loop bounds grow with input size rather than just counting loops. A loop over n items with constant work per item is linear; two full nested passes over n items are quadratic, but an inner loop of fixed length still gives linear work overall.
  • Why constants often matter less than growth rate for large inputs.
  • Time–memory tradeoffs.
  • Best-, worst-, and average-case behavior at a conceptual level.
  • Empirical timing as a complement to—not a replacement for—analysis.

11.9 Comparing alternative algorithms

Good classroom comparisons could include:

  • Repeatedly calling sum() versus maintaining a running total.
  • Linear search versus binary search. Binary search requires input already sorted under the same comparison rule. With constant-time indexing and comparisons, it needs at most logarithmically many comparisons; sorting beforehand has its own cost. Python’s bisect module finds insertion positions, so an exact-match search must also check the value at the returned position.
  • Nested-loop duplicate detection versus using a set. Set entries must be hashable; membership is typically constant-time on average, rather than guaranteed constant-time for every input.
  • Repeated list concatenation versus append. Concatenation copies existing entries; append has constant amortized cost, although an individual call may need to resize the list’s storage.
  • Removing elements during traversal versus constructing a filtered result.
  • Recomputing a moving-window sum versus updating it incrementally.
  • Iterative versus recursive implementations of the same problem.

11.10 Recursion

  • A function solving a problem using solutions to smaller instances.
  • The two essential components:
    • Base case
    • Recursive case
  • Making measurable progress toward the base case.
  • Tracing the call stack.
  • Local variables in separate function calls.
  • Returning values through recursive calls.
  • Common introductory examples:
    • Factorial
    • Greatest common divisor
    • Summing a list (avoid making a new slice at every call when comparing costs with an iterative sum)
    • Binary search
    • Processing nested lists
    • Recursive geometric patterns
    • Simple divide-and-conquer problems
  • Infinite recursion and missing base cases.
  • Python’s recursion-depth limitation. Each active call needs stack space; Python does not eliminate tail-recursive calls. An algorithm may terminate mathematically yet hit the interpreter’s recursion limit on a large input.
  • Recursive versus iterative solutions.
  • Why recursion is elegant for some problem structures but unnecessary for others.
  • Avoiding inefficient recursive examples such as naïve Fibonacci, or using them specifically to demonstrate repeated work.

11.11 Decomposition and helper functions

  • Divide a problem into cohesive subtasks.
  • Give each function one clear responsibility.
  • Separate:
    • Input/output
    • Computation
    • Validation
    • Presentation of results
  • Use helper functions to simplify recursive algorithms.
  • Avoid excessive reliance on global variables.
  • Design functions that can be independently tested and reused.

11.12 Testing algorithms

  • Test before assuming an algorithm is correct.
  • Normal cases.
  • Boundary cases:
    • Empty sequence
    • One element
    • Two elements
    • First or last element is the answer
  • Repeated values.
  • Negative and zero values.
  • Already sorted and reverse-sorted inputs.
  • Very large inputs.
  • Invalid inputs, where applicable.
  • Hand-calculated expected results.
  • Assertions and simple unit tests.
  • Randomized testing against a simpler reference implementation.

11.13 Common design mistakes

  • Coding before understanding the problem.
  • Confusing an index with the value at that index.
  • Changing a list’s length while traversing it.
  • Incorrect loop bounds.
  • Forgetting the empty-input case.
  • Initializing a minimum or maximum incorrectly.
  • Returning too early from a loop.
  • Failing to return a recursive result.
  • Writing recursion that does not approach its base case.
  • Using nested loops when one pass is sufficient.
  • Optimizing prematurely at the expense of correctness and clarity.

11.14 A repeatable design process

Students could be taught to follow this checklist:

  1. Define the inputs, outputs, and constraints.
  2. Create and solve a small example manually.
  3. Identify a suitable algorithmic pattern.
  4. Write pseudocode.
  5. Check boundary cases.
  6. Reason informally about correctness and termination.
  7. Estimate the time and memory costs.
  8. Translate the algorithm into a function.
  9. Test it systematically.
  10. Refine it only if greater efficiency or clarity is needed.

11.15 Engineering-focused exercises

  • Clean noisy experimental data.
  • Identify faulty sensor measurements.
  • Integrate sampled data using a simple numerical method.
  • Detect changes in a digital signal.
  • Analyze temperature or strain measurements.
  • Find the first time a simulated system exceeds a safe limit.
  • Compute cumulative energy consumption.
  • Search a calibration table.
  • Process nested component or assembly data recursively.
  • Compare the measured performance of two algorithms as the dataset grows.
Note

A particularly effective chapter structure would repeatedly use the cycle problem → hand-worked example → pseudocode → Python implementation → correctness argument → efficiency discussion → tests. This makes algorithm design feel like a practical engineering process rather than a collection of abstract computer-science rules.