19. Computational Thinking and Problem-Solving

Browse all infographics →

Dotted terms are defined in the glossary.

• Binary search (iterative)

  Only works on sorted data: halve the search range each time by comparing with the middle element.

  ASA2PseudocodeSearching 9618 §19.1
  Run

• Binary search (recursive)

  Two base cases — empty range (not found) and middle matches (found) — and two recursive calls.

  A2PseudocodeSearching 9618 §19.1
  Run

• Linear vs binary search — count the comparisons

  Big O in practice: 1000 sorted items, linear search is O(n) and binary search O(log n).

  A2PseudocodeSearching 9618 §19.1
  Run

• Bubble sort with a Swapped flag

  Stop early when a whole pass makes no swaps — the efficient version examiners like.

  ASA2PseudocodeSorting 9618 §9.2, §19.1
  Run

• Insertion sort

  Take each value in turn and slide it left into the sorted part of the array.

  ASA2PseudocodeSorting 9618 §19.1
  Run

• Stack — push, pop, overflow & underflow

  LIFO with an array and a Top pointer. Watch what happens on the 4th pop.

  ASA2PseudocodeStacks, queues, lists & trees 9618 §10.4, §19.1
  Run

• Linear queue — enqueue & dequeue

  FIFO with Front and Rear pointers. Notice the space at the front is never reused.

  ASA2PseudocodeStacks, queues, lists & trees 9618 §10.4, §19.1
  Run

• Circular queue

  Rear MOD Size + 1 wraps the pointer back to slot 1 so freed space is reused.

  A2PseudocodeStacks, queues, lists & trees 9618 §19.1
  Run

• Linked list in arrays with a free list

  Insert at the front, delete by value, traverse — using Data/Pointer records, StartPointer and FreePointer.

  ASA2PseudocodeStacks, queues, lists & trees 9618 §10.4, §19.1
  Run

• Binary search tree — insert, search & three traversals

  Nodes in an array with LeftPointer/RightPointer; in-order traversal outputs the values sorted.

  A2PseudocodeStacks, queues, lists & trees 9618 §19.1
  Run

• Hash table with linear probing

  Key MOD TableSize gives the slot; on a collision, step to the next free slot.

  A2PseudocodeStacks, queues, lists & trees 9618 §19.1
  Run

• Dictionary — key → value pairs

  A dictionary ADT built from an array of records: Add updates an existing key or appends a new one; Lookup returns the value.

  A2PseudocodeStacks, queues, lists & trees 9618 §19.1
  Run

• Using a stack — balanced brackets

  Push every ( and pop on every ); the expression is balanced if the stack ends empty and never underflows.

  A2PseudocodeStacks, queues, lists & trees 9618 §19.1
  Run

• Evaluate Reverse Polish Notation with a stack

  Operands are pushed; an operator pops two, applies itself and pushes the result — how a compiler evaluates RPN.

  A2PseudocodeStacks, queues, lists & trees 9618 §16.3
  Run

• Factorial — the first recursive function

  Base case N <= 1 returns 1; the general case calls itself with N - 1.

  A2PseudocodeRecursion 9618 §19.2
  Run

• Winding and unwinding — watch the call stack

  Output before the recursive call happens on the way down; output after it happens on the way back up.

  A2PseudocodeRecursion 9618 §19.2
  Run

• Fibonacci numbers

  Two base cases and two recursive calls — simple to write, expensive to run.

  A2PseudocodeRecursion 9618 §19.2
  Run

• Recursive power & digit sum

  Two more classic recursive definitions: x^n = x * x^(n-1), and digit sum = last digit + digit sum of the rest.

  A2PseudocodeRecursion 9618 §19.2
  Run

• Greatest common divisor (Euclid)

  GCD(A, B) = GCD(B, A MOD B) until B is 0.

  A2PseudocodeRecursion 9618 §19.2
  Run

• Tower of Hanoi

  Move N-1 discs out of the way, move the biggest, move the N-1 back. 2^N - 1 moves.

  A2PseudocodeRecursion 9618 §19.2
  Run

• Recursion vs iteration

  The same sum written both ways — same answer, different use of the stack.

  A2PseudocodeRecursion 9618 §19.2
  Run

• Reverse a string recursively

  Reverse of S = reverse of everything after the first character, followed by the first character.

  A2PseudocodeRecursion 9618 §19.2
  Run

• A Stack class

  The stack ADT wrapped in a class: the array and Top are PRIVATE, so only Push/Pop can touch them.

  A2PseudocodeObject-oriented programming §10.1 · 9618 §19.1
  Run

• Frequency count with a list and a dictionary

  Count dice rolls two ways: a list indexed by value, and a dictionary (the ADT the exam calls a dictionary).

  ASA2PythonArrays §3 ↔ Python
  Run

• Binary search — iterative and recursive

  Halve the search space each time; the list must be sorted. Both versions, with the number of comparisons.

  ASA2PythonSearching §7 ↔ Python
  Run

• Insertion sort

  Take each item and slide it left into the sorted part. Compare with sorted() and .sort() at the end.

  ASA2PythonSorting §7 ↔ Python
  Run

