Problem solving concepts and top-down design
Problem solving concepts and top-down design: definitions, stepwise refinement, decomposition, abstractions, specifications, and implementing solutions in Python with examples.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Engineers solve real-world problems: estimating loads, processing sensor data, or automating reports. A clear problem-solving method and top-down design help you convert a vague requirement into a correct, readable, and maintainable Python program.
Key ideas
- Assumption — A condition you take as true about inputs or environment (e.g., input is an integer). In code, assumptions are checked with validation.
- Precondition — A condition that must hold before a function runs (e.g., n > 0). If preconditions are met, the function guarantees the postcondition.
- Postcondition — A condition guaranteed after a function runs if preconditions held (e.g., returns the minimum of a non-empty list).
- Algorithm — A finite, unambiguous, and effective sequence of steps that, starting from an input, produces the required output and terminates.
- Correctness — A program is correct if, for all inputs satisfying the preconditions, its outputs satisfy the postconditions. Partial correctness means postconditions hold if the program terminates; total correctness means partial correctness plus termination.
- Top-down design — Also called stepwise refinement. Start from the overall problem and repeatedly decompose it into simpler subproblems until each is simple enough to implement directly.
- Decomposition — Breaking a problem into smaller parts (modules/functions) that can be designed, implemented, tested, and reasoned about independently.
- Abstraction — Focusing on what a module does (its interface) rather than how it does it (its implementation). In Python, a function name, parameters, and docstring are the abstraction boundary.
- Modularity — Organizing code as independent, cohesive modules with clear interfaces. Improves readability, testing, and reuse.
- Cohesion — How strongly related the responsibilities of a module are. High cohesion is desirable (one focused purpose).
- Coupling — The degree of interdependence between modules. Low coupling is desirable (few, simple interfaces; minimal shared state).
- Interface — The exposed way to use a module/function: its name, parameters, return value, and documented behavior.
- Stub — A temporary, minimal implementation of a function that returns placeholder values so other parts can be developed and tested.
- Driver — A small piece of code that calls a function/module with test inputs to verify behavior.
- Pseudocode — A language-agnostic description of an algorithm, close to natural language, used to plan before coding.
- Flowchart/Hierarchy (structure) chart — Visuals to aid design. A hierarchy chart shows modules as boxes: main at the top, sub-functions below, arrows indicating calls.
- Test case — A specific input with expected output to check correctness. Include normal, boundary, and edge cases.
- Edge case — An input at the extreme ends or special situations (e.g., empty list, zero, negative number if allowed).
- Invariant — A property that remains true during execution of a segment, especially during each iteration of a loop.
- Loop invariant method (exact statement) — To prove a loop is partially correct: (1) Identify an invariant P; (2) Show initialization: P holds before the first iteration; (3) Show maintenance: assuming P holds before an iteration, it holds after one iteration; (4) When the loop terminates, combine P with the negated loop condition to conclude the postcondition. To prove total correctness, also show termination via a decreasing measure bounded below.
- Algorithmic complexity (Big-O, brief) — A high-level measure of how running time or space grows with input size n (e.g., O(n), O(n log n)). Use it qualitatively during design to choose efficient approaches.
Typical top-down design process (stepwise refinement):
- State the problem clearly (specifications, assumptions, pre/postconditions).
- Decompose into major stages (input, processing, output).
- Refine each stage into smaller steps (e.g., validate input, compute statistics, format output).
- Define function interfaces (names, parameters, returns, docstrings) for each step.
- Write pseudocode or a hierarchy chart.
- Implement functions; use stubs initially if needed.
- Write drivers/unit tests; test normal and edge cases.
- Review correctness (invariants for loops), readability, and complexity.
- Document and finalize.
Diagram to draw for a typical exam answer: hierarchy chart
- Draw a large box labeled "main()" at the top.
- Draw three boxes below it, left to right: "read_input()", "process_data()", "display_results()".
- Draw arrows from main() to each of these three boxes to indicate calls.
- Under process_data(), draw two boxes: "compute_min_max_mean()" and "validate_numbers()" with arrows from process_data() to each.
- Label each arrow "calls"; label each box with a brief responsibility note (e.g., "returns min, max, mean").
Formulas
Syntax to remember (Python):
def function_name(param1: Type, param2: Type = default) -> ReturnType:
"""One-line summary. Preconditions, postconditions."""
# body
if __name__ == "__main__":
main()
pass # placeholder in a stub
raise ValueError("message") # for violated preconditions
x = int(input("Prompt: ")) # input as integer
tokens = input().split() # read space-separated values
print(f"Mean: {mean:.2f}") # formatted output
from typing import List, Tuple, Dict # common type hints
Pseudocode conventions (not code):
INPUT n
IF n <= 0 THEN ERROR
ELSE READ n numbers
COMPUTE min, max, mean
OUTPUT results
Worked examples
Example 1 — Statistics of a list using top-down design Problem: Read an integer n (> 0), then read n integers in one line. Compute and print the minimum, maximum, and arithmetic mean.
Design (top-down):
- main(): orchestrates calls.
- read_count(): get and validate n (> 0).
- read_numbers(n): read n integers; validate count.
- compute_stats(nums): return (min, max, mean).
- display_stats(min_v, max_v, mean_v): formatted output.
Complete Python program:
from typing import List, Tuple
def read_count() -> int:
while True:
try:
n = int(input("Enter count of integers (>0): "))
if n > 0:
return n
else:
print("Invalid. Try again.")
except ValueError:
print("Invalid. Try again.")
def read_numbers(n: int) -> List[int]:
while True:
line = input(f"Enter {n} integers separated by spaces: ")
parts = line.split()
if len(parts) != n:
print("Invalid. Try again.")
continue
try:
return [int(p) for p in parts]
except ValueError:
print("Invalid. Try again.")
def compute_stats(nums: List[int]) -> Tuple[int, int, float]:
# Preconditions: nums is non-empty
minimum = min(nums)
maximum = max(nums)
mean = sum(nums) / len(nums)
return minimum, maximum, mean
def display_stats(min_v: int, max_v: int, mean_v: float) -> None:
print(f"Min: {min_v}")
print(f"Max: {max_v}")
print(f"Mean: {mean_v:.2f}")
def main() -> None:
n = read_count()
nums = read_numbers(n)
min_v, max_v, mean_v = compute_stats(nums)
display_stats(min_v, max_v, mean_v)
if __name__ == "__main__":
main()
Sample input (user types): 5 3 7 -2 10 0
Exact output: Enter count of integers (>0): Enter 5 integers separated by spaces: Min: -2 Max: 10 Mean: 3.60
Notes: Here, the prompts appear before each user input. The values printed are correct for the given numbers.
Example 2 — Minimal coins (greedy decomposition) Problem: Given a non-negative integer amount in rupees, compute the minimal number of coins needed using denominations {10, 5, 2, 1}. Print how many coins of each denomination, and the total count.
Design:
- main(): read amount; call make_change(); display.
- make_change(amount): greedy from largest to smallest denomination.
- display_change(counts): formatted listing.
Complete Python program:
from typing import Dict, List
def read_amount() -> int:
while True:
try:
amt = int(input("Enter amount in rupees (>=0): "))
if amt >= 0:
return amt
else:
print("Invalid. Try again.")
except ValueError:
print("Invalid. Try again.")
def make_change(amount: int, denoms: List[int] = [10, 5, 2, 1]) -> Dict[int, int]:
counts: Dict[int, int] = {d: 0 for d in denoms}
remaining = amount
for d in denoms:
if remaining == 0:
break
counts[d] = remaining // d
remaining = remaining % d
return counts
def display_change(counts: Dict[int, int]) -> None:
total = sum(counts.values())
for d in sorted(counts.keys(), reverse=True):
print(f"Denomination {d}: {counts[d]}")
print(f"Total coins: {total}")
def main() -> None:
amount = read_amount()
counts = make_change(amount)
display_change(counts)
if __name__ == "__main__":
main()
Sample input (user types): 28
Exact output: Enter amount in rupees (>=0): Denomination 10: 2 Denomination 5: 1 Denomination 2: 1 Denomination 1: 1 Total coins: 5
Example 3 — Text analysis with palindrome check (functional decomposition) Problem: Read a line of text. Normalize it (keep alphanumeric characters only, convert to lowercase). Report whether it is a palindrome, the number of vowels, and the number of words.
Design:
- main(): orchestrate all steps.
- read_text(): input line from user.
- normalize(s): keep only [a–z0–9], to lowercase.
- is_palindrome(s): check s == s[::-1].
- count_vowels(s): count a, e, i, o, u in normalized string.
- count_words(raw): split on whitespace and count.
- display_results(...): print nicely.
Complete Python program:
from typing import Tuple
def read_text() -> str:
return input("Enter a line of text: ")
def normalize(s: str) -> str:
return "".join(ch.lower() for ch in s if ch.isalnum())
def is_palindrome(s: str) -> bool:
return s == s[::-1]
def count_vowels(s: str) -> int:
vowels = set("aeiou")
return sum(1 for ch in s if ch in vowels)
def count_words(raw: str) -> int:
return len(raw.split())
def display_results(is_palin: bool, vowels: int, words: int) -> None:
print(f"Palindrome: {'Yes' if is_palin else 'No'}")
print(f"Vowel count: {vowels}")
print(f"Word count: {words}")
def main() -> None:
raw = read_text()
norm = normalize(raw)
result = is_palindrome(norm)
v = count_vowels(norm)
w = count_words(raw)
display_results(result, v, w)
if __name__ == "__main__":
main()
Sample input (user types): Never odd or even
Exact output: Enter a line of text: Palindrome: Yes Vowel count: 6 Word count: 4
Common mistakes
- No validation: assuming inputs are valid; fails on edge cases (n = 0, empty line, negative amount).
- Hidden coupling: functions that read input or print unexpectedly; instead, separate computation from I/O so functions are testable.
- Poor naming and missing docstrings: makes maintenance and testing difficult.
- Ignoring termination: loops without a decreasing measure or correct condition; risk of infinite loops.
- Not using stubs/drivers: delaying testing until the end; harder debugging.
- Formatting output inconsistently: e.g., printing too many decimals; not matching required formats.
- Mixing concerns: combining normalization logic with palindrome check; harder to reuse or test independently.
For your exam
Expect questions of these types:
- Definitions: problem, specification, precondition/postcondition, correctness (partial/total), abstraction, modularity, cohesion, coupling, top-down design, stub, driver, invariant.
- Short notes: stepwise refinement with a small diagram; hierarchy chart vs flowchart; pseudocode conventions; greedy vs divide-and-conquer choices for simple problems.
- Diagrams: draw and label a hierarchy (structure) chart for a described problem. Include module names and responsibilities; arrows labeled "calls".
- Design question: Given a problem statement, write the specification, decompose into modules, write pseudocode, and outline function interfaces (parameters and returns). Provide assumptions, preconditions, and postconditions for core functions.
- Program: Write a complete Python program using top-down design and functions. Include input validation, clear function boundaries, and formatted output.
- Reasoning: Use a loop invariant to argue partial correctness of a simple loop (e.g., finding max). Show initialization, maintenance, and termination.
A full-marks answer usually includes:
- Clear, exact definitions in your own words plus textbook-style precision.
- A well-labeled hierarchy chart when asked.
- Pseudocode or structured steps before code.
- Clean Python code with functions, docstrings/comments, validation, and consistent formatting.
- Consideration of edge cases and brief reasoning about correctness/termination.
Quick check
- Define top-down design and list its main steps in order.
- What is the difference between a precondition and a postcondition? Give one example each.
- For the denominations {10, 5, 2, 1}, what is the minimal number of coins for 23 rupees, and why does a greedy algorithm work here?
Answers: 1) Start from the overall problem and repeatedly decompose into smaller subproblems until directly implementable; steps: specify, decompose, refine, define interfaces, pseudocode, implement (with stubs), test (drivers), review. 2) Precondition: must hold before a function runs (e.g., list is non-empty); Postcondition: guaranteed after it runs if preconditions held (e.g., returned value equals the maximum of the list). 3) 4 coins: 10+10+2+1 (counts 10×2, 2×1, 1×1); greedy is optimal for these canonical denominations because choosing the largest possible coin at each step never blocks an optimal solution.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?