Cambridge AS & A Level9608

Computational thinking and problem-solving

Computer Science 9608 Chapter Notes

What this chapter covers

Computational thinking and problem-solving
ShareWhatsAppPost
Computational thinking and problem-solving 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 Computational thinking and problem-solving notes as text: skim, search, and jump between subtopics.

~18 min read

In this chapter

  1. 1The Core of Computational Thinking
  2. 2Searching: Linear vs. Binary Search
  3. 3Sorting: Bubble and Insertion Sort
  4. 4ADTs: Stacks and Queues
  5. 5ADTs: Linked Lists
  6. 6ADTs: Binary Search Trees
  7. 7ADTs: Hash Tables

1. The Core of Computational Thinking

Computational thinking is not about thinking like a computer, but rather a structured way for humans to solve complex problems. It's a process that breaks down large problems into smaller, more manageable pieces. This approach involves four key techniques, often called the 'four pillars' of computational thinking.

Key term

Computational Thinking: A problem-solving process that involves formulating a problem and its solution in a way that a computer (human or machine) can effectively carry out.

Examiner insight

Examiners look for students who can not just name the four pillars, but also apply them to a given scenario, explaining how each pillar contributes to finding a solution.

Common pitfall

Confusing computational thinking with programming. Computational thinking is the problem-solving process; programming is the tool used to implement the solution.

Fun fact

The term 'computational thinking' was popularised by Jeannette Wing of Carnegie Mellon University in 2006, but the ideas behind it have been a core part of computer science since its inception.

Worked example 14 marks

Apply the four pillars of computational thinking to the problem of organising a surprise birthday party for a friend.

  1. 1
    1. Decomposition: Break the problem 'organise a party' into smaller tasks: create a guest list, send invitations, choose a venue, plan the food and drinks, buy a cake, arrange decorations, and plan activities.
  2. 2
    1. Pattern Recognition: Identify patterns or similar tasks. For example, 'buying a cake' and 'buying decorations' both involve purchasing items. 'Sending invitations' and 'tracking RSVPs' are related communication tasks. Grouping these can make planning more efficient.
  3. 3
    1. Abstraction: Focus on the essential details for each task, ignoring irrelevant ones. For the 'guest list' task, essential details are names and contact information. You can ignore details like what each person wore last time you saw them. The overall model is a checklist of key tasks, not a minute-by-minute script of the party.
  4. 4
    1. Algorithm Design: Create a step-by-step plan. For example: Step 1: Finalise guest list by Tuesday. Step 2: Send out all invitations by Wednesday. Step 3: Based on expected numbers, book the venue by Friday. Step 4: Order the cake one week before the party. This ordered sequence of steps is an algorithm for organising the party.

Recap

  • Computational thinking is a method for solving complex problems.
  • Decomposition is breaking a problem down into smaller, simpler parts.
  • Pattern recognition involves finding similarities or trends within problems.
  • Abstraction is the process of ignoring irrelevant details to focus on what is important.
  • Algorithm design is creating a step-by-step solution to the problem.

Quick check

  1. Name the four pillars of computational thinking.2 marks
  2. Which pillar involves focusing only on essential details?1 mark

2. Searching: Linear vs. Binary Search

Searching for data is a fundamental task. The two main algorithms you need to know are linear search and binary search. A linear search is simple: it checks each item in a list, one by one, from the beginning until the target is found or the end of the list is reached. A binary search is much more efficient but has a crucial requirement: the data must be sorted first. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, you narrow the interval to the lower half. Otherwise, you narrow it to the upper half. You continue this until the value is found or the interval is empty.

Worst-case Time Complexity (Linear Search): O(n)

Worst-case Time Complexity (Binary Search): O(log n)

Key term

Binary Search: An efficient search algorithm that finds an item in a sorted array by repeatedly dividing the search interval in half.

Examiner insight

