CIS 3490 — Design & Analysis of Algorithms

📊 Line Coverage — proof every algorithm line is hit

Counts every step the animation emits per pseudocode line (incl. both TRUE and FALSE branches of every IF). After a complete run, every executable line should have count ≥ 1.

How insertion sort works

⚠ Section C exam tip: when you trace a graph, write the pseudocode FIRST, then the iteration steps. Both are graded. Always label edges as Tree/Back/Cross.

⚠ THE RULE

Wrong first term = ZERO for entire question. No alternative methods accepted. No partial marks in Section A. Section B questions are worth 5 marks each — your first line alone is typically worth 2.

Drill until you can write each opening cold in under 10 seconds.

⚠ MARKING SCHEME REMINDER

Section C trace questions are graded on the table format above plus the derivation line below. Must use the technique asked (insertion = shift+insert, selection = find-min+swap, DFS = stack-based, BFS = queue-based). Alternative algorithms = 0 marks even if correct.

Always end with: C_worst(n) = Σ_{i=1}^{n-1} i = n(n−1)/2 ∈ Θ(n²) (insertion/selection) or Tree edges: ... | Back/Cross edges: ... (DFS/BFS).

Marking-scheme answer

⏱ TIMELINE

Exam: Monday 2:30 PM · Now: Saturday/Sunday · Target: 38/50 (75%) — drop up to 12 marks and still pass.

Failure mode (per the Master Plan diagnosis): "conflates understanding with retrieval. The exam tests retrieval speed not depth." Every program here is timed/graded for retrieval.

📅 SATURDAY NIGHT (10 PM → 1 AM, then sleep)

→ SLEEP 6 hours minimum. Memory consolidates overnight.

📅 SUNDAY (7 AM → 10 PM)

📅 MONDAY (6 AM → 2:30 PM exam)

THE NON-NEGOTIABLE RULES

• Every topic gets its time slot and then it ENDS. Physical timer. When it goes off, write DONE and move on.
• One worked example → immediate cold attempt. No passive explanation.
• Mock exam at 1 PM Sunday while FRESH — not after 8 hours of grinding.
• After mock: fix only failures. Do not re-study what you got right.
• Study ends 9 PM Sunday. Sleep 9 hours. Structural, not optional.
• Monday is recall and rest only. No new learning after 8 AM.

After review: feed any wrong answers into 🚨 First-Move Drill if you missed the opening line, or ✎ Design Bank if you missed pseudocode, or ⚡ MC Blitz if you missed multiple-choice.

⚠ Mocks 2 (D&C), 3 (Asymptotic Deep Dive), and 4 (Full Coverage Hardest) are in your original MockExam.pdf. Print or open them on paper for additional cold simulations.

📊 Line Coverage — per-algorithm pseudocode hit tracking

Executable lines per algorithm. Binary search lines 7/8 (low=mid+1 / high=mid-1) should BOTH fire across a complete search unless target is at midpoint. Line 9/10 (return -1) only fires when target is absent.

⚠ Section C/D exam reminder

When multiple candidate edges have the same min weight, the tie-break rule is: pick the edge whose NEW (non-tree) vertex comes first alphabetically. If still tied, pick the one whose tree vertex comes first alphabetically. Complexity: O(|V|²) array-based, O((V+E) log V) with a binary heap.

Notes

Dijkstra requires non-negative edge weights — for negative weights use Bellman-Ford. Complexity: O(V²) array-based, O((V+E) log V) with binary heap, O(E + V log V) with Fibonacci heap. Greedy paradigm: pick the closest unvisited each step (which is provably the final shortest distance).

📊 Line Coverage — proof every BellmanFord line is hit

Tracks step-emit count per pseudocode line. After a complete run, all executable lines should be hit (the negative-cycle branch only fires when the chosen graph has one).

Why Bellman-Ford over Dijkstra?

Dijkstra fails with negative weights — its greedy choice (lock-in nearest unvisited) can finalize a vertex before a longer-then-cheaper-via-negative path is found. Bellman-Ford does NOT commit to any vertex; it simply relaxes every edge |V|-1 times. After |V|-1 passes, every shortest path of ≤ |V|-1 edges has stabilized. A |V|-th pass that still relaxes ANY edge ⇒ negative cycle exists.

Complexity: Θ(V·E). Slower than Dijkstra's O(E + V log V), but more general. Paradigm: Dynamic Programming — dist[v] is built up from shorter sub-paths.

📊 Line Coverage — BetterForwardElimination + Back-Substitution

