Cambridge AS & A Level9608

Algorithm design methods

Computer Science 9608 Chapter Notes

What this chapter covers

Algorithm design methods
ShareWhatsAppPost
Algorithm design methods notes

Unable to load PDF

The notes viewer could not load. Please refresh the page.

Read online free. Download a watermarked copy with a free account.

Read the notes

The full Algorithm design methods notes as text: skim, search, and jump between subtopics.

~20 min read

In this chapter

  1. 1Stepwise Refinement & Structure Charts
  2. 2Advanced Searching: The Binary Search
  3. 3Efficient Sorting: The Insertion Sort
  4. 4Comparing Algorithms: Time & Space Complexity
  5. 5Abstract Data Types (ADTs)
  6. 6Linear ADTs: Stacks and Queues
  7. 7Dynamic Data Structures: Linked Lists
  8. 8Non-Linear Data Structures: Binary Trees

1. Stepwise Refinement & Structure Charts

Algorithm design often starts with a complex problem. Stepwise refinement is the process of breaking this problem down into smaller, more manageable sub-problems. This is also known as decomposition. We repeat this process until each sub-problem is simple enough to be represented as a single program module (like a procedure or function). A structure chart is a diagram that visualises this decomposition. It shows the overall architecture of the solution, including the different modules, their hierarchy (which module calls which), and the data passed between them (parameters). It is a top-down design tool, focusing on what needs to be done, not how it is done.

Key term

Decomposition: The process of breaking down a complex problem or system into smaller, more manageable parts that are easier to understand, design, and implement.

Examiner insight

Examiners award marks for clearly showing the hierarchy of modules and the correct direction of parameter passing. Pay attention to which data is needed by each module.

Common pitfall

Confusing a structure chart with a program flowchart. Structure charts show modular hierarchy and data flow, not the step-by-step logical sequence of instructions.

Worked example 16 marks

A program is required to read the marks for a class of 30 students. It must calculate the average mark, and then count and display the number of students who scored above the average. Decompose this problem and represent the solution using a structure chart.

  1. 1

    Step 1: Decompose the main problem. The top-level module could be 'Process Student Marks'.

  2. 2

    Step 2: Identify the main sub-tasks. These are: reading the marks, calculating the average, and counting students above average.

  3. 3

    Step 3: Further decomposition. 'Calculate Average' needs the marks and the count of students. 'Count Above Average' needs the marks and the calculated average.

  4. 4

    Step 4: Draw the structure chart. The root is 'Process Student Marks'. This main module calls three sub-modules in sequence: 'ReadMarks', 'CalculateAverage', and 'CountAboveAverage'.

  5. 5

    Step 5: Show parameter passing. 'ReadMarks' passes the array of marks up to the main module. The main module passes the marks array down to 'CalculateAverage' and 'CountAboveAverage'. 'CalculateAverage' passes the calculated average up to the main module. The main module passes this average down to 'CountAboveAverage'. 'CountAboveAverage' passes the final count up to the main module, which would then handle the output.

  6. 6

    Step 6: Refine the chart with symbols. Use rectangles for modules. Use arrows with an empty circle for data parameters (e.g., `MarksArray`, `AverageMark`). The final chart shows 'ProcessStudentMarks' at the top, with calls to 'ReadMarks', 'CalculateAverage', and 'CountAboveAverage' below it, with arrows indicating the flow of parameters like `StudentMarks` and `Average` between them.

Recap

  • Stepwise refinement breaks a large problem into smaller sub-problems.
  • Structure charts are a visual representation of the modular design of a program.
  • They show the hierarchy of modules and the parameters passed between them.
  • A rectangle represents a module (procedure or function).
  • An arrow with a circle at the end represents a parameter being passed.
  • Structure charts are for design; they do not show logic like loops or decisions.

Quick check

  1. What is the primary purpose of a structure chart?1 mark
  2. What is the name of the design process that structure charts are based on?1 mark

2. Advanced Searching: The Binary Search

A binary search is a highly efficient algorithm for finding an item in a sorted list. It works by a 'divide and conquer' strategy. Instead of checking items one by one (like a linear search), it first checks the middle item of the list. If this is the target item, the search is over. If the target item is smaller, the search continues in the lower half of the list. If it's larger, the search continues in the upper half. This process of halving the search space is repeated until the item is found or the search space is empty. The crucial pre-condition is that the list must be sorted.