Examiners award marks for correctly updating the LowerBound and UpperBound pointers within the search loop. A common mistake is setting `LowerBound = Midpoint` instead of `Midpoint + 1`, which can lead to an infinite loop.

Common pitfall

Attempting to use a binary search on an unsorted list. This will produce incorrect results or fail to find an item that is present.

Worked example 13 marks

An array `Data` contains the sorted integers: `[4, 7, 11, 15, 19, 23, 28, 31, 40, 45]`. The array indices are 0 to 9. Trace a binary search to find the value `19`.

  1. 1
    1. Initial State: LowerBound = 0, UpperBound = 9. Target = 19.
  2. 2
    1. Iteration 1: Midpoint = (0 + 9) DIV 2 = 4. Value at `Data[4]` is 19. The target is found at index 4.
  3. 3
    1. Conclusion: The value 19 is found at index 4. The search terminates.

Worked example 26 marks

Write a pseudocode algorithm for a binary search function that takes a sorted array `A`, its size `N`, and a `Target` value. It should return the index of the target if found, or -1 if not found.

  1. 1

    FUNCTION BinarySearch(A, N, Target) RETURNS INTEGER

  2. 2

    LowerBound = 0

  3. 3

    UpperBound = N - 1

  4. 4

    Found = FALSE

  5. 5

    Index = -1

  6. 6

    WHILE Found = FALSE AND LowerBound <= UpperBound

  7. 7

    Midpoint = LowerBound + (UpperBound - LowerBound) DIV 2

  8. 8

    IF A[Midpoint] = Target THEN

  9. 9

    Found = TRUE

  10. 10

    Index = Midpoint

  11. 11

    ELSE IF A[Midpoint] < Target THEN

  12. 12

    LowerBound = Midpoint + 1

  13. 13

    ELSE

  14. 14

    UpperBound = Midpoint - 1

  15. 15

    ENDIF

  16. 16

    ENDWHILE

  17. 17

    RETURN Index

  18. 18

    ENDFUNCTION

Recap

  • A linear search checks every element sequentially and can be used on any list.
  • A binary search requires the list to be sorted before searching.
  • Binary search works by repeatedly halving the search interval.
  • The time complexity of a linear search is O(n), making it inefficient for large lists.
  • The time complexity of a binary search is O(log n), making it very efficient for large lists.

Quick check

  1. What is the single most important condition for a binary search to work correctly?1 mark
  2. If a sorted list has 1024 items, roughly how many comparisons will a binary search take in the worst case?1 mark

3. Sorting: Bubble and Insertion Sort

Sorting arranges items in a list into a specific order (e.g., ascending or descending). Bubble sort and insertion sort are two simple, but relatively inefficient, sorting algorithms. Bubble Sort: This method repeatedly steps through the list, compares each pair of adjacent items, and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, which means the list is sorted. The 'heavier' items 'bubble' up to the end of the list. Insertion Sort: This algorithm builds the final sorted list one item at a time. It iterates through the input elements, taking one unsorted element and 'inserting' it into its correct position within the already sorted part of the list.

Worst-case Time Complexity (Bubble Sort): O(n^2)

Worst-case Time Complexity (Insertion Sort): O(n^2)

Key term

Bubble Sort: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

Examiner insight

For sorting algorithm questions, marks are awarded for correct loop structures and the specific logic of comparison and swapping. Tracing the state of the array after each pass is a common exam question.

Common pitfall

An 'off-by-one' error in the loop boundaries for bubble sort, often causing the last element to be missed in comparisons.

Worked example 14 marks

