Design Paradigm Clinic

Retrieval Prompts

1. Name the five paradigms covered in this module and give a one-line identifier for each.
2. State the exchange argument template for a greedy correctness proof.
3. State the two properties required for DP to apply.
4. Explain the difference between backtracking and brute force.
5. Give the recurrence for mergesort and quicksort (expected) and their solutions.

Compare and Distinguish

Separate these pairs:

• brute force versus backtracking
• divide-and-conquer versus dynamic programming (when both split the input)
• greedy versus DP (same optimization goal, different structure)
• memoization versus tabulation

Common Mistake Check

Identify the error:

1. "My greedy works on all the sample inputs, so it is correct."
2. "I memoized the recursion, so the runtime is polynomial."
3. "Divide-and-conquer is always faster than iteration."
4. "Backtracking is the same as brute force, just recursive."
5. "Since I have optimal substructure, greedy will work."

Mini Application

Paradigm triage

For each problem: (a) restate in one sentence; (b) estimate the brute-force runtime; (c) identify the paradigm you would use; (d) justify the choice in 2-3 sentences.

1. Count inversions in an array of n = 10^6 integers.
2. Given n = 20 items with weight and value, maximize total value subject to a weight cap.
3. Schedule n = 10^5 unweighted activities to maximize count.
4. Same as 3 but each activity has a value; maximize total value.
5. Minimum number of coins from {1, 3, 4} to make amount T = 10^5.
6. Given a boolean formula over n = 15 variables, decide satisfiability.
7. Find the length of the longest increasing subsequence of A.
8. Given n = 10^4 points in the plane, find the closest pair.

Exchange arguments

For each, prove optimality of the greedy rule or give a counterexample:

1. Activity selection: pick earliest finish time.
2. Fractional knapsack: sort by value/weight descending.
3. Huffman coding: merge the two lowest-frequency nodes at every step.
4. Minimum-sum interval cover: sort intervals by left endpoint and take any greedy cover.

DP state design

For each, state the state, recurrence, base cases, and runtime:

1. Edit distance between strings X and Y.
2. Longest common subsequence of X and Y.
3. 0/1 knapsack with capacity W.
4. Matrix chain multiplication of n matrices.
5. Weighted interval scheduling.

Recurrence sketch

Write the recurrence for each and solve with the master theorem or recursion tree:

1. Mergesort on n elements.
2. Quicksort expected running time with random pivot.
3. Karatsuba multiplication: T(n) = 3 T(n/2) + n.
4. Strassen matrix multiplication: T(n) = 7 T(n/2) + n^2.

Evidence Check

This page is complete only if you can:

• triage an unfamiliar problem into a paradigm in under 5 minutes
• write a correct exchange argument or counterexample for a proposed greedy
• write a DP state and recurrence before touching the code
• pick up a familiar recurrence and solve it from memory

Integrated Paradigm Classification Drill

Classify each problem as brute force, greedy, divide and conquer, dynamic programming, or "needs more information." Then write one sentence naming the evidence.

1. Try every possible subset to find the cheapest valid server placement.
2. Sort intervals by finish time and choose the next compatible interval.
3. Split an array in half, solve each half, and combine crossing information.
4. Choose a local cheapest edge repeatedly in a graph without checking cycles.
5. Optimize a sequence where each decision depends on the previous two positions.
6. Count ways to form a target amount using unlimited coins.
7. Find whether a target exists in a sorted array.
8. Pick the first design pattern you remember for every object-modeling problem.

For each greedy or DP classification, add either an exchange-argument sketch, a counterexample, or a recurrence-to-state sketch. The classification alone is not accepted.