11  Designing Algorithms

A useful theme for the chapter would be: design an algorithm before translating it into Python. Since Python distinguishes between lists and true numerical arrays, you could introduce the ideas using lists and then note how they apply to NumPy arrays later.

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 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.
  • Do not add or remove elements from a list while iterating over that same list.
  • Safe alternatives:
    • Build a new output list.
    • Use a list comprehension.
    • Mark elements for later removal.
    • Iterate backward when in-place removal is genuinely required.
  • In-place processing versus producing a new result.
  • Memory and readability tradeoffs.
  • Python lists versus fixed-size arrays and NumPy arrays.
  • A first introduction to vectorized NumPy operations, if NumPy is in the course.

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 must be 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))
  • Single loops versus nested loops.
  • 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.
  • Nested-loop duplicate detection versus using a set.
  • Repeated list concatenation versus append.
  • 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
    • Binary search
    • Processing nested lists
    • Recursive geometric patterns
    • Simple divide-and-conquer problems
  • Infinite recursion and missing base cases.
  • Python’s recursion-depth limitation.
  • 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.