Show the passes of a bubble sort on the array `[6, 2, 8, 4, 1]`. Show the state of the array after each pass.

  1. 1

    Initial Array: `[6, 2, 8, 4, 1]`

  2. 2

    Pass 1: [2, 6, 8, 4, 1] -> [2, 6, 8, 4, 1] -> [2, 6, 4, 8, 1] -> [2, 6, 4, 1, 8]. Result: `[2, 6, 4, 1, 8]`

  3. 3

    Pass 2: [2, 6, 4, 1, 8] -> [2, 4, 6, 1, 8] -> [2, 4, 1, 6, 8]. Result: `[2, 4, 1, 6, 8]`

  4. 4

    Pass 3: [2, 4, 1, 6, 8] -> [2, 1, 4, 6, 8]. Result: `[2, 1, 4, 6, 8]`

  5. 5

    Pass 4: [1, 2, 4, 6, 8]. Result: `[1, 2, 4, 6, 8]`

  6. 6

    Pass 5: No swaps occur, the algorithm could terminate early if optimized. The list is now sorted.

Worked example 25 marks

Write a pseudocode algorithm to implement an insertion sort.

  1. 1

    PROCEDURE InsertionSort(A, N)

  2. 2

    FOR i FROM 1 TO N - 1

  3. 3

    CurrentValue = A[i]

  4. 4

    Position = i

  5. 5

    WHILE Position > 0 AND A[Position - 1] > CurrentValue

  6. 6

    A[Position] = A[Position - 1]

  7. 7

    Position = Position - 1

  8. 8

    ENDWHILE

  9. 9

    A[Position] = CurrentValue

  10. 10

    ENDFOR

  11. 11

    ENDPROCEDURE

Recap

  • Bubble sort repeatedly compares and swaps adjacent elements.
  • Insertion sort builds a sorted sublist by inserting elements one by one.
  • Both bubble sort and insertion sort have a worst-case time complexity of O(n^2).
  • Insertion sort is generally more efficient than bubble sort in practice.
  • The performance of these sorts can depend on the initial order of the data.

Quick check

  1. Which sort involves comparing and swapping only adjacent elements?1 mark
  2. What is the time complexity of both bubble sort and insertion sort in the worst case?1 mark

4. ADTs: Stacks and Queues

An Abstract Data Type (ADT) is a high-level model of a data structure. It defines a collection of data and the set of operations on that data, without specifying how the data structure is implemented. Stacks and Queues are two fundamental linear ADTs. Stack: A stack operates on a Last-In, First-Out (LIFO) principle. The last element added to the stack is the first one to be removed. Think of a stack of plates. Key operations are `PUSH` (add an item to the top) and `POP` (remove the top item). Queue: A queue operates on a First-In, First-Out (FIFO) principle. The first element added to the queue is the first one to be removed. Think of a queue of people waiting for a bus. Key operations are `ENQUEUE` (add an item to the back) and `DEQUEUE` (remove the item from the front).

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 implementation.

Examiner insight

Marks are often awarded for accurately tracing the state of a stack or queue through a series of operations. Be precise about what is added, what is removed, and the resulting state.

Common pitfall

Confusing the operations for stacks and queues, for example, using 'POP' when describing a queue or 'DEQUEUE' for a stack.

Fun fact

The 'Undo' feature in most text editors is implemented using a stack. Each change is pushed onto the stack, and pressing Ctrl+Z pops the last change off and reverses it.

Worked example 14 marks

A stack, initially empty, is used to process the following sequence of operations: PUSH(10), PUSH(20), POP, PUSH(30), PUSH(40), POP. Show the state of the stack after each operation and state the final value at the top of the stack.

  1. 1
    1. Initial: `[]` (empty)
  2. 2
    1. PUSH(10): `[10]`
  3. 3
    1. PUSH(20): `[10, 20]`
  4. 4
    1. POP: Returns 20. Stack is now `[10]`
  5. 5
    1. PUSH(30): `[10, 30]`
  6. 6
    1. PUSH(40): `[10, 30, 40]`
  7. 7
    1. POP: Returns 40. Stack is now `[10, 30]`
  8. 8

    Conclusion: The final state of the stack is `[10, 30]`. The value at the top is 30.

Worked example 24 marks