Mid ← (LowerBound + UpperBound) DIV 2

Time Complexity: O(log n)

Key term

Divide and Conquer: An algorithmic strategy where a problem is repeatedly broken down into two or more sub-problems of the same type, until they become simple enough to be solved directly.

Examiner insight

Examiners look for a clear trace table showing the values of the pointers (lower, upper, mid) and the comparisons made at each iteration of the search.

Common pitfall

Forgetting that a binary search requires the data to be sorted beforehand. Another common error is an 'off-by-one' mistake when updating the LowerBound or UpperBound (e.g., setting `UpperBound = Mid` instead of `Mid - 1`).

Fun fact

The 'guess the number' game is a perfect real-world example. If you have to guess a number between 1 and 1000, a binary search strategy guarantees you will find it in 10 guesses or fewer.

Worked example 15 marks

Trace a binary search to find the number 23 in the following sorted array: [4, 8, 11, 15, 23, 28, 33, 40]. Show the values of `LowerBound`, `UpperBound`, and `Mid` at each step.

  1. 1

    Initial state: Array = [4, 8, 11, 15, 23, 28, 33, 40], Target = 23. Let's use 1-based indexing.

  2. 2

    Pass 1: LowerBound = 1, UpperBound = 8. Mid = (1 + 8) DIV 2 = 4. Value at index 4 is 15. Since 23 > 15, the target is in the upper half. New LowerBound = Mid + 1.

  3. 3

    Pass 2: LowerBound = 5, UpperBound = 8. Mid = (5 + 8) DIV 2 = 6. Value at index 6 is 28. Since 23 < 28, the target is in the lower half. New UpperBound = Mid - 1.

  4. 4

    Pass 3: LowerBound = 5, UpperBound = 5. Mid = (5 + 5) DIV 2 = 5. Value at index 5 is 23. The target is found at index 5. Search terminates.

Recap

  • A binary search is used to find an item in a sorted list.
  • It works by repeatedly dividing the search interval in half.
  • Its time complexity is logarithmic, O(log n), making it very fast for large lists.
  • The list must be sorted before a binary search can be performed.
  • The algorithm maintains a `LowerBound`, `UpperBound`, and `Mid` pointer to manage the search space.

Quick check

  1. What is the essential pre-condition for performing a binary search?1 mark
  2. If a sorted list has 1024 items, roughly how many comparisons will a binary search take in the worst case?2 marks

3. Efficient Sorting: The Insertion Sort

An insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by taking each unsorted element and 'inserting' it into its correct position within the sorted part of the array. Imagine you are sorting a hand of playing cards: you pick up one card at a time and insert it into the correct position in the cards you are already holding. The algorithm is 'in-place', meaning it sorts the list without requiring extra memory. It is efficient for small datasets or datasets that are already partially sorted.

Best-case Time Complexity: O(n)

Average/Worst-case Time Complexity: O(n^2)

Key term

In-place sort: A sorting algorithm which transforms input using no auxiliary data structure, meaning the input is overwritten by the output as the algorithm executes.

Examiner insight

Be prepared to compare the performance of an insertion sort with a bubble sort. Examiners often ask about the number of comparisons and swaps in best-case and worst-case scenarios.

Common pitfall

When shifting elements to make space for the item being inserted, students sometimes overwrite a value before it has been moved, or they shift one too many or one too few elements.

Worked example 15 marks

Perform an insertion sort on the array [7, 3, 9, 2, 5]. Show the state of the array after each pass (after each element is inserted into the sorted sub-array).

  1. 1

    Initial Array: [7, 3, 9, 2, 5]. The sorted sub-array is [7].

  2. 2

    Pass 1 (insert 3): Compare 3 with 7. 3 is smaller, so shift 7 right. Insert 3. Array: [3, 7, 9, 2, 5]. Sorted sub-array is [3, 7].

  3. 3

    Pass 2 (insert 9): Compare 9 with 7. 9 is larger, so it's in the correct place. Array: [3, 7, 9, 2, 5]. Sorted sub-array is [3, 7, 9].

  4. 4

    Pass 3 (insert 2): Compare 2 with 9, 7, and 3. Shift 9, 7, and 3 right. Insert 2. Array: [2, 3, 7, 9, 5]. Sorted sub-array is [2, 3, 7, 9].

  5. 5

    Pass 4 (insert 5): Compare 5 with 9 and 7. Shift 9 and 7 right. Insert 5. Array: [2, 3, 5, 7, 9]. Sorted sub-array is [2, 3, 5, 7, 9].

  6. 6

    Final Sorted Array: [2, 3, 5, 7, 9].