Tracks step-emit count per pseudocode line. Pivot-search lines (3-7) fire only when partial pivoting is enabled.

Why is it Θ(n³)?

Three nested loops: outer i (1..n-1), middle j (i+1..n), inner k (i..n+1). Total mults ≈ Σᵢ₌₁ⁿ⁻¹ (n-i)(n-i+1) ≈ Σ p² ≈ n³/3. Doubling n → 8× runtime.

Partial pivoting swaps in the row with the largest |A[j,i]| as the pivot before eliminating. Why? In floating-point, dividing by a tiny pivot (e.g. 0.00001) creates a huge multiplier that swamps precision in other rows. Pivoting keeps the multiplier ≤ 1, preserving numerical stability. It also handles A[i,i]=0 (basic algorithm crashes).

Paradigm: Transform & Conquer / Instance Simplification — transform a general system into upper-triangular (a simpler instance), then solve by back-substitution.

Array (1-indexed) · green = sorted region

📊 Line Coverage — HeapBottomUp + SiftDown + Heapsort wrapper

Tracks step-emit count per pseudocode line. Both child-comparison branches of SiftDown should fire (left bigger vs right bigger).

Why is heap construction Θ(n) but heapsort Θ(n log n)?

Bottom-Up Heap Construction: A node at height h sifts down at most h levels. Most nodes are near the bottom (height 0/1), so cost = Σₕ h·(nodes at h) ≈ 2n ⇒ Θ(n). (Top-down insert-one-at-a-time costs Θ(n log n) — strictly worse.)

Heapsort: Stage 1 = Θ(n) construction; Stage 2 = n−1 extractions × O(log n) sift-down each = Θ(n log n). Overall Θ(n log n). In-place: the "deleted" max goes into the freed slot at the back, so the same array becomes the sorted output. Not stable — sift-down can reorder equal keys.

Mapping (1-indexed): root = H[1] · parent(i) = ⌊i/2⌋ · left(i) = 2i · right(i) = 2i+1. Last parent = ⌊n/2⌋. Leaves at indices ⌊n/2⌋+1..n already satisfy parental dominance (no children).

Paradigm: Transform & Conquer / Representation Change — re-represent the array as a max-heap, then exploit the dominance property to extract sorted elements.

4 Rotation Types

BF formula: BF(node) = height(left) − height(right). AVL invariant: BF ∈ {−1, 0, +1} for every node. Height bound: h < 1.4405 log₂(n+2) − 1.3277. Search/Insert/Delete: Θ(log n) worst case.

Array · pink=pivot · gold=i · purple=j · green=sorted position locked

📊 Line Coverage — proof every Partition/Quicksort line is hit

Tracks step-emit count per pseudocode line. Both TRUE and FALSE branches of every IF should fire across a complete sort.

Why partition is the soul of Quicksort

Hoare partition uses two scanning indices that walk toward each other. Index i scans left-to-right past anything strictly less than the pivot. Index j scans right-to-left past anything strictly greater than the pivot. Both stop at equality — this is critical for duplicates (otherwise an all-equal array splits 0 / n-1 and we get Θ(n²)). When i < j we swap A[i] ↔ A[j] and advance both. When i ≥ j we swap pivot ↔ A[j] to place pivot in its final position; j is returned as the split.

Recurrence: T(n) = T(k) + T(n−k−1) + Θ(n) where k = elements smaller than pivot. Best: k = n/2 each level ⇒ T(n)=2T(n/2)+n ⇒ Θ(n log n). Worst: k = 0 or n−1 (sorted, pivot=first ⇒ smallest each time) ⇒ T(n)=T(n−1)+n ⇒ Θ(n²). Average: ≈ 1.39·n log₂n — only ~39% slower than the theoretical optimum.

Quicksort is in-place (no auxiliary array like mergesort) but not stable (swaps can reorder equal keys). Median-of-three pivoting + Randomization push the worst case toward improbable.

Paradigm: Divide & Conquer — but unusual because all the work happens in the divide step (partitioning), none in the combine step (subarrays are already in their final relative regions).

Element Uniqueness

The Big Lesson

Presorting trades the up-front cost of an O(n log n) sort for the dramatic simplification of the post-sort problem. Worth it when the post-sort algorithm is linear (so total is dominated by the sort) and you'd otherwise pay quadratic. Not worth it for a single sequential search (n log n + log n > n).

Searching m times on the same data: m·n (sequential) vs n log n + m log n (sort+binary). Crossover at m ≈ log n.