A queue is used for the same sequence of operations (using ENQUEUE for PUSH and DEQUEUE for POP): ENQUEUE(10), ENQUEUE(20), DEQUEUE, ENQUEUE(30), ENQUEUE(40), DEQUEUE. Show the state of the queue after each operation.

  1. 1
    1. Initial: `[]` (empty)
  2. 2
    1. ENQUEUE(10): `[10]`
  3. 3
    1. ENQUEUE(20): `[10, 20]`
  4. 4
    1. DEQUEUE: Returns 10. Queue is now `[20]`
  5. 5
    1. ENQUEUE(30): `[20, 30]`
  6. 6
    1. ENQUEUE(40): `[20, 30, 40]`
  7. 7
    1. DEQUEUE: Returns 20. Queue is now `[30, 40]`
  8. 8

    Conclusion: The final state of the queue is `[30, 40]`.

Recap

  • An ADT defines 'what' a data structure does, not 'how' it does it.
  • A stack is a LIFO (Last-In, First-Out) data structure.
  • Key stack operations are PUSH (add) and POP (remove).
  • A queue is a FIFO (First-In, First-Out) data structure.
  • Key queue operations are ENQUEUE (add) and DEQUEUE (remove).

Quick check

  1. Which principle does a stack follow: LIFO or FIFO?1 mark
  2. What is the name of the operation to add an element to a queue?1 mark

5. ADTs: Linked Lists

A linked list is a linear ADT where elements are not stored in contiguous memory locations like an array. 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 list is accessed via a 'start pointer' or 'head pointer' which points to the first node. The last node in the list has a pointer that points to 'NULL', indicating the end of the list. This structure allows for efficient insertion and deletion of elements without needing to shift other elements, which is a major advantage over arrays.

Key term

Linked List: A linear data structure where elements are not stored at contiguous memory locations but are linked using pointers.

Examiner insight

Examiners look for careful handling of pointers. Diagrams can be very helpful in visualising the changes. When writing pseudocode, clearly distinguish between a pointer and the data it points to (e.g., `CurrentPointer` vs `CurrentPointer.Data`).

Common pitfall

When deleting a node, forgetting to update the pointer of the *previous* node. This breaks the chain and makes the rest of the list inaccessible.

Worked example 15 marks

Write a pseudocode algorithm to find an item in a singly linked list. The function should take the `StartPointer` and the `ItemToFind` as input, and return TRUE if found, FALSE otherwise.

  1. 1

    // Assume node structure is (Data, NextNodePointer)

  2. 2

    FUNCTION FindItem(StartPointer, ItemToFind) RETURNS BOOLEAN

  3. 3

    CurrentPointer = StartPointer

  4. 4

    WHILE CurrentPointer <> NULL

  5. 5

    IF CurrentPointer.Data = ItemToFind THEN

  6. 6

    RETURN TRUE

  7. 7

    ENDIF

  8. 8

    CurrentPointer = CurrentPointer.NextNodePointer

  9. 9

    ENDWHILE

  10. 10

    RETURN FALSE

  11. 11

    ENDFUNCTION

Worked example 24 marks

Describe the steps required to delete a node containing the value `X` from a singly linked list. Consider the cases where the node is the first node or in the middle of the list.

  1. 1
    1. Search for the node: Traverse the list from the start, keeping track of the current node and the previous node.
  2. 2
    1. Case 1: Node is the first node: If the node to be deleted is the first one (`StartPointer.Data = X`), update the `StartPointer` to point to the second node (`StartPointer = StartPointer.NextNodePointer`).
  3. 3
    1. Case 2: Node is in the middle or end: If the node is found at `CurrentPointer`, update the `NextNodePointer` of the `PreviousPointer` to bypass the current node. This is done by setting `PreviousPointer.NextNodePointer = CurrentPointer.NextNodePointer`.
  4. 4
    1. Deallocate memory: The memory occupied by the deleted node should be returned to the system (or a free list) to be reused.

Recap

  • A linked list is a dynamic data structure made of nodes.
  • Each node contains data and a pointer to the next node.
  • The `StartPointer` (or head) points to the first node in the list.
  • The last node's pointer is `NULL` to signify the end.
  • Insertion and deletion are efficient but random access is slow (O(n)).