• Stack and queue with a list

  append/pop give a stack; append/pop(0) a queue. Watch the order things come out.

  ASA2PythonStacks, queues, lists & trees §10 ADT ↔ Python
  Run

• Stack as a class with an array and a pointer

  The exam implementation: fixed-size list, top pointer, isFull / isEmpty checks — not just list.pop().

  A2PythonStacks, queues, lists & trees 9618 §19.1 ↔ Python
  Run

• Linked list with nodes and pointers

  Node objects linked by a next reference; insert at the front, traverse, delete a value.

  A2PythonStacks, queues, lists & trees 9618 §19.1 ↔ Python
  Run

• Binary search tree — insert and in-order traversal

  Recursive insert and traversal on a tree of nodes. In-order gives the values sorted.

  A2PythonStacks, queues, lists & trees 9618 §19.1 ↔ Python
  Run

• Hash table with linear probing

  A hash function (key mod size) and collision handling by probing — the §19.1 implementation, before using dict.

  A2PythonStacks, queues, lists & trees 9618 §19.1 ↔ Python
  Run

• Recursion — factorial, Fibonacci, GCD

  Base case + general case. Open the Trace tab to see n shrink as the calls wind in.

  A2PythonRecursion 9618 §19.2 ↔ Python
  Run

• Towers of Hanoi

  The classic recursive puzzle: move n-1 discs aside, move the last, move the n-1 back.

  A2PythonRecursion 9618 §19.2 ↔ Python
  Run

Also for this topic: 11 Java programs · 10 VB.NET programs in the browser compilers.

• ancestor/2 — the classic recursive rule

  Base case: a parent is an ancestor. Recursive case: a parent of an ancestor is an ancestor. Order of the clauses matters.

  A2Recursive rules 9618 §20.1
  Run

• Lists — [Head | Tail]

  A list is a head and a tail. Unification splits it: [H|T] = [a, b, c] gives H = a, T = [b, c].

  A2Lists 9618 §20.1
  Run

• Recursing over a list — length, sum, count

  Base case on [], recursive case on [H|T]. Note that the arithmetic comes AFTER the recursive call so N1 has a value.

  A2Lists 9618 §20.1
  Run

• Factorial and Fibonacci

  Recursion with arithmetic. The guard N > 0 stops the recursion running below zero.

  A2Arithmetic 9618 §20.1
  Run

• Push, push, pop

  The first stack question: three pushes, two pops, what is left and where is TopPointer?

  ASA2Stacks 9618 §10.4
  Open

• Stack overflow and underflow

  A stack of 3: the fourth push is refused; popping past empty is refused too.

  ASA2Stacks 9618 §10.4
  Open

• Stack as a bracket checker

  Push every opening bracket, pop on every closing one — the stack is empty at the end only if the brackets match.

  A2Stacks 9618 §19.1
  Open

• Linear queue fills up

  Why a linear queue is wasteful: after dequeuing, the space at the front cannot be reused.

  ASA2Queues 9618 §10.4
  Open

• Circular queue wrap-around

  The same operations on a circular queue: RearPointer wraps to 1 and Ed fits.

  ASA2Queues 9618 §10.4
  Open

• Print queue

  Jobs arrive and are printed in order — FIFO in action.

  ASQueues 9618 §10.4
  Open

• Insert into an ordered linked list

  Values arrive out of order; each takes the next free node and is linked in order — watch StartPointer and FreePointer.

  ASA2Linked lists 9618 §10.4
  Open

• Delete from a linked list

  Deleting relinks the previous node and returns the node to the free list — the data may still be visible in the array.

  A2Linked lists 9618 §19.1
  Open

• Search a linked list

  Follow the pointers from StartPointer until the value or pointer 0.

  A2Linked lists 9618 §19.1
  Open

• Build a binary search tree

  Insert 50, 30, 70, 20, 40, 60, 80 — smaller to the left, larger to the right — and read off the arrays.

  A2Binary trees 9618 §19.1
  Open

• In-order, pre-order, post-order

  The same tree, three traversals — in-order gives sorted output; the others are the exam's favourite trick.

  A2Binary trees 9618 §19.1
  Open

• Tree of words

  Strings compare alphabetically — insert names and search for one.

  A2Binary trees 9618 §19.1
  Open

• Sorted input makes a bad tree

  Inserting 1, 2, 3, 4, 5 in order gives a tree that is really a list — every FIND walks the whole thing.

  A2Binary trees 9618 §19.1
  Open

• Hash table with MOD 10

  Keys hashed with key MOD 10; 23 and 13 collide, so 13 is probed to the next free slot.

  A2Dictionaries / hash tables 9618 §19.1
  Open

• Hashing words by ASCII sum

  A string key is turned into a number (sum of ASCII codes) before MOD — see the working for each key.

  A2Dictionaries / hash tables 9618 §19.1
  Open

• Delete leaves a tombstone

  Deleting a key that another key was probed past must not break later lookups.

  A2Dictionaries / hash tables 9618 §19.1
  Open

• Read: a Stack class

  A class that wraps an array and TopPointer — the ADT as an object.

  A2Read the code → draw the diagram 9618 §20.1
  Open