Recap

  • Insertion sort builds a sorted list by taking one element at a time and inserting it into its correct position.
  • It is an in-place sorting algorithm.
  • Its average and worst-case time complexity is O(n^2).
  • Its best-case time complexity (for an already sorted list) is O(n).
  • It is generally more efficient than bubble sort in practice.

Quick check

  1. What is the time complexity of an insertion sort if the list is already sorted in reverse order?1 mark

4. Comparing Algorithms: Time & Space Complexity

When we have different algorithms to solve the same problem, we need a way to compare them. The two main criteria are time complexity and space complexity. Time complexity measures how the execution time of an algorithm grows with the size of the input (n). Space complexity measures how the amount of memory it requires grows. We use Big O notation to describe this growth. For example, O(n) (linear time) means the runtime grows proportionally to the input size, while O(n^2) (quadratic time) means it grows much faster. An algorithm with a lower order of Big O complexity is generally more efficient for large inputs.

O(1): Constant Time (e.g., accessing an array element)

O(log n): Logarithmic Time (e.g., binary search)

O(n): Linear Time (e.g., linear search)

O(n^2): Quadratic Time (e.g., bubble sort, insertion sort)

Key term

Time Complexity: A measure of the amount of time an algorithm takes to run as a function of the length of the input, often expressed using Big O notation.

Examiner insight

Students who can explain *why* an algorithm has a certain Big O complexity (e.g., 'binary search is O(log n) because it halves the search space with each comparison') score higher than those who just state the value.

Common pitfall

Assuming that an algorithm with a better Big O complexity is always faster. For very small input sizes, an O(n^2) algorithm might be faster than an O(n log n) algorithm due to simpler instructions and lower constant overhead.

Worked example 14 marks

Algorithm A has a time complexity of O(n) and Algorithm B has a time complexity of O(log n). For a dataset of 1,000,000 items, explain which algorithm is more efficient and why.

  1. 1

    Step 1: Identify the complexities. Algorithm A is linear time, O(n). Algorithm B is logarithmic time, O(log n).

  2. 2

    Step 2: Understand the growth. O(n) means time is proportional to the number of items, n. O(logn) means time grows by one unit each time the number of items doubles. This is much slower growth.

  3. 3

    Step 3: Apply to the dataset size. For n = 1,000,000, Algorithm A will take roughly 1,000,000 steps. For Algorithm B, the number of steps will be log₂(1,000,000), which is approximately 20.

  4. 4

    Step 4: Conclude. Algorithm B is vastly more efficient for a large dataset. The logarithmic growth means its runtime increases very slowly as the dataset size grows, whereas the linear algorithm's runtime increases directly with the size.

Recap

  • Algorithms are compared based on time and space complexity.
  • Big O notation describes how performance scales with input size 'n'.
  • Common complexities include O(1), O(log n), O(n), and O(n^2).
  • An algorithm with a lower Big O complexity is more scalable and efficient for large inputs.
  • Space complexity refers to the memory requirements of an algorithm.

Quick check

  1. Which has a better time complexity for large lists: linear search or binary search?1 mark
  2. What does O(1) complexity mean?1 mark

5. Abstract Data Types (ADTs)

An Abstract Data Type (ADT) is a high-level, logical model of a data structure. It defines a collection of data and a set of operations that can be performed on that data, but it hides the implementation details. Think of it as a 'black box'. You know what it does (its interface), but you don't need to know how it does it (its implementation). For example, a 'List' ADT would define operations like `add item`, `remove item`, `find item`, without specifying if the list is implemented using an array or a linked list. This separation of interface and implementation is a core principle in computer science called abstraction.

Key term

Abstract Data Type (ADT): A logical description of a collection of data and the set of operations that can be performed on that data, independent of its specific implementation.

