Question 7 of 8: Algorithm Concepts

Question 7: Algorithm Concepts (20 marks: five of six requested, 5 each — all six answered below)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

1. Divide and conquer

A divide-and-conquer algorithm splits a problem into smaller independent subproblems of the same form, solves each recursively, and combines the sub-results into the answer for the original problem. Examples: merge sort (Q5 above) — divide the array in half, sort each half, merge; and binary search — divide the search range in half using one comparison, recurse into the half that could contain the target, discard the other half entirely.

2. Breadth-first search (BFS)

BFS explores a graph outward from a source vertex one "distance layer" at a time, using a FIFO queue: visit the source, then all its unvisited neighbours, then all of their unvisited neighbours, and so on. Examples: finding the shortest path (fewest edges) between two vertices in an unweighted graph; computing connected components; the classic "word ladder" / puzzle-shortest-solution problems where each state transition has equal cost.

3. Use of randomness in algorithms

A randomized algorithm makes some of its decisions using random bits rather than fixed rules, trading a (usually vanishingly small) probability of a bad outcome for much better expected performance or a simpler algorithm. Examples: randomized quicksort — picking the pivot uniformly at random guarantees $O(n\log n)$ expected time on every input, defeating any adversary that knows the algorithm but not its random choices; and Monte Carlo primality testing (e.g. Miller–Rabin), which answers "probably prime" or "definitely composite" using far less work than deterministic primality proving.

4. "Greedy" algorithms

A greedy algorithm builds a solution step by step, at each step making the choice that looks best right now (locally optimal) without reconsidering earlier choices, and never backtracks. Greedy only produces a globally optimal answer for problems that have the right structure (a matroid-like "exchange" or "cut/cycle" property); otherwise it can be badly wrong. Examples: Kruskal's and Prim's minimum-spanning-tree algorithms (Q4 above) — always take the cheapest safe edge; Huffman coding — always merge the two least-frequent symbols; both are provably optimal because of the cut/exchange properties specific to those problems.

5. Dynamic programming

Dynamic programming solves a problem by breaking it into overlapping subproblems, solving each subproblem only once, and storing (memoizing) its result so later requests for the same subproblem are answered in $O(1)$ instead of being recomputed — applicable whenever the problem has both optimal substructure and overlapping subproblems (the feature that distinguishes it from plain divide-and-conquer). Examples: the DAG shortest-path DP used for Jerry's flights in Q6; the classic 0/1 knapsack problem, solved in $O(nW)$ by tabulating the best value achievable for every (item count, remaining capacity) pair rather than trying all $2^n$ subsets.

6. Tail recursion

A recursive call is a tail call when it is the very last operation the function performs — nothing (not even a pending multiplication or addition) is left to do with the result after the recursive call returns. A compiler that performs tail-call optimisation can then reuse the current stack frame for the call instead of pushing a new one, turning the recursion into a loop that runs in $O(1)$ stack space instead of $O(n)$. Examples: an accumulator-style factorial, fact(n, acc) { return n <= 1 ? acc : fact(n-1, n*acc); }, is tail-recursive (the multiplication happens before the call, folded into acc), whereas the naive fact(n) { return n <= 1 ? 1 : n * fact(n-1); } is not, because the multiplication by n happens after the recursive call returns and so each call must stay on the stack awaiting that result.