Ch 1 · 19 Computational Thinking and Problem-solving · AS & A Level Computer Science 9618
Topic 1 of 2 in Computational Thinking and Further Programming — AS & A Level Computer Science 9618 — 119 lessons.
Introduction
At A Level you must write the standard algorithms in pseudocode, not just describe them: searches, sorts, and the operations on linked lists, binary trees, stacks and queues. You also compare algorithms using Big O notation and write recursive algorithms. (Syllabus topic 19: sections 19.1–19.2.) In the code below, NullPointer is a constant set to −1.
Key ideas — 19.1 (a) Linear and binary search
A linear search checks each item in turn, from the first. It works on any list, sorted or not.
🧑🏫 Teacher's explanation
Imagine you are looking for a specific page in a book. A linear search is like starting at page 1 and flipping every single page one by one until you find it. It works even if the book is a mess of random pages, but it is very slow if the book is thick.
📖 Definitions
🔍 Worked example — Easy
A list contains the following elements: [12, 45, 7, 23, 56]. Perform a linear search for the value 23. List the indices checked (starting from 1).
🔍 Worked example — Standard
A sorted array A contains [10, 20, 30, 40, 50, 60, 70, 80, 90]. Use binary search to find the index of the value 70. Assume indices start at 1.
🔍 Worked example — Exam-style
A binary search is performed on a sorted array of 1,000,000 items. What is the maximum number of comparisons required to find an item or determine it is not there? (Use the approximation log_2(n) + 1)
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) State one advantage of using a binary search instead of a linear search for this task. [1] (b) Calculate the maximum number of comparisons required to find a specific student ID using a binary search. Show your working. [2] [3 marks]
Key ideas — 19.1 (b) Insertion sort and bubble sort
An insertion sort builds a sorted part at the start of the list. Each item in turn is taken from the unsorted part and inserted into the correct position in the sorted part, by shifting larger items one place to the right.
🧑🏫 Teacher's explanation
Imagine you are playing a card game. To sort your hand using Insertion Sort, you pick up one card at a time from the table and slide it into the correct spot in your hand, shifting your existing cards to the right to make room. You aren't swapping two cards repeatedly; you are creating a gap for the new card.
📖 Definitions
🔍 Worked example — Easy
Trace an insertion sort on the array A = [5, 2, 8, 1] for the first two iterations (starting from the second element).
🔍 Worked example — Standard
A bubble sort is performed on the list [3, 1, 4, 2]. Show the state of the list after the first full pass (one complete pass through the list).
🔍 Worked example — Exam-style
If an algorithm has a time complexity of O(n^2), and it takes 10 seconds to sort 1,000 items, approximately how long will it take to sort 2,000 items?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 19.1 (c) Linked lists: finding an item
The list is stored in an array of records, with a start pointer and a free-list pointer.
🧑🏫 Teacher's explanation
Imagine a scavenger hunt where each clue tells you where the next clue is hidden. You don't know where the final prize is, and the clues aren't in a neat row; they are scattered around a park. To find the prize, you must start at the first clue (the Start Pointer) and follow the trail, one by one, until you either find the prize or run out of clues (reach a Null Pointer).
📖 Definitions
🔍 Worked example — Easy
Given a linked list stored in an array of records where: \nStartPointer arrow 2 \nList[2].Data arrow "Apple", List[2].Pointer arrow 5 \nList[5].Data arrow "Banana", List[5].Pointer arrow NullPointer \nFind the index of "Banana".
🔍 Worked example — Standard
A linked list is implemented in an array of records. \nStartPointer arrow 1 \nList[1].Data arrow "Red", List[1].Pointer arrow 4 \nList[4].Data arrow "Blue", List[4].Pointer arrow 2 \nList[2].Data arrow "Green", List[2].Pointer arrow NullPointer \nTrace the search for "Green".
🔍 Worked example — Exam-style
A linked list is stored in an array of records. The search for "Z" fails. What is the value of CurrentNodePtr if the last node in the list has a Pointer value of 0 and NullPointer is defined as 0?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 19.1 (c) Linked lists: inserting and deleting
Insert an item (keeping the list in order):
🧑🏫 Teacher's explanation
Imagine a linked list as a scavenger hunt where each clue tells you where to find the next one. Unlike an array, where items sit side-by-side in a fixed row, linked list items (nodes) can be scattered anywhere in memory. Each node has two parts: the actual data and a 'pointer' (the address of the next clue).
📖 Definitions
🔍 Worked example — Easy
A linked list contains the nodes: A arrow B arrow C. If we insert node X such that the list remains sorted and A < X < B, what is the new sequence of pointers?
🔍 Worked example — Standard
Consider a linked list with nodes at indices \1, 3, 5, 7\ where StartPointer = 1. If we delete the node at index 3, what is the new StartPointer and what does the node at index 1 point to?
🔍 Worked example — Exam-style
A linked list is implemented using an array of records. The array is: \nList[1].Data = 'Apple', List[1].Pointer = 3 nList[2].Data = 'Cherry', List[2].Pointer = NULL \nList[3].Data = 'Banana', List[3].Pointer = 2 nStartPointer = 1$. \nPerform $DeleteNode('Banana')$ and state the final $StartPointer$ and the contents of the list.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 19.1 (d) Binary tree operations
A binary tree is made of nodes, each with data and two pointers: left and right. In a binary search tree, every item in a node's left subtree is smaller than it, and every item in its right subtree is larger (or equal). The first node is the root; nodes with no children are leaves.
🧑🏫 Teacher's explanation
Imagine you are looking for a specific page in a massive, organized encyclopedia. Instead of flipping every single page from the start (which is slow), you open to the middle. If your page number is lower, you ignore the entire second half of the book and repeat the process with the first half. This 'divide and conquer' approach is exactly how a Binary Search Tree works.
📖 Definitions
🔍 Worked example — Easy
A Binary Search Tree contains the following values: 50, 30, 70, 20, 40. Trace the path taken to find the value 40.
🔍 Worked example — Standard
Insert the following sequence of integers into an empty Binary Search Tree: 15, 10, 20, 5, 12. Draw/describe the final structure.
🔍 Worked example — Exam-style
Calculate the maximum number of comparisons needed to find an item in a perfectly balanced binary tree containing n = 15 nodes.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 19.1 (e) Stack and queue operations
🧑🏫 Teacher's explanation
Imagine a stack of cafeteria trays. You can only add a new tray to the top, and when you need one, you take it from the top. This is 'Last-In, First-Out' (LIFO). You can't grab the bottom tray without removing everything above it first.
📖 Definitions
🔍 Worked example — Easy
A stack has a MaxSize of 5. Perform the following operations: Push("A"), Push("B"), Pop(), Push("C"). What is the value of TopPointer and the contents of the stack?
🔍 Worked example — Standard
A circular queue has MaxSize = 3. Perform: Enqueue("X"), Enqueue("Y"), Enqueue("Z"), Dequeue(), Enqueue("W"). What is the value of FrontPointer and RearPointer?
🔍 Worked example — Exam-style
Calculate the number of operations required to empty a stack containing n elements if each Pop operation takes 1 unit of time.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) State the value of TopPointer after three items have been successfully pushed into the stack. [1] (b) Write pseudocode for a function 'IsFull()' that returns TRUE if the stack is full and FALSE otherwise. [2] [3 marks]
Key ideas — 19.1 (f) Graphs, dictionaries, and ADTs built from other ADTs
A graph is an ADT made of nodes (vertices) and edges connecting them; edges may be directed or undirected and weighted or unweighted. Unlike a tree, a graph can have cycles and has no root. Justify: use a graph when items have many-to-many connections: road maps, computer networks, social networks (people and friendships), web pages and links. (You do not write code for graphs.)
🧑🏫 Teacher's explanation
Think of an Abstract Data Type (ADT) as a 'blueprint' or a 'contract'. It tells you *what* the data structure does (e.g., a Stack allows you to push and pop), but it doesn't tell you *how* it is built. You can build a house using bricks (arrays) or wood (linked lists); the house still functions as a home regardless of the material.
📖 Definitions
🔍 Worked example — Easy
A dictionary is implemented using an array of records. Each record contains a key (STRING) and a value (INTEGER). If the array has 5 slots and we insert (\"Apple\", 10) and (\"Banana\", 20), how many records are currently occupied?
🔍 Worked example — Standard
A graph is used to represent a computer network. If there are 5 nodes and each node is connected to exactly 3 other nodes via undirected edges, how many edges are in the graph?
🔍 Worked example — Exam-style
A queue is implemented using two stacks: S_1 (for enqueuing) and S_2 (for dequeuing). If we perform the following operations: 1. Enqueue(A), 2. Enqueue(B), 3. Dequeue(), 4. Enqueue(C), 5. Dequeue(). What is the final state of S_2?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Identify one way this Dictionary could be implemented using another ADT. [1] (b) Explain one advantage of using a Hash Table to implement this Dictionary instead of a Binary Tree. [2] [3 marks]
Key ideas — 19.1 (g) Comparing algorithms: Big O notation
Algorithms that do the same task can be compared by the time they take and the memory they use, as the number of items n grows. Big O notation describes the worst-case growth rate, ignoring constants.
🧑🏫 Teacher's explanation
Imagine you are organizing a massive library. If you want to find a specific book, one way is to check every single book one by one from the front door. If the library doubles in size, it takes you twice as long. This is 'linear' growth. Another way is to use a system where you jump to the middle, see if the book is in the left or right half, and repeat. Even if the library grows massive, you only need a few more jumps to find it. This is 'logarithmic' growth.
📖 Definitions
🔍 Worked example — Easy
An algorithm performs a single operation regardless of the input size n. What is its Big O time complexity?
🔍 Worked example — Standard
A bubble sort uses two nested loops. The outer loop runs n times, and for every iteration of the outer loop, the inner loop runs n times. Determine the time complexity.
🔍 Worked example — Exam-style
A recursive function calls itself twice for every single call (e.g., T(n) = 2T(n-1) + 1). If the depth of the recursion is n, what is the worst-case time complexity?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) State the Big O time complexity for the worst-case scenario of a binary search. [1] (b) Explain why a binary search is more efficient than a linear search for large values of n. [2] [3 marks]
Key ideas — 19.2 (a) Recursion
A recursive subroutine is one that is defined in terms of itself: it calls itself.
🧑🏫 Teacher's explanation
Imagine you are standing in a long line of people and you want to know what position you are in. Instead of counting everyone yourself, you tap the person in front of you and ask, "What position are you in?" That person taps the person in front of them and asks the same thing. This continues until the person at the very front is asked. They know they are position 1 (the base case) and tell the person behind them. That person adds 1 and tells the person behind them, and so on, until the answer reaches you.
📖 Definitions
🔍 Worked example — Easy
Trace the execution of the following pseudocode for Sum(3):
🔍 Worked example — Standard
A recursive function is defined as:
🔍 Worked example — Exam-style
A recursive algorithm is used to traverse a binary tree. If the tree has a height of h, and each recursive call adds a new frame to the stack, what is the maximum number of stack frames that will be active at once during the descent to the deepest leaf?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Write pseudocode for this function. (b) Trace the execution of the function for N = 3. [4 marks]
Key ideas — 19.2 (b) When recursion is beneficial
🧑🏫 Teacher's explanation
Imagine you are standing in a long line of people, and you want to find a specific person. Instead of walking down the line one by one (iteration), you split the line in half. You ask the person in the middle, "Is the person I want to the left or right of you?" Based on the answer, you ignore half the line and repeat the process with the remaining half. This "splitting" behavior is the essence of recursion.
📖 Definitions
🔍 Worked example — Easy
Trace the following recursive function for f(3) where: f(n) = IF n == 0 THEN 1 ELSE n × f(n-1)
🔍 Worked example — Standard
A recursive algorithm is used to traverse a binary tree. If the tree has a depth of 10, how many stack frames are added to the call stack during the deepest path of traversal?
🔍 Worked example — Exam-style
Compare the space complexity of an iterative factorial algorithm (using one integer variable) and a recursive factorial algorithm (where n is the input) using Big O notation.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) State one advantage of using a recursive approach for tree traversal. [1] (b) State one disadvantage of using a recursive approach compared to an iterative approach. [1] [2 marks]
Key ideas — 19.2 (c) How a compiler handles recursion: stacks and unwinding
The compiler must generate code that uses a stack (the call stack). Each time the subroutine is called, a stack frame is pushed holding:
🧑🏫 Teacher's explanation
Imagine you are following a recipe for a cake, but halfway through, the recipe says "To make the frosting, follow the recipe for buttercream." You stop what you are doing, grab a new piece of paper, and start writing down the steps for buttercream. You must remember exactly where you were in the cake recipe so you can come back to it. This "sticky note" containing your current progress is like a stack frame.
📖 Definitions
🔍 Worked example — Easy
Trace the stack for the recursive function FACT(n) where FACT(n) returns n × FACT(n-1) and the base case is n=1. Trace the stack for FACT(3).
🔍 Worked example — Standard
A recursive function uses a stack frame that stores 4 bytes for the return address, 8 bytes for a parameter x, and 8 bytes for a local variable y. If the recursion depth reaches 4 calls, what is the total memory used by the stack frames (excluding the initial program overhead)?
🔍 Worked example — Exam-style
Consider the following pseudocode:
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) State the purpose of the 'base case' in this recursive function. [1] (b) Describe what the compiler must store in a stack frame each time the function is called. [3] [4 marks]
Worked example
Show the comparisons made by a binary search for 47 in 3, 8, 12, 19, 25, 31, 40, 47, 52, 66 (indexes 1–10).
🔍 Worked example — Easy
A sorted array contains the values: [5, 12, 18, 22, 35, 40, 55]. Using binary search, find the index of the value 35. (Assume 1-based indexing).
🔍 Worked example — Standard
Compare the maximum number of comparisons required for a linear search vs a binary search for an array of size n = 1024.
🔍 Worked example — Exam-style
Trace the binary search for the target value 47 in the array [3, 8, 12, 19, 25, 31, 40, 47, 52, 66] (indices 1-10).
⚠️ Common errors
Common mistakes
Practice
Answers: (1) The data must be sorted, and it must be possible to access any item directly (e.g. an array). (2) 11 (2¹¹ = 2 048); a linear search may need 2 000. (3) Each item is compared with the item before it; if it is already in place, the inner loop stops immediately, so only about n comparisons are needed. (4) Root 40; left child 25 (children 10 and 30); right child 60 (children 50 and 70). (5) Follow the pointers from the start, keeping the previous node, until the item is found; if it is the first node, set the start pointer to its pointer, otherwise set the previous node's pointer to its pointer; then add the node to the free list. (6) (a) O(n); (b) O(log n); (c) O(n²). (7) A base case; a general case that calls itself; each call moves towards the base case. (8) Each call pushes a stack frame with the return address, parameters and local variables; when the base case is reached, frames are popped in turn (unwinding), returning each result to the caller.