Examiner insight

Examiners reward clear definitions that separate the logical model (the ADT) from the physical implementation (the data structure). Using an analogy, like a car's dashboard, can be effective.

Common pitfall

Confusing an ADT with a data structure. A 'Stack' is an ADT. An array used to implement a stack is a data structure. The ADT is the 'what', the data structure is the 'how'.

Worked example 14 marks

Explain why a Stack is considered an Abstract Data Type. Describe its fundamental operations.

  1. 1

    Step 1: Define ADT in context. An ADT separates the logical concept from the physical implementation.

  2. 2

    Step 2: Apply to Stack. A Stack is defined by its behaviour: Last-In, First-Out (LIFO). This is a logical description.

  3. 3

    Step 3: Describe operations. The operations on a stack are defined abstractly: `PUSH` (add an item to the top), `POP` (remove an item from the top), `PEEK` (view the top item without removing it), and `isEmpty` (check if the stack is empty).

  4. 4

    Step 4: Explain abstraction. We can talk about pushing and popping from a stack without needing to know if it's implemented using an array, a linked list, or another data structure. This hiding of implementation details is what makes it an ADT.

Recap

  • An ADT is a logical model for a data structure.
  • It specifies a set of data and the operations on that data.
  • The implementation of an ADT is kept separate and hidden (abstraction).
  • Examples of ADTs include Stacks, Queues, Lists, and Dictionaries.
  • ADTs allow us to reason about data structures at a higher level.

Quick check

  1. What is the key principle that separates an ADT from a data structure?1 mark

6. Linear ADTs: Stacks and Queues

Stacks and Queues are two fundamental linear ADTs. A Stack follows a Last-In, First-Out (LIFO) principle. Think of a stack of plates: you add a new plate to the top, and you take a plate from the top. The main operations are `PUSH` (add to top) and `POP` (remove from top). A Queue follows a First-In, First-Out (FIFO) principle. Think of a line at a supermarket checkout: the first person in line is the first person served. The main operations are `ENQUEUE` (add to the back) and `DEQUEUE` (remove from the front). Both can be implemented using static arrays or dynamic linked lists.

Stack Operations: PUSH(item), POP(), PEEK()

Queue Operations: ENQUEUE(item), DEQUEUE(), PEEK()

Key term

LIFO (Last-In, First-Out): A principle of processing data where the last item added to a structure is the first one to be removed, characteristic of a stack.

Common pitfall

Mixing up LIFO and FIFO, or confusing the operation names (e.g., saying 'Push' for a queue). When using arrays, managing the pointers for a circular queue can be tricky.

Fun fact

The 'Undo' feature in most software (like Ctrl+Z) is implemented using a stack. Each action is pushed onto the stack, and 'Undo' simply pops the most recent action off.

Worked example 15 marks

A queue is implemented using a linear array with pointers `Front` and `Rear`. The queue is of size 6. Show the state of the queue and the pointers after the following operations: ENQUEUE(A), ENQUEUE(B), ENQUEUE(C), DEQUEUE, ENQUEUE(D). Assume initial state is Front=0, Rear=-1.

  1. 1

    Initial: [ , , , , , ] Front=0, Rear=-1

  2. 2

    ENQUEUE(A): Item A is added. Rear becomes 0. Queue: [A, , , , , ] Front=0, Rear=0

  3. 3

    ENQUEUE(B): Item B is added. Rear becomes 1. Queue: [A, B, , , , ] Front=0, Rear=1

  4. 4

    ENQUEUE(C): Item C is added. Rear becomes 2. Queue: [A, B, C, , , ] Front=0, Rear=2

  5. 5

    DEQUEUE: Item at Front is removed. Front becomes 1. Queue: [ , B, C, , , ] Front=1, Rear=2

  6. 6

    ENQUEUE(D): Item D is added. Rear becomes 3. Final Queue: [ , B, C, D, , ] Front=1, Rear=3

Recap

  • A Stack is a LIFO (Last-In, First-Out) data structure.
  • A Queue is a FIFO (First-In, First-Out) data structure.
  • Stack operations are PUSH and POP.
  • Queue operations are ENQUEUE and DEQUEUE.
  • They can be implemented using arrays or linked lists.
  • Stacks are used for function calls and undo features; queues are used for print jobs and buffers.