Quick check

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

6. ADTs: Binary Search 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 top-most 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 subtree are less than the node's value, and all values in its right subtree are greater than the node's value. This property makes searching for data highly efficient, similar to a binary search in an array.

Average Time Complexity (BST Search/Insert/Delete): O(log n)

Key term

Binary Search Tree (BST): A tree data structure where each node's left child value is less than the node's value, and the right child's value is greater.

Examiner insight

Examiners often test the ability to construct a BST from a given sequence of data. It is crucial to follow the insertion rules strictly for every single number to get the correct final structure.

Common pitfall

Creating an unbalanced tree by inserting data that is already sorted. This degenerates the tree into a linked list, making its performance O(n) instead of O(log n).

Worked example 14 marks

Draw the binary search tree that results from inserting the following integer keys in order: `50, 25, 75, 15, 30, 60, 85`.

  1. 1
    1. Insert 50: 50 becomes the root.
  2. 2
    1. Insert 25: 25 < 50, so it becomes the left child of 50.
  3. 3
    1. Insert 75: 75 > 50, so it becomes the right child of 50.
  4. 4
    1. Insert 15: 15 < 50 (go left), 15 < 25 (go left). It becomes the left child of 25.
  5. 5
    1. Insert 30: 30 < 50 (go left), 30 > 25 (go right). It becomes the right child of 25.
  6. 6
    1. Insert 60: 60 > 50 (go right), 60 < 75 (go left). It becomes the left child of 75.
  7. 7
    1. Insert 85: 85 > 50 (go right), 85 > 75 (go right). It becomes the right child of 75.
  8. 8

    The final tree will have 50 at the root, with left subtree rooted at 25 and right subtree rooted at 75.

Worked example 25 marks

Write a recursive pseudocode algorithm to find a value in a binary search tree. Assume nodes have properties `Data`, `LeftPointer`, `RightPointer`.

  1. 1

    FUNCTION FindInBST(CurrentNode, ValueToFind) RETURNS BOOLEAN

  2. 2

    IF CurrentNode = NULL THEN

  3. 3

    RETURN FALSE // Value not in tree

  4. 4

    ENDIF

  5. 5

    IF CurrentNode.Data = ValueToFind THEN

  6. 6

    RETURN TRUE // Value found

  7. 7

    ELSE IF ValueToFind < CurrentNode.Data THEN

  8. 8

    RETURN FindInBST(CurrentNode.LeftPointer, ValueToFind)

  9. 9

    ELSE

  10. 10

    RETURN FindInBST(CurrentNode.RightPointer, ValueToFind)

  11. 11

    ENDIF

  12. 12

    ENDFUNCTION

Recap

  • A binary search tree (BST) is a hierarchical data structure for efficient searching.
  • The BST property is: left child < parent < right child.
  • The top node of the tree is called the root.
  • Nodes with no children are called leaves.
  • Searching a balanced BST is very fast, with O(log n) time complexity.

Quick check

  1. In a BST, if the current node's value is 100, would you search for the value 88 in the left or right subtree?1 mark
  2. What is the maximum number of children a node in a binary tree can have?1 mark

7. ADTs: Hash Tables

A hash table is a powerful data structure that maps keys to values for highly efficient lookup. It's the structure that commonly implements dictionaries or associative arrays. The process works by using a 'hash function' to compute an index, or 'hash code', from a key. This index is then used to locate a 'bucket' or 'slot' in an array where the corresponding value is stored. For example, to store a phone number (value) for a person's name (key), the hash function would take the name and calculate an array index. Because the hash function can compute the index directly, the average time to find, insert, or delete an item is O(1), or constant time, which is incredibly fast. A 'collision' occurs when the hash function generates the same index for two different keys. There are various techniques to handle collisions, such as storing multiple items in the same bucket (e.g., in a linked list).

