Difficulty: Intermediate to Advanced | Prerequisites: Basic Java programming, loops, arrays, recursion fundamentals.
This set of topics covers the core algorithm-design strategies you will meet throughout COE 301: recursion, divide-and-conquer, greedy choice, and dynamic programming. Each strategy answers a different question about how to break a problem down, and the exam tests whether you can pick the right one, trace its execution, and analyse its running time. If you are comfortable writing simple recursive methods and understand Big-O notation at an intuitive level, you have enough background to start here.
Recursion solves a problem by reducing it to smaller copies of itself; the Towers of Hanoi is the classic example, with exponential cost. QuickSort uses a pivot to partition an array and runs in O(n log n) on average but O(n²) in the worst case. Matrix Chain Multiplication uses dynamic programming to find the cheapest (or most expensive) way to parenthesise a sequence of matrix products, and greedy algorithms make locally optimal choices at each step without looking ahead.
Recursion
A technique where a function calls itself with a smaller input until it reaches a base case. Think of it as solving a big problem by first solving a slightly smaller version of the same problem.
Base case
The condition under which a recursive function stops calling itself and returns directly. In simple terms, this is the "smallest" version of the problem that you can answer without further recursion.
Recurrence relation
A mathematical equation that expresses the running time of a recursive algorithm in terms of the running time on smaller inputs, e.g. T(n) = 2T(n – 1) + 1. Think of it as a formula that counts total work by adding up work at each level of recursion.
Greedy algorithm
An algorithm that makes the locally best choice at each step, hoping this leads to a globally optimal solution. In simple terms, it always picks whatever looks best right now without considering future consequences.
Dynamic programming (DP)
A strategy that solves a problem by breaking it into overlapping sub-problems, solving each once, and storing results in a table. Think of it as "recursion with a notebook" so you never redo work.
Pivot (QuickSort)
The element chosen to partition the array into two halves: elements less than the pivot go left, elements greater go right. In COE 301 problems, the pivot is typically the first element of the current sub-array.
Balanced partition
A partition where both halves are roughly equal in size. This is the best case for QuickSort and happens when the pivot is the median.
Matrix chain multiplication
The problem of finding the best order to multiply a sequence of matrices to minimise (or maximise) the total number of scalar multiplications. The order of multiplication does not change the result, but it dramatically changes the cost.
Parenthesisation
The specific grouping of matrices in a chain product, indicated by parentheses. Different parenthesisations of the same chain can differ by orders of magnitude in cost.
Scalar multiplication
A single multiply operation on two numbers. When multiplying an (r1 × c1) matrix by a (c1 × c2) matrix, the total scalar multiplications required is r1 × c1 × c2.
Time complexity (Big-O)
A measure of how the running time of an algorithm grows as the input size increases, ignoring constant factors. O(n²) means roughly proportional to the square of the input size.
Move n disks from source to destination using one auxiliary peg
Rules: only move one disk at a time, never place a larger disk on a smaller one
Algorithm: move n–1 disks to auxiliary, move disk n to destination, move n–1 disks from auxiliary to destination
Recurrence: T(n) = 2T(n – 1) + 1, which solves to 2ⁿ – 1 moves
Time complexity: O(2ⁿ)
Four locations: Start, Aux1, Aux2, Dest
Permitted moves form a directed cycle: Start → Aux1 → Aux2 → Dest → Start
You cannot skip locations; a disk at Start can only go to Aux1, not directly to Dest
Base case (n = 1): move the disk along the full path Start → Aux1 → Aux2 → Dest (three individual moves)
Recursive step for n disks:
Move n–1 disks from Start to Dest (recursive call)
Move disk n from Start to Aux1
Move n–1 disks from Dest back to Start (recursive call)
Move disk n from Aux1 to Aux2
Move n–1 disks from Start to Dest (recursive call)
Move disk n from Aux2 to Dest
This produces three recursive calls on n–1 disks plus three single-disk moves
Recurrence: T(n) = 3T(n – 1) + 3
Time complexity: O(3ⁿ)
Divide-and-conquer sorting algorithm
Choose a pivot, partition the array so all elements less than the pivot are on the left, all greater are on the right, then recursively sort each half
In COE 301, the pivot is always the first element of the current sub-array
Best case (balanced partitions):
The pivot lands in the middle, splitting the array into two roughly equal halves
For n = 13, the first element should be 7 (the median) so that six elements fall on each side
Example array: [7, 4, 2, 1, 3, 6, 5, 11, 9, 8, 10, 12, 13]
Each sub-array's first element should also be its sub-array's median for the pattern to repeat
Recurrence: T(n) = 2T(n/2) + O(n), giving O(n log n)
Worst case (maximally unbalanced partitions):
The pivot is always the smallest or largest element, producing one partition of size 0 and one of size n–1
This happens when the array is already sorted or reverse sorted
Example arrays: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] or [13, 12, 11, ..., 1]
Recurrence: T(n) = T(n–1) + O(n), giving O(n²)
Recursion depth in worst case: n
Base case: when n = 1, zero recursive calls are made
Given a sequence of matrices M1, M2, ..., Mk, find the parenthesisation that minimises (or maximises) the total number of scalar multiplications
Matrix Mi has dimensions n_i × n_(i+1). The subscript notation M_(a,b) means the matrix has a rows and b columns
The cost to multiply two adjacent matrices of dimensions (r1 × c1) and (c1 × c2) is r1 × c1 × c2 scalar multiplications
The diagonal M(i,i) is always 0 (a single matrix requires no multiplication)
DP formula for minimum: M(i,j) = min over i ≤ k < j of { M(i,k) + M(k+1,j) + n_i × n_(k+1) × n_(j+1) }
For maximum, replace min with max
Time complexity of the DP algorithm: O(n³)
Worked example from the exam:
Chain: M(9,3) × M(3,9) × M(9,1) × M(1,8) × M(8,4)
Dimensions sequence: 9, 3, 9, 1, 8, 4
A single multiplication of a 9×3 by a 3×9 matrix costs 9 × 3 × 9 = 243 scalar multiplications
Maximum number of scalar multiplications through parenthesisation: 1,251
A robot moves through a 2D grid collecting coins
At each cell (r, c), the robot evaluates three adjacent cells: up (r–1, c), down (r+1, c), and right (r, c+1)
It picks the cell with the highest coin value among valid neighbours
Tie-breaking priority: Up > Down > Right
The robot must check bounds (row index between 0 and mat.length – 1)
The robot terminates when it reaches the last column
This is a greedy approach: it makes the locally optimal choice at each step without considering the global path
Algorithm | Recurrence | Closed Form / Complexity |
|---|---|---|
Towers of Hanoi (3-peg) | T(n) = 2T(n – 1) + 1 | O(2ⁿ) |
Restricted Hanoi (4-location cycle) | T(n) = 3T(n – 1) + 3 | O(3ⁿ) |
QuickSort (best case) | T(n) = 2T(n/2) + O(n) | O(n log n) |
QuickSort (worst case) | T(n) = T(n – 1) + O(n) | O(n²) |
Matrix Chain Multiplication (DP) | M(i,j) = min/max { M(i,k) + M(k+1,j) + n_i × n_(k+1) × n_(j+1) } | O(n³) |
Scalar multiplications for one product | (r1 × c1) times (c1 × c2) | r1 × c1 × c2 |
The Towers of Hanoi models backup rotation schemes and recursive data-structure traversals. QuickSort is the default sort in many standard libraries because its average-case performance and cache behaviour are excellent. Matrix chain multiplication shows up whenever you chain expensive linear-algebra operations, such as in computer graphics pipelines or machine-learning model inference. Greedy algorithms underpin scheduling, Huffman coding, and network routing.
Students often think QuickSort is always O(n log n). It is not. The worst case is O(n²), and the exam will test whether you know when that happens (already-sorted input with first-element pivot).
Students often confuse the restricted Hanoi recurrence with the standard one. The restricted version has three recursive calls per level, not two, because the movement graph is a cycle.
Students sometimes assume the greedy robot strategy gives the globally optimal path. It does not. Greedy can miss a better overall route by being short-sighted. The exam tests whether you understand the distinction.
Students frequently forget that M(i,i) = 0 in the matrix chain DP table. A single matrix requires no multiplication at all.
⚠️ The exam asks you to construct specific arrays for QuickSort best and worst cases (n = 13). Practise building median-first arrays recursively.
⚠️ The restricted Hanoi question requires you to write the recursive algorithm and derive the recurrence T(n) = 3T(n–1) + 3. Show your working.
⚠️ Matrix chain problems can ask for either minimum or maximum scalar multiplications. Read the question carefully.
⚠️ The greedy robot question tests tie-breaking: Up > Down > Right. If you get the priority wrong, the entire trace is incorrect.
⚠️ Know the base cases: QuickSort with n = 1 makes zero recursive calls; Hanoi with n = 1 is three moves in the restricted version.
True or false: The standard 3-peg Towers of Hanoi has time complexity O(n²). (False, it is O(2ⁿ).)
Fill in the blank: In QuickSort, if n = 1, the number of recursive calls is ____. (0)
True or false: A greedy algorithm always finds the globally optimal solution. (False.)
Fill in the blank: The diagonal entry M(i,i) in a matrix chain DP table is always ____. (0)
True or false: Sorting the input array in ascending order gives the best-case performance for QuickSort with first-element pivot. (False, that is the worst case.)
Q: What is the Big-O time complexity of the standard Towers of Hanoi algorithm for n disks on a 3-peg system?
A: O(2ⁿ). The recurrence is T(n) = 2T(n – 1) + 1, which solves to 2ⁿ – 1.
Q: For QuickSort with first-element pivot, construct an array of [1..13] that gives optimal (balanced) execution.
A: Place the median (7) first, then recursively place the median of each sub-array first. One valid answer: [7, 4, 2, 1, 3, 6, 5, 11, 9, 8, 10, 12, 13].
Q: For QuickSort with first-element pivot, construct an array of [1..13] that gives worst-case execution.
A: Use an already-sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], or reverse-sorted: [13, 12, 11, ..., 1]. This makes every partition of size 0 and n–1.
Q: How many scalar multiplications are needed to multiply a 9×3 matrix by a 3×9 matrix?
A: 9 × 3 × 9 = 243.
Q: Which of the following describes the greedy approach in the robot pathfinding problem? (a) The robot calculates the total path sum before moving. (b) The robot always picks the adjacent cell with the highest immediate coin value.
A: (b). A greedy algorithm makes the locally optimal choice at each stage.
Q: What is the Big-O complexity of QuickSort in the worst case?
A: O(n²). This occurs when the pivot always produces partitions of size 0 and n–1.
Q: In the robot pathfinding problem, what is the tie-breaking order when adjacent cells have equal coin values?
A: Up > Down > Right. The robot prefers moving up over down, and down over right.
Q: What is the time complexity of the DP algorithm for matrix chain multiplication?
A: O(n³), where n is the number of matrices in the chain.
Recursion and recurrence relations come back in every algorithm unit, including MergeSort and binary search. Dynamic programming extends the idea of recursion by caching results, and you will see the same tabular approach in other DP problems such as longest common subsequence and knapsack. The greedy approach connects to the broader question of when local optima lead to global optima, a theme that reappears in graph algorithms like Dijkstra's shortest path.
recursion, recursive algorithm, base case, recurrence relation, Tower of Hanoi, Towers of Hanoi, restricted Hanoi, directed graph, cycle, QuickSort, quick sort, pivot, partition, balanced partition, worst case, best case, O(n log n), O(n squared), O(n^2), median, sorted array, matrix chain multiplication, matrix chain ordering, parenthesization, scalar multiplication, dynamic programming, DP, DP table, greedy algorithm, greedy approach, robot pathfinding, grid traversal, tie-breaking, Big-O, time complexity, COE 301, introduction to computer programming, University of Texas