Quick check

  1. Which principle does a stack follow: LIFO or FIFO?1 mark
  2. What is the term for adding an element to a queue?1 mark

7. Dynamic Data Structures: Linked Lists

A linked list is a linear, dynamic data structure where elements are not stored at contiguous memory locations. Instead, each element, called a 'node', contains two parts: the data itself, and a pointer (or link) to the next node in the sequence. The last node points to NULL, indicating the end of the list. Because they are dynamic, linked lists can easily grow and shrink at runtime, which is a major advantage over static arrays. Inserting or deleting an element in the middle of a linked list is very efficient, as it only requires updating a few pointers, without the need to shift other elements.

Node Structure: [ Data | Pointer ]

Key term

Dynamic Data Structure: A data structure that can change its size during program execution, allocating and deallocating memory as needed.

Examiner insight

Diagrams are essential for linked list questions. Marks are given for correctly updating pointers, including the start pointer and null pointers. Be sure to handle edge cases like inserting at the beginning or end of the list.

Common pitfall

Forgetting to update all necessary pointers during insertion or deletion. A classic mistake is changing a node's 'next' pointer before using it to access the subsequent node, effectively losing the rest of the list.

Worked example 15 marks

A linked list stores names and is maintained in alphabetical order. The list currently contains 'Ali' -> 'Ben' -> 'David'. Draw diagrams to show how the list is modified to insert the name 'Chen'.

  1. 1

    Step 1: Initial state. The list is: StartPointer -> [Ali | ptr] -> [Ben | ptr] -> [David | NULL].

  2. 2

    Step 2: Create the new node. A new node is created for 'Chen': [Chen | NULL].

  3. 3

    Step 3: Traverse the list to find the insertion point. Start at 'Ali'. 'Chen' > 'Ali', so move to the next node, 'Ben'. 'Chen' > 'Ben', so move to the next node, 'David'. 'Chen' < 'David', so the insertion point is between 'Ben' and 'David'.

  4. 4

    Step 4: Update pointers. The pointer of the new 'Chen' node must be set to point to the 'David' node. The pointer of the 'Ben' node must be updated to point to the new 'Chen' node.

  5. 5

    Step 5: Final state diagram. The list is now: StartPointer -> [Ali | ptr] -> [Ben | ptr] -> [Chen | ptr] -> [David | NULL]. The link between 'Ben' and 'David' has been broken and rerouted through 'Chen'.

Recap

  • A linked list is a dynamic data structure made of nodes.
  • Each node contains data and a pointer to the next node.
  • The list is accessed via a start pointer, and the last node points to NULL.
  • Insertion and deletion are efficient as they only require pointer changes.
  • Unlike arrays, linked lists do not require contiguous memory.

Quick check

  1. What are the two components of a node in a simple linked list?2 marks
  2. What value does the pointer in the last node of a linked list hold?1 mark

8. Non-Linear Data Structures: Binary Trees

A binary tree is a non-linear, hierarchical data structure where each node can have at most two children, referred to as the left child and the right child. The topmost node is called the root. A Binary Search Tree (BST) is a special type of binary tree with a specific ordering property: for any given node, all values in its left sub-tree are less than the node's value, and all values in its right sub-tree are greater. This property makes searching for data very efficient, similar to a binary search. We can process the nodes in a tree using different traversal algorithms: in-order, pre-order, and post-order.

In-order Traversal: Left, Node, Right

Pre-order Traversal: Node, Left, Right

Post-order Traversal: Left, Right, Node

Key term

Binary Search Tree (BST): A rooted binary tree where each node's key is greater than all keys in its left subtree and less than all keys in its right subtree.

Examiner insight

Be fluent in all three traversal methods (in-order, pre-order, post-order). Questions often ask you to perform a specific traversal on a given tree or to construct a tree from a list of inputs.

Common pitfall

Violating the BST property during insertion. Every new node must be placed correctly relative to its parent and all its ancestors, not just its immediate parent.

