Explain modular design: top-down design, coupling, cohesion, and hierarchy charts
Describe the advantages of modular programming
Understand standard algorithms: linear search, binary search, bubble sort, merge sort
Compare algorithm efficiency and know Big O notation for each standard algorithm
Modular Design
Top-Down Design and Modular Programming
Modular programming breaks a large program into smaller, self-contained modules (subroutines/functions/procedures). Each module performs one task. The top-down design approach defines the overall structure first, then refines each level into smaller modules.
Coupling
Degree of interdependence between modules. Low coupling is desirable — modules should be as independent as possible, communicating only through well-defined interfaces (parameters). High coupling makes changes in one module break others.
Cohesion
Degree to which a module's responsibilities form a single, focused unit. High cohesion is desirable — a module should do one thing well. Low cohesion means a module does too many unrelated things and should be split.
Hierarchy Charts
Structure / Hierarchy Diagrams
A hierarchy chart (also called a structure diagram) shows the decomposition of a program into modules and the relationships between them. The top level is the main program; sub-levels are the subroutines called by each level above.
A hierarchy chart does NOT show the flow of data or the order of execution — it only shows the structure of the program (which modules call which). Use a flowchart or pseudo-code to show execution order.
Advantages of modular design: easier to develop in a team (different modules assigned to different developers); easier to test (unit test each module independently); easier to maintain and update (change one module without affecting others); modules can be reused across projects.
Standard Algorithms
Linear and Binary Search
Linear Search — O(n)
Check each element in sequence until the target is found or the list ends. Works on unsorted data. Simple to implement. For large n, slow on average — must check n/2 elements on average.
Binary Search — O(log n)
Requires a sorted list. Compare the middle element with target — if less, search left half; if greater, search right half. Halves search space each time. Very fast for large n.
For n=1,000,000: linear search may check 500,000 elements on average; binary search takes at most log₂(1,000,000) ≈ 20 comparisons. Binary search is dramatically faster but requires sorted data.
Sorting Algorithms
Bubble Sort and Merge Sort
Bubble Sort — O(n²)
Repeatedly compare adjacent elements and swap if out of order. After each pass, the largest unsorted element "bubbles" to its correct position. n-1 passes needed in worst case. Simple but very inefficient for large n.
Merge Sort — O(n log n)
Divide and conquer. Split list in half recursively until single elements remain; merge pairs of sorted lists. Always O(n log n) — much better than bubble sort for large n. Requires additional memory for the merging step.
For n=10,000: bubble sort ≈ 100,000,000 comparisons; merge sort ≈ 133,000 comparisons. Merge sort is dramatically better for large data sets.
Big O Notation
Complexity Summary
O(1) — Constant
Same time regardless of input size. E.g. accessing array element by index, hash table lookup (average).
O(log n) — Logarithmic
Time grows slowly as n increases. Doubles when n squares. E.g. binary search.
O(n) — Linear
Time grows proportionally with n. E.g. linear search, traversing a list.
O(n²) — Polynomial
Time grows with n squared. Nested loops. E.g. bubble sort, selection sort. Tractable but slow for large n.
Exam Practice
OCR H446 Style · 5 marks
Explain two advantages of using modular design when developing a large software system, and justify why a merge sort would be preferable to a bubble sort for sorting a list of 50,000 student records.
[5 marks]
2
Modular advantage 1: Different modules can be developed and tested in parallel by different team members. Since modules have well-defined interfaces, developers do not need to understand the internal workings of other modules — reducing development time and errors.
1
Modular advantage 2: Individual modules can be unit-tested independently, making bugs easier to isolate and fix. A module once tested can be reused in other programs.
2
Merge sort justification: Merge sort has O(n log n) complexity, so for 50,000 records it performs approximately 50,000 × log₂(50,000) ≈ 780,000 comparisons. Bubble sort O(n²) would require approximately 2,500,000,000 comparisons in the worst case — making merge sort orders of magnitude faster for this data size.
Common Mistakes
Don't Lose Marks
!
Saying binary search works on any list — binary search requires a sorted list as a precondition. Always state this. If the data is unsorted, the list must first be sorted before binary search can be applied — and sorting takes additional time.
!
Confusing coupling and cohesion — coupling measures interdependence between modules (want LOW coupling); cohesion measures how focused a single module is (want HIGH cohesion). Students frequently reverse these. Remembered: "modules should couple loosely and cohere strongly".
!
Not giving a numerical justification for algorithm choice — when an exam question asks you to justify sorting algorithm selection, giving a vague answer ("merge sort is faster") scores 0-1. Always provide the Big O complexities of both and, ideally, a numerical comparison for the given n.