Which technique?
Recognise which method a question wants.
Exam questions rarely name the method. Use this page to go from what the question looks like to what to do. It grows as the course continues (greedy, DP and graphs get added when we reach them).
"Analyse this…" questions
| If the question shows… | Do this | Topic |
|---|---|---|
| loops with fixed bounds | multiply the loop sizes (inside-out) | 5 |
| an inner loop bound that depends on the outer variable | write the sum, use a closed form | 0, 5 |
| a counter that doubles/halves | iterations | 5 |
| a function that calls itself | write the recurrence | 8 |
| recursion tree → equal / shrinking / growing levels | 8 | |
| expansion (unroll), then a sum | 8 | |
| "prove " for a recurrence | guess from the tree, then induction (substitution) | 8 |
| "best / worst case" | find the input that makes the inner loop shortest / longest | 4 |
"Prove…" questions
| If the question says… | Use | Topic |
|---|---|---|
| "show " | find explicit () and | 6 |
| "show " | contradiction: get constant | 6 |
| "prove this loop algorithm is correct" | loop invariant: Init / Maintenance / Termination | 3 |
| "prove this recursive algorithm is correct" | induction on | 3 |
| "prove for all " (a sum or formula) | induction | 2 |
| "there is no…" / "impossible" | contradiction | 2 |
| "if P then Q" where "not Q" is concrete | contraposition | 2 |
"Design an algorithm…" questions (strategy picker)
| Problem smell | Try first | Notes |
|---|---|---|
| small input, or you just need something correct | Brute force | try every possibility; often , or |
| splits into independent halves that combine cheaply | Divide & conquer | e.g. merge sort, binary search; write the recurrence |
| "build the answer one element at a time, keeping it valid" | Incremental | e.g. insertion sort; prove with a loop invariant |
| a locally best choice seems to never hurt | Greedy | coming later in the course |
| subproblems overlap / repeat | Dynamic programming | coming later in the course |
| networks, routes, connections | Graph algorithms | coming later in the course |
Assignment write-ups (per the course rules, Intro Slide 19) need: a plain-English description, a worked example, a correctness argument and a running-time analysis. Each topic page models all four.