Describe and use the process of stepwise refinement to express an algorithm to a level of detail from which the task may be programmed.
What is Stepwise Refinement?
Stepwise refinement (also called top‑down design) is a systematic method of developing an algorithm by repeatedly breaking a problem into smaller, more manageable sub‑problems until each part can be directly translated into code.
Why Use Stepwise Refinement?
Improves clarity and understanding of the problem.
Facilitates testing of individual components.
Reduces the risk of overlooking edge cases.
Provides a clear roadmap for programmers.
The Stepwise Refinement Process
Define the overall problem. Write a high‑level description of what the algorithm must achieve.
Identify major sub‑tasks. Decompose the problem into logical sections.
Refine each sub‑task. Break each section into smaller steps, adding detail each time.
Validate. Check that each refined step is unambiguous and testable.
Translate to code. When a step is sufficiently detailed, write the corresponding program fragment.
Refinement Levels – Example Table
Level
Focus
Typical Output
1
Problem statement
Natural‑language description of the overall task.
2
Major sub‑tasks
Bulleted list of high‑level functions or modules.
3
Detailed steps
Pseudocode or flow‑chart style description.
4
Implementation ready
Executable code fragments.
Worked Example – Finding the Maximum \cdot alue in a List
We will refine the problem from a simple description to a level ready for programming.
Level 1 – Problem Statement
Given a list of numbers, determine the largest number.
Level 2 – Major Sub‑tasks
Read the list of numbers.
Initialise a variable to hold the current maximum.
Compare each number with the current maximum and update if larger.
Output the final maximum value.
Level 3 – Detailed Steps (Pseudocode)
\$\$
\begin{aligned}
\text{Input } &\; \text{list } L \\
\text{max} &\; \leftarrow L[0] \\
\text{FOR } &\; i \; \text{from } 1 \text{ to } |L|-1 \\
\quad &\text{IF } L[i] > \text{max} \\
\quad &\quad \text{max} \leftarrow L[i] \\
\text{END FOR} \\
\text{Output } \text{max}
\end{aligned}
\$\$
Level 4 – Ready for Programming (Python Example)
def find_max(L):
max_val = L[0]
for i in range(1, len(L)):
if L[i] > max_val:
max_val = L[i]
return max_val
Applying Stepwise Refinement to a More Complex Task – Insertion Sort
Below is a concise illustration of how a sorting algorithm can be refined.
Level 1 – Problem Statement
Sort a list of numbers into non‑decreasing order using the insertion sort method.
Level 2 – Major Sub‑tasks
Iterate over each element starting from the second position.
Insert the current element into the already sorted portion of the list.
Shift larger elements one position to the right to make space.
Repeat until the entire list is sorted.
Level 3 – Detailed Steps (Pseudocode)
\$\$
\begin{aligned}
\text{FOR } &\; j \leftarrow 2 \text{ to } n \\
\quad &\text{key} \leftarrow A[j] \\
\quad &i \leftarrow j-1 \\
\quad &\text{WHILE } i > 0 \text{ AND } A[i] > \text{key} \\
\quad \quad &A[i+1] \leftarrow A[i] \\
\quad \quad &i \leftarrow i-1 \\
\quad \text{END WHILE} \\
\quad &A[i+1] \leftarrow \text{key} \\
\text{END FOR}
\end{aligned}
\$\$
Level 4 – Ready for Programming (Python Example)
def insertion_sort(A):
n = len(A)
for j in range(1, n):
key = A[j]
i = j - 1
while i >= 0 and A[i] > key:
A[i + 1] = A[i]
i -= 1
A[i + 1] = key
return A
Key Points to Remember
Each refinement step should add enough detail to make the next step unambiguous.
Maintain consistent naming of variables and sub‑routines throughout the refinement.
Validate logic at each level – use test data early to catch errors.
Document assumptions (e.g., input size, data type) as part of the refinement.
Practice Exercise
Refine the following problem using stepwise refinement to a level ready for implementation.
Problem: Given a string, count how many times each vowel (a, e, i, o, u) appears, ignoring case.
Suggested Steps for Students
Write a high‑level description of the task.
Identify sub‑tasks such as converting to lower case, iterating over characters, checking for vowels, and updating counts.
Develop detailed pseudocode using loops and conditional statements.
Translate the pseudocode into a programming language of your choice.
Suggested diagram: Flowchart showing the top‑down decomposition from the overall problem to individual loops and condition checks.