Paradigm: Transform & Conquer · Instance Simplification — transform an arbitrary array into a sorted one (simpler instance), then solve.

Why does saving 1 multiplication matter so much?

For 2×2 the difference is trivial (7 vs 8 mults). But Strassen recurses: when n>2, each of the 7 sub-products is itself an (n/2)×(n/2) matrix multiplication done via Strassen. The recurrence is M(n) = 7M(n/2). By the Master Theorem (a=7, b=2, f(n)=Θ(n²)): a > b^d (7 > 4) ⇒ T(n) ∈ Θ(n^log_b a) = Θ(n^log₂7) ≈ Θ(n^2.807). Better than Θ(n³) by a polynomial factor.

The 7 magic products: M1 = (A00+A11)(B00+B11), M2 = (A10+A11)·B00, M3 = A00·(B01−B11), M4 = A11·(B10−B00), M5 = (A00+A01)·B11, M6 = (A10−A00)(B00+B01), M7 = (A01−A11)(B10+B11). Then: C00 = M1+M4−M5+M7, C01 = M3+M5, C10 = M2+M4, C11 = M1+M3−M2+M6. 7 multiplications + 18 additions.

Trade-off: Strassen uses 18 additions vs brute-force's 4 additions per 2×2. Constant overhead means Strassen only wins for large n (crossover ≈ 100 in practice). The naive D&C split (8 sub-products) gives the same Θ(n³) — Strassen's insight was that the algebraic identity reduces 8 to 7.

Paradigm: Divide & Conquer with algebraic refinement. Faster algorithms exist (Coppersmith-Winograd O(n^2.376), more recent ~O(n^2.371)), but huge hidden constants make them impractical.

Polynomial

Result p(x)

Why Horner's Rule works

The insight: Brute force computes each x^i from scratch (no shared work). Horner factors the polynomial into nested form:

p(x) = (...((aₙ·x + aₙ₋₁)·x + aₙ₋₂)·x + ... + a₁)·x + a₀

Each iteration does one multiplication and one addition. n iterations total ⇒ n mults, n adds, total Θ(n). Brute force does (n+1)(n+2)/2 ∈ Θ(n²) mults due to recomputing powers. Horner is provably optimal for polynomial evaluation without preprocessing.

Paradigm: Transform & Conquer · Representation Change — re-express the polynomial in nested form to eliminate redundant work.

🔁 Bonus: LCM via GCD (Problem Reduction Demo)

Classic problem reduction: lcm(m,n) reduces to gcd(m,n) via the identity lcm(m,n) = m·n / gcd(m,n). GCD via Euclid is O(log n), so LCM also runs in O(log n). Old way: prime factorization (expensive).