Average Time Complexity (Hash Table Search/Insert): O(1)

Key term

Hash Function: A function that converts an input key into an index for a hash table, determining where the corresponding value should be stored.

Examiner insight

Students should be able to explain the concept of hashing and apply a given hash function to a key to find an index. Understanding that a collision is a possibility and being able to describe a simple resolution method is also key.

Common pitfall

Assuming that hash table lookups are always O(1). While this is the average case, a poorly chosen hash function or many collisions can degrade performance to O(n) in the worst case.

Fun fact

Hash tables are fundamental to internet security. Cryptographic hash functions are used to securely store passwords; instead of storing your actual password, a website stores its hash. When you log in, it hashes your input and compares it to the stored hash.

Worked example 13 marks

A hash table of size 11 (indices 0 to 10) is used to store string keys. The hash function sums the ASCII values of the characters and then applies MOD 11. For example, `H("Tim") = (ASCII('T') + ASCII('i') + ASCII('m')) MOD 11`. Given ASCII values T=84, i=105, m=109, calculate the hash for 'Tim'.

  1. 1
    1. Sum the ASCII values: 84 + 105 + 109 = 298.
  2. 2
    1. Apply the MOD operator: 298 MOD 11.
  3. 3
    1. Perform the division: 298 / 11 = 27 with a remainder.
  4. 4
    1. The remainder is the hash value: 298 = 11 * 27 + 1. The remainder is 1.
  5. 5
    1. The key 'Tim' would be placed at index 1 in the hash table.

Worked example 23 marks

Describe a simple method to handle a collision when inserting a new key-value pair into a hash table.

  1. 1
    1. A common method is called 'linear probing'.
  2. 2
    1. When a collision occurs (the calculated index is already occupied by another key), the algorithm checks the next available slot in the array.
  3. 3
    1. It moves sequentially (linearly) through the array from the point of collision, looking for the first empty bucket.
  4. 4
    1. The new key-value pair is then inserted into this empty bucket.
  5. 5
    1. The search for an empty slot may 'wrap around' from the end of the array to the beginning if necessary.

Recap

  • Hash tables use a hash function to map keys to array indices.
  • This allows for extremely fast, constant time O(1) average lookups.
  • A collision is when two different keys produce the same hash index.
  • Collisions must be handled using techniques like linear probing or chaining.
  • Hash tables are used to implement dictionaries and associative arrays.

Quick check

  1. What is the term for when two different keys generate the same hash index?1 mark
  2. What is the primary role of a hash function?1 mark

End-of-chapter exercise

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

  1. Compare and contrast a stack and a queue. Describe one real-world computing application for each.4 marks
  2. A sorted array contains 2000 elements. A computer needs to find a specific value. Explain, with reference to time complexity, why a binary search would be a better choice than a linear search.4 marks
  3. Write a pseudocode procedure to implement a bubble sort algorithm for an array of integers `MyList` of size `N`.6 marks
  4. Describe the steps to insert a new node into a sorted singly linked list, ensuring the list remains sorted after the insertion. You may use a diagram to support your answer.5 marks
  5. Given the list of numbers: `[30, 45, 12, 50, 22, 80, 18]`. Show the state of the list after the first three outer loop iterations of an insertion sort.3 marks
  6. Explain what a hash table collision is and describe, with the aid of an example, the method of linear probing to resolve it.4 marks
  7. Draw the binary search tree that is formed when the following values are inserted in the given order: `100, 50, 150, 25, 75, 125, 175, 60`.4 marks
  8. An algorithm's performance can be measured by time taken and memory used. Explain why two different sorting algorithms might perform differently on the same list of 10,000 numbers.3 marks
  9. Write a pseudocode algorithm to delete an item from a queue implemented using an array and pointers for the front and rear of the queue. You must handle the case of an empty queue.6 marks
  10. Explain the concept of abstraction in computational thinking. Provide an example of how abstraction is used when modelling a real-world system, such as a car in a driving simulator.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