Worked example 16 marks

  1. Draw the Binary Search Tree that results from inserting the following integers in order: 50, 25, 75, 10, 30, 60. 2. State the output of an in-order traversal of the resulting tree.
  1. 1

    Part 1 (Drawing the tree):

  2. 2

    Insert 50: 50 becomes the root.

  3. 3

    Insert 25: 25 < 50, so it becomes the left child of 50.

  4. 4

    Insert 75: 75 > 50, so it becomes the right child of 50.

  5. 5

    Insert 10: 10 < 50 -> left. 10 < 25 -> left. 10 becomes the left child of 25.

  6. 6

    Insert 30: 30 < 50 -> left. 30 > 25 -> right. 30 becomes the right child of 25.

  7. 7

    Insert 60: 60 > 50 -> right. 60 < 75 -> left. 60 becomes the left child of 75.

  8. 8

    The final tree has 50 at the root, with left child 25 and right child 75. 25 has children 10 and 30. 75 has left child 60.

  9. 9

    Part 2 (In-order traversal - Left, Node, Right):

  10. 10

    Traverse left subtree of 50. In that subtree (rooted at 25), go left to 10. Print 10. Go back to 25, print 25. Go right to 30, print 30.

  11. 11

    Now back at the root, print 50.

  12. 12

    Traverse right subtree of 50. In that subtree (rooted at 75), go left to 60. Print 60. Go back to 75, print 75. No right child.

  13. 13

    Final Output: 10, 25, 30, 50, 60, 75.

Recap

  • A binary tree is a hierarchical structure where each node has at most two children.
  • A Binary Search Tree (BST) is ordered, which allows for efficient searching (O(log n) on average).
  • In a BST, left children are smaller and right children are larger than the parent node.
  • Three common traversal methods are in-order, pre-order, and post-order.
  • An in-order traversal of a BST will always produce a sorted list of its elements.

Quick check

  1. What is the name for a node in a tree that has no children?1 mark
  2. Which traversal of a Binary Search Tree results in a sorted list?1 mark

End-of-chapter exercise

Test yourself on the whole chapter. Work through these before moving on.

  1. Define the term 'Abstract Data Type' (ADT) and give one example.2 marks
  2. State the single most important pre-condition that must be met before a binary search algorithm can be used on a list.1 mark
  3. A small program needs to allow a user to enter a password, validate it against a stored password, and display either 'Access Granted' or 'Access Denied'. Draw a structure chart to represent the design of this program.5 marks
  4. Trace the execution of an insertion sort to sort the following array into ascending order. Show the state of the array after each complete pass. Array: [8, 4, 6, 2, 9]5 marks
  5. A queue is implemented using an array of size 5. Show the contents of the queue and the values of the `Front` and `Rear` pointers after the following sequence of operations. Initial state: empty. Operations: ENQUEUE(10), ENQUEUE(20), DEQUEUE, ENQUEUE(30), ENQUEUE(40).4 marks
  6. Compare the best-case and worst-case time complexity (using Big O notation) for a bubble sort and an insertion sort. Explain the conditions that lead to the best-case performance for each.4 marks
  7. Write a pseudocode algorithm for a function `InsertInOrder(MyList, NewValue)` that inserts an integer `NewValue` into its correct alphabetical position in a sorted linked list `MyList`. You can assume the list is already sorted and node structure is [Data, Pointer].7 marks
  8. For the binary search tree created by inserting the numbers 70, 30, 90, 20, 50, 80, 100 in that order, state the sequence of nodes visited for: a) a pre-order traversal, b) an in-order traversal, and c) a post-order traversal.6 marks
  9. A library's database stores 2,097,152 book records in a sorted array, indexed by ISBN. The system uses a binary search to find books. What is the maximum number of comparisons needed to find any book? Explain your reasoning in terms of time complexity.4 marks
  10. Explain the key difference between a stack and a queue. For each, describe a different, practical computing scenario where it would be the most appropriate data structure to use.4 marks

Go deeper

Practise and revise with member-only material for this chapter.

Workbook

Exam-style practice questions with full worked solutions.

Unlock with a plan

Chapter at a Glance

A single-page summary of every key idea for fast revision.

Unlock with a plan

Free notes are just the start.

Unlock every Workbook and Chapter at a Glance, and generate your own worksheets and predicted papers.

Explore plans

Related chapters

Data representation (1.1)Communication and Internet technologiesHardwareProcessor fundamentalsSystem software (1.5)Security, privacy and data integrity