DP Recurrence (Binomial via Pascal's Identity)

function Binomial(n, r):                 // Θ(n·r) time, Θ(n·r) space
  if r == 0 or r == n: return 1            // base case
  return Binomial(n-1, r-1) + Binomial(n-1, r)

Bottom-up DP fills the triangle row-by-row, each cell = sum of two cells above.
This is the classic dynamic programming example — direct recursion repeats work
exponentially; memoization/DP reduces it to Θ(n·r) ⇐ store all C(n,r) for n' ≤ n.

4 Key Identities (all visible in the triangle)

1. Pascal's Identity: C(n+1, k) = C(n, k−1) + C(n, k). Every cell = sum of two cells above. This is the recurrence.
2. Symmetry: C(n, r) = C(n, n−r). Every row mirrors around its center. (Try "symmetry" mode above.)
3. Row sum: Σⱼ C(n, j) = 2ⁿ — total number of subsets of an n-set. (Try "row sum" mode.)
4. Hockey stick: Σⱼ₌ᵣⁿ C(j, r) = C(n+1, r+1) — diagonal sums. (Try "diagonal" mode.)
Plus Vandermonde: C(m+n, r) = Σ C(m, r−k)·C(n, k), and the binomial theorem (x+y)ⁿ = Σ C(n,j)·xⁿ⁻ʲyʲ — shown live in the right panel above.

Matrix · pink = current cell · green = found · grey = eliminated

📊 Line Coverage — SortedMatrixSearch

Tracks step-emit count per pseudocode line. Lines 5/7 (move-left vs move-down) both fire when the key isn't trivially at the corner.

Why O(n) and not O(n²) or O(log n)?

O(n²) brute force scans every cell. O(log n) per row using binary search × n rows = O(n log n). But the corner trick beats both: starting at the top-right corner exploits the sortedness of BOTH dimensions simultaneously. Each comparison decides "eliminate this whole row" or "eliminate this whole column" — never both. After at most n + n = 2n steps either we find K or we walk off the grid ⇒ O(n).

Variable decrease-and-conquer: the "decrease" is not a fixed n−1 or n/2 — it adapts per comparison (sometimes a row drops, sometimes a column drops). Bottom-left also works (mirror direction). Top-left and bottom-right do NOT — at those corners both moves go the same way and the algorithm fails.

Other "Variable Decrease" exam algorithms: Euclid's GCD (gcd(m,n) reduces to gcd(n, m mod n)), Interpolation Search (jump proportional to key value, expected O(log log n) on uniform data).

The Addition Rule

Process vertices in topological order. Label S = 1. For every vertex v after S, set N(v) = Σ N(u) over all u → v incoming edges. The value at F is the total path count. This works because every path to v ends with exactly one incoming edge from some u, and the paths through different u's are disjoint.

Complexity: Θ(V + E) — one pass through each vertex, summing its in-edges. Far better than the brute-force "enumerate every path" which is exponential.

Lattice paths connect to Pascal's triangle! The number of paths in an m×n grid from corner to corner (only right + up moves) is C(m+n, m). Try the lattice presets — the path count at the top-right corner matches Pascal's triangle entry. This is the classic "lattice paths = binomial coefficients" identity.

Paradigm: Dynamic Programming on a DAG. Stores intermediate path counts to avoid re-enumeration. Same technique powers shortest-path counting, viability checks, and many DP problems on DAGs.

Each Q links to the program inside this studio that drills it. Click the ▶ button below the Q to see the marking-scheme solution. Practice the linked program first, then attempt the Q on paper, then reveal.

DeepSeek grades on the rubric below the mode selector. After submission you'll get: marks awarded, what you got right, what you missed, and a targeted re-do hint. Use this for Section D (Algorithm Design — 15 marks).

Both methods are Θ(V+E). DAG required — any cycle makes topological order impossible (DFS would find a back edge; Kahn would leave non-zero in-degrees stuck). Method 1 (DFS): output vertices in REVERSE order of when they finish. Method 2 (Kahn): repeatedly find vertices with in-degree 0, output, remove their outgoing edges.

A Binary Search Tree obeys: for every node, all left descendants are smaller and all right descendants are larger. Traversal complexities are all Θ(n). BST insert is Θ(log n) avg, Θ(n) worst (skewed). Self-balancing variants (AVL, red-black) guarantee Θ(log n). Use in-order traversal on a BST to read its values in sorted order.

The standard backward-sub move (memorize): Expand T(n) by substituting the recurrence repeatedly. Look for the i-th step pattern: T(n) = T(n−i) + i·W for additive (or 2ⁱ·T(n−i) + W(2ⁱ−1) for doubling). Then set i so the base case appears: i = n − 1 for n→n−1 recurrences, i = log n for n→n/2 recurrences. Finally simplify with a Σ formula (Σi = n(n+1)/2, Σi² = n(n+1)(2n+1)/6, Σ2ⁱ = 2ⁿ−1).

First-move setup (cheatsheet): C(n) = Σᵢ₌₀ⁿ⁻² Σⱼ₌ᵢ₊₁ⁿ⁻¹ 1
Σ formulas to remember: Σi = n(n+1)/2 · Σi² = n(n+1)(2n+1)/6 · Σi³ = [n(n+1)/2]²
Nested for j=i+1..n-1: inner count = (n-1) − (i+1) + 1 = n−1−i

The 6 paradigms (cheatsheet)

• Brute Force — directly implement definition, no optimization (e.g. closest pair, TSP, knapsack)
• Decrease & Conquer — ONE smaller instance: by constant (insertion sort), by factor (binary search), by variable (Euclid GCD)
• Divide & Conquer — MULTIPLE independent subproblems, recurse, MERGE (merge sort, D&C find max)
• Transform & Conquer — change representation, then solve (presort, Horner's, distribution counting)
• Greedy — locally optimal at each step (SJF, Prim's, Dijkstra)
• Dynamic Programming — optimal substructure + overlapping subproblems, build table (max non-adj, weighted activity)

YOU NEED 38/50.

Section A (10) target: 7-8 · Section B (15) target: 10-12 · Section C (10) target: 7-8 · Section D (15) target: 8-10

First line correct = partial marks. Use this. You have the time. Execute the plan.