Repository Guide | English | 한국어
Last Updated: 2026-11-10
- 1. What Is an Algorithm?
- 2. Complexity Analysis: Big-O, Recurrences, and the Master Theorem
- 3. Data Structures and Basic Sorting
- 4. Divide and Conquer
- 5. Greedy Algorithms
- 6. Dynamic Programming
- 7. Midterm Review: Synthesis
- 8. The Big Picture: How the Three Paradigms Relate
- 8.1 Comparing the Three Paradigms
- 8.2 Decision Flowchart
- 8.3 Same Problem, Different Paradigms
- 8.4 Seven Key Connections
- Connection 1: The Unity of Recursive Thinking
- Connection 2: Divide and Conquer and Logarithmic Complexity
- Connection 3: The Switch from Greedy to DP
- Connection 4: The Hierarchy of the Comparison Lower Bound and Linear Sorting
- Connection 5: Prim ↔ Dijkstra ↔ Huffman
- Connection 6: From the Limits of Divide and Conquer to DP
- Connection 7: Complexity Analysis Connects Everything
- 8.5 Advanced Tips for Writing Answers
- 9. Last-Minute Exam Checklist
- Closing Remarks
There are countless ways to solve a problem. Given two methods for the same problem, one must judge objectively which one is better and why. This requires the following three things.
- A precise definition of what an algorithm is.
- A measurable criterion that fixes what "efficient" means.
- Familiarity with the design patterns that appear repeatedly.
These three points are the core of Week 1, and the later weeks build more complex algorithms on this foundation.
An algorithm is a systematic problem-solving procedure that takes an input and produces the desired output through a finite number of steps.
flowchart LR
I["Input (Problem)"] --> A["Algorithm (finite steps)"]
A --> O["Output (Result)"]
Figure 1. Relationship among input, algorithm, and output
An algorithm must satisfy the following five properties.
| Property | Meaning | Failure Example |
|---|---|---|
| Correctness | It produces the correct output for every valid input. | It returns a wrong answer. |
| Executability | Every step can be executed mechanically. | It contains a non-executable step such as "ask an oracle". |
| Finiteness | It always terminates in a finite amount of time. | An infinite loop occurs. |
| Efficiency | It uses time and space appropriately. | It consumes infeasible resources, such as exponential time. |
| Unambiguity | It is described without ambiguity. | It uses a vague description such as "handle it as appropriate". |
Table 1. Five properties an algorithm must satisfy, with failure examples
When an exam question asks whether a given description is an algorithm, judge it against these five properties.
Niklaus Wirth's law "Algorithm + Data Structure = Program" summarizes this relationship. If the algorithm decides what to do, the data structure decides how to store the data, and the two cannot be separated. For example, only sequential search is possible in an unsorted dictionary, whereas binary search is possible in a sorted one.
Background: The Euclidean GCD was devised around 300 BCE, so it was known 2,300 years before computers appeared.
Key identity:
Why it holds: Let
Implementation:
def gcd(a, b):
while b != 0:
a, b = b, a % b
return aExplanation: Each iteration updates a, b = b, a % b) is a Python idiom.
Trace of gcd(48, 18):
| Step | a | b | a mod b |
|---|---|---|---|
| 1 | 48 | 18 | 12 |
| 2 | 18 | 12 | 6 |
| 3 | 12 | 6 | 0 |
| 4 | 6 | 0 | → return 6 |
Table 2. Step-by-step trace of gcd(48, 18)
Complexity: The worst case is
It can also be implemented with recursion, and it is the prototype of recursive thinking, which reduces a problem to a smaller one. This way of thinking leads to divide and conquer in Week 4.
The classical problems of Week 1 all show, from different angles, the same idea: halving the problem yields
| Problem | Strategy | Worst Case | Key Idea |
|---|---|---|---|
| Finding the maximum | Sequential scan | Every element must be seen at least once | |
| Binary search | Divide and conquer | Compare with the middle value of a sorted array and discard half | |
| Coin change (standard) | Greedy | Choose the largest denomination first | |
| Euler circuit | Graph traversal | Exists when every vertex has even degree | |
| Maze (connected walls) | Right-hand rule | A physical version of DFS | |
| Counterfeit coin (1,024 coins) | Split in half | 10 weighings | |
| Poisoned wine (n jars) | Binary encoding |
|
Each servant = 1 bit of information |
Table 3. Strategies, worst-case complexities, and key ideas of the Week 1 classical problems
Precondition: The array must be sorted.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right: # [Caution] equality is required!
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Explanation: It maintains the invariant that [left, right] is the closed interval not yet examined. Each iteration compares the middle value arr[mid] with target and halves the closed interval. If they are equal, it returns the index; if the target is larger, it discards the left half (left = mid + 1); if smaller, it discards the right half (right = mid - 1). When left > right, the remaining interval is empty, so it returns -1. The complexity is
If the equality in left <= right is omitted, the case where only one element remains in the interval (left == right) is not checked, and an existing key is missed. The equality includes the step that checks a single element.
Comparison: With one million elements, sequential search needs up to 1,000,000 comparisons in the worst case, whereas binary search needs only about 20 (
Problem: One of
Strategy: Assign each jar a binary ID from
Example with 4 jars:
| Jar | Binary | Servant A (bit 1) | Servant B (bit 0) |
|---|---|---|---|
| 0 | 00 | - | - |
| 1 | 01 | - | ✓ |
| 2 | 10 | ✓ | - |
| 3 | 11 | ✓ | ✓ |
Table 4. Binary IDs of 4 jars and which servant tastes each jar
Interpreting the result: For example, if A dies and B survives, jar 2, which corresponds to binary 10, is poisoned.
Generalization:
Problem: Using a balance scale, find the one counterfeit coin (slightly lighter) among 1,024 coins while minimizing the number of weighings.
| Approach | Description | Worst-Case Count |
|---|---|---|
| Compare one by one | Brute force | 1,023 |
| Compare in pairs | A slightly improved method | 512 |
| Split in half | Divide and conquer | 10 |
Table 5. Worst-case number of weighings for each approach to finding the counterfeit coin
Divide-and-conquer solution: Start with 512 vs 512, choose the lighter side, and keep halving: 256 vs 256, 128 vs 128, and so on. Since
An Euler path is a path that traverses every edge exactly once, and an Euler circuit is an Euler path that returns to its starting point.
Theorem:
- An Euler circuit exists only if every vertex has even degree.
- An Euler path (not necessarily a circuit) exists only if there are exactly 0 or 2 vertices of odd degree.
Intuition: In a circuit, every time you enter a vertex you must leave it, so the number of incoming and outgoing edges at each vertex must be equal, and hence the degree is even.
Avoiding bridges: A bridge is an edge whose removal disconnects the graph. Crossing a bridge too early traps you on the other side, making it impossible to traverse all remaining edges.
The big picture of Week 1 is as follows. An algorithm is a systematic procedure that satisfies five properties: correctness, executability, finiteness, efficiency, and unambiguity. The Euclidean GCD is the prototype of recursive thinking, which reduces a problem to a smaller one. The
Given two algorithms for the same problem, one needs a way to compare which one is faster independently of hardware. Running time (in seconds) depends on hardware, but the number of basic operations is an intrinsic property of the algorithm, so the operation count is expressed as a function of the input size
For sufficiently large
The RAM (Random Access Machine) is the standard computational model for theoretical analysis. Each basic operation (assignment, comparison, arithmetic, array access) counts as one time unit, and memory access time is assumed to be constant regardless of the address. Basic operations include the four arithmetic operations, comparison, assignment, array indexing, and pointer dereferencing.
| Type | Meaning | Typical Use |
|---|---|---|
| Worst-case | Guarantees an upper bound that no input can exceed. | The most commonly used type. |
| Average-case | Expresses the expected time under a probability distribution. | Practical, but complicated to compute. |
| Best-case | The case that runs fastest. | Not used as a basis for comparing algorithms. |
| Amortized | Analyzes the average over a sequence of operations. | Used for operations such as expanding a dynamic array. |
Table 6. Four types of complexity analysis and where each is used
The worst case is used most often because it guarantees performance. The promise that this algorithm never exceeds
The exact operation count (e.g.,
Definition:
Intuitively, it means that
Recipe for polynomial proofs: For
Example:
Intuitively, it means that
It means that
Distinguishing the three notations:
-
$O(n^2)$ means at most on the order of$n^2$ . -
$\Omega(n^2)$ means at least on the order of$n^2$ . -
$\Theta(n^2)$ means exactly on the order of$n^2$ .
Write tight bounds:
Growth by input size (to get a feel):
| n | |||||
|---|---|---|---|---|---|
| 10 | 3.3 | 10 | 33 | 100 | 1,024 |
| 100 | 6.6 | 100 | 664 | ||
| 20 | - |
Table 7. Growth of each function by input size
Sorting one billion elements (on a PC performing
- An
$O(n^2)$ algorithm takes about 300 years, which is infeasible. - An
$O(n \log n)$ algorithm finishes in about 5 minutes.
This is why Week 3 abandons the
A recurrence relation is an equation that expresses the value of a function in terms of its values on smaller inputs.
Examples: The following are typical recurrences.
-
$T(n) = T(n-1) + c$ has the factorial form. -
$T(n) = 2T(n/2) + n$ is the recurrence of merge sort. -
$T(n) = T(n/2) + 1$ is the recurrence of binary search.
Solving a recurrence means expressing it in closed form, for example as
Expand the recurrence step by step, find the pattern, and generalize.
Assume
Since
Proof that
Base case:
Inductive hypothesis:
Inductive step: $$ \begin{aligned} T(n) &= 2T(n/2) + n \ &\leq 2 \cdot c(n/2) \log(n/2) + n \ &= cn(\log n - \log 2) + n \ &= cn \log n - cn + n \ &\leq cn \log n \quad (c \geq 1) \end{aligned} $$
Common mistake: When a leftover term remains in the inductive step, as in
Form:
Comparison function:
Three cases:
| Case | Condition | Result | Meaning |
|---|---|---|---|
| 1 |
|
Leaf cost dominates | |
| 2 | Costs balanced across levels | ||
| 3 |
|
Root cost dominates |
Table 8. The three cases of the Master Theorem
Regularity condition (Case 3):
Catalog of key examples:
| Recurrence | Case | Result | |||
|---|---|---|---|---|---|
| 2, 2 | 2 | ||||
| 1, 2 | 2 | ||||
| 2, 2 | 1 | ||||
| 4, 2 | 1 | ||||
| 4, 2 | 2 | ||||
| 3, 4 | 3 |
Table 9. Examples of applying the Master Theorem
When the Master Theorem cannot be used:
-
$T(n) = T(n-1) + \Theta(n)$ becomes$\Theta(n^2)$ by repeated substitution. -
$T(n) = T(n-1) + T(n-2) + 1$ becomes$\Theta(\phi^n)$ by solving the characteristic polynomial. -
$T(n) = T(n/5) + T(7n/10) + n$ becomes$\Theta(n)$ by induction and a geometric series.
The Master Theorem is the key tool for analyzing the divide-and-conquer algorithms of Week 4.
| Technique | English Name | Key Idea | Representative Examples |
|---|---|---|---|
| Divide and conquer | Divide and Conquer | Divide, conquer, and combine. | Merge sort, quick sort, binary search |
| Greedy algorithm | Greedy | Choose the local optimum at each step. | Dijkstra, Huffman, MST |
| Dynamic programming | Dynamic Programming | Store subproblem results and reuse them. | LCS, knapsack, edit distance |
| Approximation algorithm | Approximation | Find approximate solutions to NP-hard problems. | TSP approximation |
| Backtracking | Backtracking | Add pruning to exhaustive search. | N-Queen |
| Branch and bound | Branch and Bound | Add bounds to backtracking to reduce the search. | Exact TSP |
Table 10. Six techniques of algorithm design
Of these, the three core techniques this course focuses on are divide and conquer (Week 4), greedy (Week 5), and dynamic programming (Week 6).
The big picture of Week 2 is as follows. To compare algorithms independently of hardware, the operation count is expressed as a function of the input
| Operation | Array | Linked List |
|---|---|---|
| Index access | O(1) | O(n) |
| Insertion/deletion in the middle | O(n) | O(1) (if the position is known) |
| Memory | Contiguous (cache-friendly) | Scattered (pointer overhead) |
| Resizing | Amortized O(1) with a dynamic array | Naturally flexible |
Table 11. Operation-by-operation comparison of arrays and linked lists
LIFO (Last In, First Out) describes a data structure in which the most recently inserted element comes out first.
┌─────┐
│ C │ ← top (push / pop)
├─────┤
│ B │
├─────┤
│ A │ ← bottom
└─────┘
Figure 2. Top and bottom of a stack
Operations: push, pop, peek, and isEmpty are all
Practical uses: The function call stack, bracket matching (({[]})), Undo (Ctrl+Z) in editors, DFS implementation, and expression evaluation (infix → postfix conversion).
FIFO (First In, First Out) describes a data structure in which the earliest inserted element comes out first.
dequeue ←── [ A | B | C | D ] ←── enqueue
front rear
Figure 3. Front and rear of a queue and the enqueue and dequeue directions
Practical uses: Breadth-first search (BFS), printer queues, CPU scheduling, and message queues (Kafka, RabbitMQ).
A heap is a complete binary tree that satisfies the heap property.
- In a max-heap, each parent key is greater than or equal to its child keys, and the maximum is at the root.
- In a min-heap, each parent key is less than or equal to its child keys, and the minimum is at the root.
Array representation (1-indexed):
- The left child of node
$i$ is$A[2i]$ . - The right child of node
$i$ is$A[2i+1]$ . - The parent of node
$i$ is$A[\lfloor i/2 \rfloor]$ .
Operation complexity:
-
insert(x)andextractMin/Maxare each$O(\log n)$ . -
getMin/Maxis$O(1)$ . -
buildHeapis$O(n)$ . Intuitively it seems to be$O(n \log n)$ , but a tight analysis that accounts for most nodes having small height and thus small heapify cost (leaves need no heapify at all) reduces it to$O(n)$ .
Practical uses: It is the foundation of priority queues, heap sort, Dijkstra's algorithm, and Huffman coding.
All three sorts in this section follow the recurrence
In each round, this sort finds the maximum (or minimum) of the remaining part and sends it to its correct position.
selectionSort(A[], n):
for last = n downto 2:
k = index of the maximum in A[1..last]
swap A[k] ↔ A[last]
Characteristics: The best, average, and worst cases are all
This sort compares two adjacent elements and swaps them if they are out of order. Large elements are pushed toward the end like rising bubbles.
bubbleSort(A[], n):
for last = n downto 2:
for i = 1 to last-1:
if A[i] > A[i+1]:
swap A[i] ↔ A[i+1]
Optimization: With a swapped flag, if no swap occurs during a pass, the array is already sorted, so the algorithm terminates early. This achieves
Characteristics: The worst and average cases are A[i] > A[i+1], it is a stable sort, and it is in place.
Like sorting the cards in your hand during a card game, this sort inserts each new element into its correct position in the already sorted part.
insertionSort(A[], n):
for i = 2 to n:
key = A[i]
j = i - 1
while j ≥ 1 and A[j] > key:
A[j+1] = A[j] # shift right
j = j - 1
A[j+1] = key # insert at the correct position
Example: For [29, 10, 14, 37, 13], it proceeds as follows.
- Inserting
10gives[10, 29 | 14, 37, 13]. - Inserting
14gives[10, 14, 29 | 37, 13]. - Inserting
37gives[10, 14, 29, 37 | 13]. - Inserting
13gives[10, 13, 14, 29, 37].
Complexity:
| Case | Number of Comparisons | Result |
|---|---|---|
| Worst (reverse-sorted input) | ||
| Average | ||
| Best (already sorted input) |
Table 12. Number of comparisons of insertion sort in each case
Characteristics: It is both stable and in place. It is very fast in practice on small, nearly sorted data, so it serves as the internal base case of practical sorts such as Timsort.
All three algorithms follow the recurrence
Divide-and-conquer strategy: Split the array in half, sort each half recursively, and then merge the two sorted subarrays.
mergeSort(A, p, r):
if p < r:
q = ⌊(p+r)/2⌋
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
Merge procedure: Compare the heads of the two sorted subarrays, copy the smaller one to the result array, and advance the corresponding pointer; the total cost is
Example: For the array [31, 3, 65, 73, 8, 11, 20, 29, 48, 15], it proceeds as follows.
Divide:
[31, 3, 65, 73, 8] [11, 20, 29, 48, 15]
↓ recurse ↓ recurse
[3, 8, 31, 65, 73] [11, 15, 20, 29, 48]
↓ merge
[3, 8, 11, 15, 20, 29, 31, 48, 65, 73]
Figure 4. Splitting, recursive sorting, and merging in merge sort
Characteristics: Performance is guaranteed at
Quick sort is an inverted form of divide and conquer: the split (partition) is the hard part, while the merge step is trivial.
quickSort(A, p, r):
if p < r:
q = partition(A, p, r)
quickSort(A, p, q-1)
quickSort(A, q+1, r)
partition(A, p, r): # Lomuto partition
pivot = A[r]
i = p - 1
for j = p to r-1:
if A[j] ≤ pivot:
i = i + 1
swap A[i] ↔ A[j]
swap A[i+1] ↔ A[r]
return i + 1
Partition invariant: The following three conditions hold during the partition loop.
- Every element of
$A[p \ldots i]$ is at most the pivot. - Every element of
$A[i+1 \ldots j-1]$ is greater than the pivot. -
$A[j \ldots r-1]$ is the region not yet examined.
Complexity:
| Case | Split Shape | Complexity |
|---|---|---|
| Worst | 0 : n-1 (bad pivot on sorted input) | |
| Average | Random pivot | |
| Best | Perfect middle split |
Table 13. Complexity of quick sort by split shape
Why even a 1:9 imbalance gives
Avoiding the worst case:
- Random pivot: Choose a random index, swap it with the last element, and then partition.
- Median-of-3: Use the median of the first, middle, and last elements as the pivot.
- Introsort: Switch to heap sort when the recursion depth exceeds a certain level (used by
std::sortin the C++ STL).
Characteristics: It is unstable but in place, and it needs a recursion stack of about
This sort turns the whole array into a max-heap with buildHeap and then repeatedly moves the root (the maximum) to the end.
heapSort(A, n):
buildHeap(A, n) # O(n)
for i = n downto 2:
swap A[1] ↔ A[i]
heapify(A, 1, i-1) # O(log i)
Explanation: First, turn the whole array into a max-heap. Then swap the root (the maximum) to the end of the array to add it to the finalized region, and restore the heap property of the heap that has shrunk by one (1..i-1) with heapify. Repeating this places the large values one after another from the end toward the front, completing an array in ascending order. It works in place without extra memory.
Why buildHeap is
Characteristics: It guarantees
| Property | Merge Sort | Quick Sort | Heap Sort |
|---|---|---|---|
| Worst | |||
| Average | |||
| Space | |||
| Stable | Yes | No | No |
| Cache | Good | Very good | Poor |
| Practical speed | Fast | Fastest | Moderate |
Table 14. Properties of merge sort, quick sort, and heap sort
Selection guide:
- If stability is required, use merge sort.
- If memory is constrained and a worst-case guarantee is needed, use heap sort.
- If the fastest sort is needed in general, use quick sort with a random pivot.
Theorem: Any comparison-based sort needs
Proof sketch (decision tree model):
- There must be
$n!$ leaves corresponding to the$n!$ possible permutations. - A binary decision tree of height
$h$ has at most$2^h$ leaves. - Therefore
$h \geq \log_2(n!) = \Theta(n \log n)$ (by Stirling's approximation).
A sort that uses only comparisons can never break this lower bound. Counting sort and radix sort use additional information, such as the range of values or the digits, instead of comparisons, so they can bypass this lower bound.
When values lie in the range
countingSort(A, n, k):
C[0..k] = 0
for j = 1 to n: C[A[j]] += 1 # occurrence count
for i = 1 to k: C[i] += C[i-1] # prefix sum
for j = n downto 1: # reverse traversal (stability)
B[C[A[j]]] = A[j]
C[A[j]] -= 1
Explanation: (1) After counting how many times each value C[v] the total number of elements at most B[C[A[j]]], and decrements C by one. Sorting is completed only with information about the range of integer values, without comparisons, giving
Why reverse traversal guarantees stability: Among elements with the same value, the one that came later is placed later in the result array, so the input order is preserved. Traversing from the front reverses that order and makes the sort unstable.
This method repeats a stable sort (usually counting sort) digit by digit and must proceed from the least significant digit (LSD) to the most significant digit (MSD).
radixSort(A, d):
for digit = 1 to d:
A = stable_sort_by_digit(A, digit)
Explanation: It sorts
Proceeding in LSD order is what lets the order from the previous digits survive, thanks to the stable sort.
Complexity:
The big picture of Week 3 is as follows. Data structures (arrays, linked lists, stacks, queues, heaps) are the tools that algorithms use. Sorts divide into
Three steps:
- Divide: Split the problem into smaller subproblems.
- Conquer: Solve each subproblem recursively.
- Combine: Merge the subsolutions into a solution of the original problem.
Required condition: The subproblems must be independent of each other. If the subproblems overlap, DP must be used instead of divide and conquer.
Typical recurrence: It has the form
| Algorithm | Divide | Conquer | Combine | Recurrence | Time |
|---|---|---|---|---|---|
| Merge sort | Split in half | Sort each half | Merge | ||
| Binary search | Compare with middle | Recurse on one side only | Trivial | ||
| Quick sort (average) | Partition | Recurse on both sides | Trivial | ||
| Quick sort (worst) | Unbalanced | - | - | ||
| Randomized select | Partition | One side only | Trivial | Average |
|
| Median of medians | Groups of 5 | Both | Partition | Worst |
|
| Closest pair | Split by x | Each half | Strip |
Table 15. Steps, recurrences, and time complexities of representative divide-and-conquer algorithms
Problem definition: Find the
select(A, p, r, i):
if p == r: return A[p]
q = partition(A, p, r) # partition from quick sort
k = q - p + 1
if i == k: return A[q]
elif i < k: return select(A, p, q-1, i)
else: return select(A, q+1, r, i-k)
Explanation: It reuses quick sort's partition to place the pivot in its final position and finds its rank
Unlike quick sort, it makes a recursive call on only one side rather than both, so it is much faster on average.
Analysis: On average the problem size shrinks to at most
Expanding it as a geometric series gives
as the result.
Idea: A method that always guarantees a balanced pivot.
- Divide the elements into groups of 5, forming
$\lceil n/5 \rceil$ groups. - Find the median of each group.
- Recursively find the median
$M$ of those medians. - Partition with
$M$ as the pivot. - Recurse on the desired side.
Guarantee: At least
Recurrence:
Why groups of 5: With groups of 3,
Problem definition: Among
Brute force: Checking every pair takes
Divide-and-conquer strategy:
- Sort the points by x-coordinate (preprocessing in $O(n \log n)$).
- Split into left and right around the median x.
- Recurse on each half to obtain
$d_L, d_R$ . - Set
$d = \min(d_L, d_R)$ . - Form a strip of the points within
$d$ of the dividing line, and check whether any pair spanning the two halves is closer than$d$ .
Geometric property of the strip: A
Complexity: The recurrence
Implementing Fibonacci with naive recursion looks as follows.
def fib(n):
if n <= 2: return 1
return fib(n-1) + fib(n-2)The recurrence is
Cause: The cause lies in overlapping subproblems, where the same subproblem is computed again and again. For example,
Solution: Such problems are solved with DP (Week 6).
Distinguishing divide and conquer from DP:
- If the subproblems are independent, use divide and conquer.
- If the subproblems overlap, DP must be used.
The big picture of Week 4 is as follows. Divide and conquer is the paradigm that recursively solves independent subproblems and combines the results. Representative algorithms include merge sort ($\Theta(n \log n)$), binary search ($\Theta(\log n)$), quick sort (average $\Theta(n \log n)$), randomized select ($\Theta(n)$), median of medians (worst-case $\Theta(n)$), and closest pair ($O(n \log^2 n)$). Problems with overlapping subproblems, such as Fibonacci, are solved with DP.
A greedy algorithm makes, at each step, the choice that looks best right now (the local optimum). It never undoes a choice once made and does not backtrack.
Greedy(C):
S = {}
while C is not empty and S is incomplete:
x = the most promising element of C
C = C - {x}
if S ∪ {x} is feasible:
S = S ∪ {x}
return S
Explanation: This is the general greedy framework. It takes elements
For a greedy algorithm to guarantee an optimal solution, both of the following conditions must hold.
- Greedy-choice property: Some optimal solution includes the greedy choice. The standard technique for proving this is the exchange argument: show that replacing a non-greedy choice in an optimal solution with the greedy choice preserves optimality.
- Optimal substructure: After making the greedy choice, the optimal solution of the remaining subproblem becomes part of the overall optimal solution.
Practical principle: Try greedy first, and switch to DP if a counterexample appears.
| Problem | Greedy Choice | Result | Optimal Solution |
|---|---|---|---|
| Coins {1, 3, 4}, amount 6 | 4 + 1 + 1 = 3 coins | Fails | 3 + 3 = 2 coins |
| Coins {16, 10, 5, 1}, amount 20 | 16 + 1 + 1 + 1 + 1 = 5 coins | Fails | 10 + 10 = 2 coins |
| 0-1 knapsack (sorted by value/weight) | Choose the highest ratio first | Wasted capacity | DP required |
| Maximum path sum in a binary tree | Move to the larger child | Reaches only a local optimum | Misses the global optimum |
Table 16. Cases where a greedy algorithm fails to produce an optimal solution
For standard currencies such as the Korean won (500, 100, 50, 10), each denomination is a multiple of the next smaller one, so greedy is optimal; for non-standard denomination sets, always suspect a counterexample.
The simple rule is to choose the largest denomination first, and for a standard currency it obtains the optimal solution in
The knapsack problem in which items can be divided has an optimal greedy solution.
Strategy: Sort the items in descending order of value per unit weight (
FractionalKnapsack(items, C):
compute v/w of each item, sort in descending order
remaining capacity w = C
for each item x (in sorted order):
if w ≥ x.weight: take all of it
else: take the fraction that fits the remaining capacity
Example: With capacity 40 and the items platinum (10kg, $60), gold (15kg, $75), silver (25kg, $10), and tin (20kg, $2), the ratios are 6, 5, 0.4, and 0.1.
| Order | Item | Action | Cumulative Value |
|---|---|---|---|
| 1 | Platinum (10kg) | Take all of it | $60 |
| 2 | Gold (15kg) | Take all of it | $135 |
| 3 | Silver (25kg) | Take only 0.6 to fill the remaining capacity | $141 |
Table 17. Greedy selection steps for a fractional knapsack of capacity 40
Time complexity: The sorting step dominates, giving
When items cannot be divided, as in the 0-1 knapsack, greedy fails and DP must be used.
Problem definition: Select the maximum number of mutually non-overlapping activities on one machine.
Greedy strategy: Select activities starting from the one with the earliest finish time (EFT).
ActivitySelection(jobs):
sort by finish time in ascending order
selected = {first activity}
last_finish = finish time of the first activity
for each remaining j:
if j.start ≥ last_finish:
selected += {j}
last_finish = j.finish
return selected
Explanation: After sorting by finish time, it traverses the activities and selects only those whose start time is at or after the finish time of the last selected activity (last_finish). Each time it selects one, it updates last_finish. Sorting in
Why EFT: Choosing the activity that finishes earliest leaves the most time for the remaining activities.
Exchange argument proof: Compare an optimal solution
Problem definition: Perform all jobs while minimizing the number of machines used.
Greedy strategy: Assign jobs starting from the one with the earliest start time (EST).
Distinguishing it from activity selection:
| Aspect | Job Scheduling | Activity Selection |
|---|---|---|
| Goal | Minimize the number of machines | Maximize the number of activities |
| Greedy criterion | EST (start time) | EFT (finish time) |
Table 18. Goals and greedy criteria of job scheduling and activity selection
Problem definition: Compress a file by assigning variable-length binary codes based on character frequencies.
Prefix property: No code is a prefix of another code. Thanks to this property, decoding is possible without separators.
Algorithm outline: Repeatedly merge the two lowest-frequency nodes from a min-heap keyed by frequency.
Huffman(C):
Q = min-heap keyed by frequency (leaf = each character)
while |Q| ≥ 2:
A = extract-min(Q)
B = extract-min(Q)
N = new node with freq = A.freq + B.freq
N.left = A, N.right = B
insert(Q, N)
return the root of Q
Explanation: From a min-heap whose leaf nodes are the characters, it extracts the two lowest-frequency nodes, makes a new internal node with their combined frequency, and puts it back into the heap. Nodes merged early (the lower-frequency ones) sit deep in the tree and get long codes, while the rest get short codes. After
Example: With character frequencies A:450, T:90, G:120, C:270, the tree is built as follows.
- Merge T(90) and G(120), the two lowest frequencies, into a new node of frequency 210.
- Merge the next lowest, 210 and C(270), into a node of frequency 480.
- Finally, merge A(450) and 480 to complete the root of frequency 930.
Assigned codes:
- A is
0(1 bit) - C is
10(2 bits) - T is
110(3 bits) - G is
111(3 bits)
Bit count:
Complexity: It performs
Proof of optimality: It is proved with an exchange argument. The key point is that even in an optimal tree, the two lowest-frequency characters must be sibling leaves sharing the same parent.
Problem definition: In a connected weighted graph, find the tree (
KruskalMST(G):
sort edges by weight in ascending order
T = {}
initialize Union-Find
for each edge (u, v) (ascending):
if find(u) ≠ find(v): # no cycle
T += {(u, v)}
union(u, v)
return T
Explanation: This is an edge-centric approach. After sorting all edges by weight in ascending order, it examines them in order and adds an edge to the tree if it does not create a cycle. The cycle check uses Union-Find's find to see whether the two endpoints already belong to the same connected component. When an edge is added, union merges the two components. Selecting
Data structure: It uses Union-Find, which handles cycle detection in nearly constant time,
Complexity: Sorting dominates, giving
Best suited for: Sparse graphs with few edges.
PrimMST(G, s):
D[v] = ∞ for all v; D[s] = 0
T = {s}
while |T| < n:
u = vertex outside T with the minimum D[u]
T += {u}
for each neighbor v of u (v ∉ T):
if weight(u,v) < D[v]:
D[v] = weight(u,v)
parent[v] = u
return the MST edges
Explanation: This is a vertex-centric approach. Starting from the start vertex
Data structure: It uses a priority queue.
Complexity:
Best suited for: Dense graphs with many edges.
| Aspect | Kruskal | Prim |
|---|---|---|
| Approach | Edge-centric | Vertex-centric |
| Data structure | Union-Find | Priority queue |
| Complexity |
|
|
| Suitable graph | Sparse | Dense |
| Construction | Several forests merge into a tree | One tree grows gradually |
Table 19. Comparison of Kruskal's and Prim's algorithms
Problem definition: Find the shortest paths from a source vertex
Algorithm:
Dijkstra(G, s):
D[v] = ∞; D[s] = 0; S = {}
while S ≠ V:
u = vertex outside S with the minimum D[u]
S += {u}
for each neighbor v of u (v ∉ S): # edge relaxation (Relax)
if D[u] + w(u,v) < D[v]:
D[v] = D[u] + w(u,v)
parent[v] = u
Explanation: It maintains the shortest distances
Greedy invariant: If
Why it fails with negative edges: Dijkstra assumes that a finalized
Similarity to Prim's algorithm:
| Aspect | Prim | Dijkstra |
|---|---|---|
| Invariant |
|
|
| Meaning of |
The minimum weight of an edge connecting |
The shortest distance from the source |
| Operation pattern | Extract minimum → extend tree → update neighbors | Extract minimum → finalize distance → relax edges |
Table 20. Invariants and operation patterns of Prim's and Dijkstra's algorithms
They are structurally almost identical; the only difference is what updating the neighbors means.
The big picture of Week 5 is as follows. A greedy algorithm chooses the local optimum at each step. Correctness requires both the greedy-choice property (proved with an exchange argument) and optimal substructure. Representative algorithms are activity selection (EFT), the fractional knapsack (value/weight ratio), Huffman coding (merging the lowest frequencies), the MST algorithms of Kruskal and Prim, and Dijkstra's shortest paths. Coin change (arbitrary denominations) and the 0-1 knapsack, where greedy fails, must be solved with DP.
Dynamic programming (DP) is a technique that reduces exponential recursion to polynomial time by solving each overlapping subproblem only once, storing the result, and reusing it.
The term "programming" refers not to computer programming but to mathematical tabulation (tabular optimization); Richard Bellman introduced the term in the 1950s.
- Optimal substructure: The overall optimal solution consists of optimal solutions to subproblems.
- Overlapping subproblems: The same subproblem is computed repeatedly in the recursive structure.
Comparing these two conditions with those of the other paradigms gives the following.
- Divide and conquer needs only optimal substructure, and its subproblems must be independent.
- Greedy needs both optimal substructure and the greedy-choice property.
- DP is used when optimal substructure and overlapping subproblems are both present.
This approach combines recursive calls with a cache, and the call structure naturally explores the subproblems in the shape of a DAG.
def fib_memo(n, memo=None):
if memo is None: memo = {}
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]Explanation: It keeps the recursive structure and adds a cache (the dictionary memo). Each call to fib_memo(k) first looks up the cache: if the value is there, it returns immediately; otherwise it computes the value recursively and stores it. As a result, each value of
Advantages: It computes only the subproblems that are actually needed, and the implementation is intuitive.
Disadvantages: It has recursive call stack overhead and may hit the depth limit.
This approach fills the table in order with a loop, starting from the base cases.
def fib_tab(n):
if n <= 1: return n
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Explanation: Without recursion, it fills
Advantages: There is no recursion overhead, sequential array access gives good cache efficiency, and it runs fast in practice.
Disadvantages: It must compute every subproblem, and the computation order must be determined explicitly.
| Memoization | Tabulation | |
|---|---|---|
| Direction | Top-down (large → small) | Bottom-up (small → large) |
| Implementation | Recursion + cache | Loop |
| Subproblems | Only those needed (lazy) | All computed |
| Overhead | Recursion stack, lookups | Tight loop |
| In practice | Easier | Faster |
Table 21. Comparison of memoization and tabulation
Approach every DP problem with the following six steps.
- Define the subproblem: Decide exactly what
dp[i, j, ...]means. - Write the recurrence: Decide how to express the subproblem in terms of smaller subproblems.
- Identify the base cases: Decide the boundary values at which the recursion ends trivially.
- Determine the computation order: Decide the order of solving subproblems so that dependencies are satisfied.
- Extract the answer: Identify which cell of the table stores the final answer.
- (Optional) Backtrack: If the actual solution, not just its value, must be recovered, design the backtracking path.
Subproblem:
Recurrence:
Complexity:
Measured comparison (
| Method | Time |
|---|---|
| Naive recursion | About 150 ms, |
| Memoization | About 0.005 ms, |
| Tabulation | About 0.003 ms, |
Table 22. Running time for
Problem definition: Find the longest common subsequence of two strings
Subsequence vs substring: A subsequence need not be contiguous. For example, the LCS of "ABCBDAB" and "BDCABA" is "BCAB" (length 4).
Subproblem:
Recurrence: $$ c[i,j] = \begin{cases} 0 & i = 0 \text{ or } j = 0 \ c[i-1, j-1] + 1 & X[i] = Y[j] \ \max(c[i-1, j], c[i, j-1]) & X[i] \neq Y[j] \end{cases} $$
Example: The DP table for ABCBDAB and BDCAB is as follows.
"" B D C A B
"" 0 0 0 0 0 0
A 0 0 0 0 1 1
B 0 1 1 1 1 2
C 0 1 1 2 2 2
B 0 1 1 2 2 3
D 0 1 2 2 2 3
A 0 1 2 2 3 3
B 0 1 2 2 3 4
Figure 5. LCS DP table for ABCBDAB and BDCAB
How to read the table: Rows represent prefixes of A, AB, ABC, and so on), and columns represent prefixes of B, BD, and so on). Each cell is the LCS length of the two corresponding prefixes. Row 0 and column 0 correspond to the empty string, so their values are 0. Interior cells are filled by referring to the upper-left, left, and upper cells according to the recurrence, and the bottom-right corner cell is the final answer.
Answer: BCAB.
Backtracking: Starting from
Complexity: Both time and space are
Applications: Git diff, DNA sequence alignment, and variants of the edit distance problem.
Problem definition: Find the minimum number of operations to transform string
Subproblem:
Recurrence: $$ E[i,j] = \begin{cases} j & i = 0 \quad (\text{insert j}) \ i & j = 0 \quad (\text{delete i}) \ E[i-1, j-1] & X[i] = Y[j] \ 1 + \min(E[i-1, j], E[i, j-1], E[i-1, j-1]) & \text{else} \end{cases} $$
-
$E[i-1, j] + 1$ denotes a deletion. -
$E[i, j-1] + 1$ denotes an insertion. -
$E[i-1, j-1] + 1$ denotes a substitution.
Example: The edit distance from kitten to sitting can be found with the following table.
"" s i t t i n g
"" 0 1 2 3 4 5 6 7
k 1 1 2 3 4 5 6 7
i 2 2 1 2 3 4 5 6
t 3 3 2 1 2 3 4 5
t 4 4 3 2 1 2 3 4
e 5 5 4 3 2 2 3 4
n 6 6 5 4 3 3 2 3
Figure 6. Edit distance DP table for turning kitten into sitting
How to read the table: Rows represent prefixes of kitten), and columns represent prefixes of sitting). Each cell is the edit distance between the two prefixes. The value
Answer:
Complexity: Both time and space are
Problem definition: Given
Subproblem:
Recurrence: $$ K[i, w] = \begin{cases} 0 & i = 0 \text{ or } w = 0 \ K[i-1, w] & w_i > w \ \max(K[i-1, w], K[i-1, w - w_i] + v_i) & \text{else} \end{cases} $$
Decision: For each item, decide whether to include it in the knapsack or exclude it.
Example: With items (weight, value)
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 12 12 12 12
2 0 10 12 22 22 22
3 0 10 12 22 30 32
4 0 10 15 25 30 37
Figure 7. DP table of a 0-1 knapsack with capacity 5
How to read the table: Row
Answer:
Backtracking: If
Complexity:
Space optimization: Since the recurrence refers only to the previous row
Why greedy fails: Taking items in descending order of value/weight ratio can leave capacity unused while the next item no longer fits. DP explores all partial solutions, so it handles such cases correctly.
Problem definition: Given coin denominations
Subproblem:
Recurrence:
Example: With denominations
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 1 | 1 | 2 | 2 |
Table 23. Minimum number of coins for each amount with denominations {1, 3, 4}
Comparison with greedy: Greedy chooses 4 + 1 + 1 = 3 coins, but DP finds the optimal solution 3 + 3 = 2 coins.
Complexity:
Problem definition: Given a weighted directed graph, find the shortest distance between every pair of vertices.
Subproblem:
Recurrence:
Implementation (without a 3D array, to save space):
FloydWarshall(W, n):
D = W # copy the adjacency matrix
for k = 1 to n: # [Caution] k must be outermost!
for i = 1 to n:
for j = 1 to n:
D[i,j] = min(D[i,j], D[i,k] + D[k,j])
return D
Explanation:
Loop order:
Complexity:
Negative edges: Negative edges are allowed as long as there is no negative cycle. A negative cycle can be detected by a diagonal entry
Subproblem:
Recurrence:
Complexity: Both time and space are
| Problem | Subproblem | Recurrence | Time | Space |
|---|---|---|---|---|
| Fibonacci | ||||
| Matrix path | ||||
| LCS | Branch on match/mismatch | |||
| Edit distance | min of insert, delete, substitute | |||
| 0-1 knapsack | max of include/exclude | |||
| Coins (minimum) | ||||
| Floyd-Warshall | With/without intermediate vertex |
Table 24. Subproblems, recurrences, and complexities of representative DP problems
Big picture: DP is a technique that uses optimal substructure and overlapping subproblems to reduce exponential-time recursion to polynomial time. The standard six-step recipe is: define the subproblem, derive the recurrence, set the base cases, determine the computation order, extract the answer, and backtrack. Master the seven classic problems: Fibonacci, matrix path, LCS, edit distance, 0-1 knapsack, coin change, and Floyd-Warshall.
graph TD
ps["Problem solving"] <--> dc["Divide and conquer"]
dc <--> rt["Recursive thinking"]
rt <--> rec["Recurrences"]
dc <--> pc["Paradigm choice (Greedy / DP / D&C)"]
Figure 8. The flow of concepts running through the whole semester
Every algorithm shares recursive thinking that goes from a large problem → smaller problems → a combination. The differences between paradigms arise from whether the subproblems are independent and from the details of how the subproblems are defined.
| Algorithm | Worst | Average | Best | Space | Stable | In Place |
|---|---|---|---|---|---|---|
| Selection | ✗ | ✓ | ||||
| Bubble | ✓ | ✓ | ||||
| Insertion | ✓ | ✓ | ||||
| Merge | ✓ | ✗ | ||||
| Quick | ✗ | ✓ | ||||
| Heap | ✗ | ✓ | ||||
| Counting | ✓ | ✗ | ||||
| Radix | ✓ | ✗ |
Table 25. Complexity, space, stability, and in-place property of each sorting algorithm
|
|
Result |
|---|---|
|
|
|
|
|
|
|
|
|
Table 26. Results of comparing
| Recurrence | Solution | Example |
|---|---|---|
| Binary search | ||
| Factorial | ||
| Merge sort | ||
| - | ||
| Insertion sort, quick sort worst case | ||
| Tower of Hanoi | ||
| Naive recursive Fibonacci |
Table 27. Common recurrences and their solutions
-
LCS:
$c[i-1, j-1] + 1$ on a match,$\max(c[i-1, j], c[i, j-1])$ on a mismatch -
Edit distance:
$E[i-1, j-1]$ on a match,$1 + \min$ (three directions) on a mismatch -
0-1 knapsack:
$\max(K[i-1, w], v_i + K[i-1, w - w_i])$ -
Matrix path:
$m[i,j] + \max(c[i-1,j], c[i,j-1])$ -
Coin change:
$1 + \min_{d_i \leq j} C[j - d_i]$ -
Floyd-Warshall:
$\min(d[i,j], d[i,k] + d[k,j])$ (k in the outer loop)
| Mistake | Prevention |
|---|---|
| Confusing O vs Ω vs Θ | Memorize the definitions; distinguish one-sided from two-sided bounds |
| Loose Big-O | Always be tight (use Θ when needed) |
| Claiming greedy without proof | Search for a counterexample → if none, use an exchange argument |
| Wrong DP base case | Verify n=0,1,2 by hand |
| Off-by-one in the DP table | State 0-index vs 1-index explicitly |
| Fractional vs 0-1 knapsack | Divisible = greedy, indivisible = DP |
| Quick sort on sorted input | Random or median-of-3 pivot |
| Floyd-Warshall loop order | k must be outermost |
| Dijkstra + negative edges | Replace with Bellman-Ford |
| Induction: |
Strengthen the guess: |
| Omitting merge sort's space | State the |
Table 28. Common mistakes and how to prevent them
| Aspect | Divide and Conquer | Greedy | DP |
|---|---|---|---|
| Subproblems | Independent (tree) | N/A | Overlapping (DAG) |
| Approach | Divide → conquer → combine | Choose the local optimum | Store and reuse subproblem results |
| Direction | Recursive (top-down) | Sequential | Bottom-up or memoization |
| Optimality guarantee | Problem-dependent | Requires the greedy-choice property | ✓ (optimal substructure) |
| Time | Typically |
|
|
| Space |
|
|
|
| Representative | Merge, quick, binary search | Dijkstra, Huffman, MST | LCS, edit distance, knapsack, FW |
Table 29. Aspect-by-aspect comparison of divide and conquer, greedy, and DP
flowchart TD
q1{"Does the problem ask for an optimal value?"} -->|"No"| dc1["D&C (sorting, searching, k-th element, etc.)"]
q1 -->|"Yes"| q2{"Can a safe greedy choice be proved?"}
q2 -->|"Yes"| gr["Greedy"]
q2 -->|"No"| q3{"Do subproblems overlap?"}
q3 -->|"Yes"| dp["DP"]
q3 -->|"No"| dc2["D&C"]
Figure 9. Flowchart for choosing a paradigm from the properties of a problem
| Problem | Greedy | DP | D&C |
|---|---|---|---|
| Coin change (standard) | ✓ | ✓ | - |
| Coin change (arbitrary) | ✗ | ✓ | - |
| Fractional knapsack | ✓ | ✓ | - |
| 0-1 knapsack | ✗ | ✓ | - |
| Shortest path (weights ≥ 0) | ✓ Dijkstra | ✓ | - |
| Shortest path (negative weights allowed) | - | ✓ Bellman-Ford, FW | - |
| Sorting | - | - | ✓ |
| k-th element | - | - | ✓ Select |
| MST | ✓ | - | - |
| LCS / edit distance | ✗ | ✓ | - |
Table 30. Paradigms applicable to each problem
The Euclidean GCD (Week 1), merge sort (Week 4), and DP (Week 6) all share the structure of reducing a problem to smaller problems. Recursion is the basso continuo that runs through the whole course.
Binary search (Week 1), the counterfeit coin problem (Week 1), and merge sort (Week 4) all split the problem in half, and the total complexity is determined by
For coin change with arbitrary denominations and for the 0-1 knapsack, greedy fails, so one must switch to DP. This switch teaches the lesson of moving from recognizing a counterexample to a generalized solution.
The comparison-based
All three algorithms share the common pattern extract minimum → finalize → update neighbors. In other words, they stand on the same skeleton: a greedy framework based on a priority queue.
Divide and conquer handles independent subproblems, and DP handles overlapping ones. The
Big-O, recurrences, and the Master Theorem (Week 2) are the tools for analyzing every algorithm from Week 3 through Week 7. Without the language of complexity, one cannot explain why one algorithm is better than another.
✗ "LCS is solved with DP."
✓ "LCS has two choices, depending on whether
✗ "Quick sort is fast."
✓ "Quick sort averages
✗ "Prim finds an MST."
✓ "Prim is structurally identical to Dijkstra: both repeat extracting the minimum and updating neighbors. The only difference is the meaning of
✗ "Dijkstra finds shortest paths."
✓ "Dijkstra works only with non-negative edges. With negative edges, a finalized
✗ "LCS is O(mn)."
✓ "LCS underlies Git diff and is also used for DNA sequence alignment. It finds the common lines of two files and marks changes, additions, and deletions. If
This table collects, week by week, the core information that must be found fastest during the exam.
| Week | Topic | Core Algorithms | Complexity |
|---|---|---|---|
| Week 2 | Complexity | Big-O, loop analysis | - |
| Week 3 | Sorting | Merge sort, quick sort, heap sort | |
| Week 4 | Divide and conquer | Binary search, closest pair, selection |
|
| Week 5 | Greedy | Activity selection, Huffman, fractional knapsack, MST, Dijkstra | |
| Week 6 | DP | Fibonacci, LCS, 0-1 knapsack, edit distance, Floyd-Warshall |
|
Table 31. Topics, core algorithms, and complexities by week
1. Complexity: notice the i *= 2 (log n) vs i += 1 (n) pattern
2. Sorting: memorize each sort's time/space complexity AND stability
3. D&C: write the recurrence first → apply the Master Theorem
4. Greedy: explain "why" the greedy-choice property holds
5. DP: subproblem definition → recurrence → base case → fill order
| Mistake | How to Avoid It |
|---|---|
| Confusing O, Ω, Θ | O = upper bound, Ω = lower bound, Θ = tight two-sided bound |
| Applying the Master Theorem when f(n) is not polynomial | Check the regularity condition; if it fails, use another method |
| Claiming greedy is optimal without proof | Always look for a counterexample first |
| Wrong base case in a DP recurrence | Verify by tracing small inputs (n=1, 2, 3) |
| Off-by-one errors in a DP table | State explicitly whether it is 0-indexed or 1-indexed |
| Confusing fractional vs 0-1 knapsack | Fractional = greedy, 0-1 = DP |
| Overlooking quick sort's worst case ( |
Avoid it with a random pivot or median-of-3 |
Table 32. Common exam mistakes and how to avoid them
The following are three representative exam question types.
Problem: Find the time complexity of the following recurrence with the Master Theorem.
Solution:
-
$a = 4$ ,$b = 2$ ,$f(n) = n$ $n^{\log_b a} = n^{\log_2 4} = n^2$ - Compare
$f(n) = n$ vs$n^2$ -
$f(n) = O(n^{2-\varepsilon})$ ($\varepsilon = 1$ ) → Case 1 -
Answer:
$T(n) = \Theta(n^2)$ .
Problem: With denominations
Greedy solution:
- 4 (remaining: 2), 1 (remaining: 1), 1 (remaining: 0)
- Result:
${4, 1, 1}$ = 3 coins
DP solution:
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| C(j) | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
Table 33. DP table filled up to amount 6 with denominations {1, 3, 4}
$C(6) = 1 + \min(C(5), C(3), C(2)) = 1 + \min(2, 1, 2) = 2$ - Result:
${3, 3}$ = 2 coins
Conclusion: Greedy finds 3 coins and DP finds 2, so greedy is not optimal for these denominations.
Problem: Find the LCS of ABCB and BDCAB with a DP table.
Table:
| "" | B | D | C | A | B | |
|---|---|---|---|---|---|---|
| "" | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 |
| B | 0 | 1 | 1 | 2 | 2 | 3 |
Table 34. LCS DP table for ABCB and BDCAB
Answer: The LCS length is 3, and one LCS is BCB.
Backtracking: When the characters match, move diagonally and include the character; otherwise, move to whichever of the two neighbors has the larger value.
These problems come from Week 7 Lab Exercise 2 and train the ability to decide which paradigm to use for a problem on the exam.
| # | Problem | Paradigm | Reason |
|---|---|---|---|
| 1 | Two Sum (n ≤ 100) | Brute force |
|
| 2 | Maximum subarray sum | DP (Kadane) or D&C | dp[i] = max(a[i], dp[i-1]+a[i]) |
| 3 | Closest pair of points ( |
Divide and conquer | Split by x, recurse on each half, check the strip. |
| 4 | Coin change {1, 5, 7, 10} | DP | Non-standard denominations, so greedy fails |
| 5 | Activity selection | Greedy | Sort by finish time ascending; EFT optimality is proved |
Table 35. Paradigm identification exercises 1-5 and the paradigm for each
Problem 4:
Coins {1, 5, 7, 10}, amount 14
Greedy: 10 + 1 + 1 + 1 + 1 = 5 coins
DP: 7 + 7 = 2 coins ← optimal!
| # | Problem | Paradigm | Reason |
|---|---|---|---|
| 6 | Permutation in String | Brute force (sliding window) | Check every window of length len(s1)
|
| 7 | Longest increasing subsequence (LIS) | DP |
dp[i] = length of the LIS ending at index i |
| 8 | Multiplying large numbers | Divide and conquer (Karatsuba) | Split the digits, 3 multiplications. |
| 9 | Minimum number of meeting rooms | Greedy | Event sweep: start +1, end -1, track the maximum |
| 10 | Edit distance | DP | A 2D table similar to LCS. dp[i][j] = minimum operations for the prefixes |
Table 36. Paradigm identification exercises 6-10 and the paradigm for each
flowchart TD
r["Read the problem"] --> q1{"Small constraints (n ≤ hundreds)?"}
q1 -->|"Yes"| bf["Brute force"]
q1 -->|"No"| q2{"Split into independent subproblems?"}
q2 -->|"Yes"| dc["Divide and conquer"]
q2 -->|"No"| q3{"Local optimum = global optimum?"}
q3 -->|"Yes"| gr["Greedy"]
q3 -->|"No"| q4{"Overlapping subproblems + optimal substructure?"}
q4 --> dp["DP"]
Figure 10. Flowchart for choosing a paradigm from the problem's conditions
Rule of thumb: Try greedy first, and switch to DP if a counterexample is found.
These problems come from Week 7 Lab Exercise 3 and review the core concepts of each week.
Problem: Find the time complexity of the following function and the result of mystery(16).
def mystery(n):
count = 0
i = 1
while i < n: # outer loop
j = 0
while j < n: # inner loop
count += 1
j += 1
i *= 2 # key: i doubles each time
return countSolution:
Outer loop: i = 1, 2, 4, 8, ..., until i ≥ n
i doubles → O(log n) iterations
Inner loop: j = 0, 1, ..., n-1
O(n) iterations per outer iteration
Total: O(n) × O(log n) = O(n log n)
Trace of mystery(16):
i = 1: j over 0..15 → 16 times
i = 2: j over 0..15 → 16 times
i = 4: j over 0..15 → 16 times
i = 8: j over 0..15 → 16 times
i = 16: while condition fails, exit
count = 16 × 4 = 64
Answer: (a)
Key point: The i *= 2 pattern repeats i += 1 pattern repeats
Problem: Implement merge sort and count the number of merge operations.
def merge_sort(arr):
"""Return (sorted array, merge count)."""
if len(arr) <= 1:
return arr[:], 0
mid = len(arr) // 2
left, lc = merge_sort(arr[:mid])
right, rc = merge_sort(arr[mid:])
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= (stability)
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged, lc + rc + 1Explanation: It splits the array into two parts at the midpoint and calls itself recursively. It merges the two returned sorted subarrays with two pointers, adding the smaller of left[i] and right[j] to the result and advancing that pointer. The remaining elements are appended at the end with extend. The merge count is the sum of the left and right merge counts plus 1 for the current merge. It uses <= for stability (the left element goes first when values are equal).
Example: The input [38, 27, 43, 3, 9, 82, 10] is sorted into [3, 9, 10, 27, 38, 43, 82], and the merge count is 6, equal to the number of internal nodes of the recursion tree,
Problem: Find the maximum of an array with divide and conquer and count the comparisons.
def find_max_dc(arr):
"""Return (maximum, comparison count)."""
comparisons = [0]
def helper(a, lo, hi):
if lo == hi:
return a[lo]
mid = (lo + hi) // 2
left_max = helper(a, lo, mid)
right_max = helper(a, mid + 1, hi)
comparisons[0] += 1
return left_max if left_max >= right_max else right_max
return helper(arr, 0, len(arr) - 1), comparisons[0]Explanation: It splits the array in half, recursively finds the maximum of the left and right halves, and returns the larger of the two with one comparison. The base case is a single element (lo == hi). The recurrence
Example: The maximum of [3, 7, 2, 9, 1, 8, 4, 6, 5] is 9, and the total number of comparisons is 8, equal to
Recurrence:
Takeaway: The
Problem: From a list of (start, end) lectures, select the maximum number of lectures that fit in one lecture room.
def activity_selection(lectures):
"""Return (count, list of selected indices)."""
indexed = [(end, start, i) for i, (start, end) in enumerate(lectures)]
indexed.sort() # sort by finish time (EFT)
selected = []
last_end = -1
for end, start, idx in indexed:
if start >= last_end:
selected.append(idx)
last_end = end
return len(selected), selectedExplanation: It converts each lecture into an (end, start, original index) tuple and sorts by finish time (Python sorts tuples by their first element). While traversing, it selects a lecture if its start is at least the previous last_end and updates last_end to the current finish time. The greedy choice of the lecture that ends earliest is optimal because it leaves the most time for the remaining lectures (exchange argument).
Example: For the lecture list [(1,3),(2,5),(3,6),(5,7),(6,8),(8,10),(9,11)], the selected lectures are (1,3) → (3,6) → (6,8) → (8,10), 4 in total. A lecture that starts exactly when the previous one ends does not overlap it (start >= last_end).
Key point: It is a greedy algorithm based on EFT (Earliest Finish Time), and its time complexity is
Problem: There are cost[i]. You climb 1 or 2 stairs at a time, starting from stair 0 or 1. Find the minimum cost to reach the top.
def min_cost_climbing(cost):
n = len(cost)
if n <= 1:
return cost[0] if n == 1 else 0
prev2 = cost[0] # dp[0]
prev1 = cost[1] # dp[1]
for i in range(2, n):
current = cost[i] + min(prev1, prev2)
prev2, prev1 = prev1, current
return min(prev1, prev2) # to the top from the last or second-to-last stairExplanation: prev1, prev2) instead of an array.
Examples:
- The minimum cost for
[10, 15, 20]is 15. - The minimum cost for
[1, 100, 1, 1, 1, 100, 1, 1, 100, 1]is 6.
Recurrence: dp[i] = cost[i] + min(dp[i-1], dp[i-2]).
Complexity:
Generalization: Even in 2D DP, if the recurrence refers only to the previous row or the previous column, the space can be reduced to a 1D array.
- What are the five properties of an algorithm?
- What is the basis for the correctness of the Euclidean GCD algorithm?
- Why is the equality in
left <= rightneeded in binary search? - Why are
$\log_2 n$ servants enough in the poisoned wine problem?
- What is the difference between Big-O, Ω, and Θ?
- What is the RAM model?
- What are the condition and result of each of Cases 1, 2, and 3 of the Master Theorem?
- How do you prove
$T(n) = 2T(n/2) + n$ by induction?
- What are the per-operation complexities of arrays vs linked lists?
- Name three practical uses each for LIFO stacks and FIFO queues.
- What are the parent and child indices in the array representation of a heap?
- Under what condition is insertion sort's best case
$\Theta(n)$ ? - What worst-case scenario makes quick sort
$\Theta(n^2)$ ? - Why is buildHeap
$O(n)$ ? - How is the
$\Omega(n \log n)$ lower bound for comparison-based sorting proved? - Why does counting sort need reverse traversal?
- Why does radix sort use LSD order?
- What are the three steps of divide and conquer?
- Why is merge sort
$\Theta(n \log n)$ even in the worst case? - What is the outline of the proof that randomized select is
$\Theta(n)$ on average? - Why does median of medians use groups of 5?
- Why are 7 neighbors enough in the strip check of the closest pair algorithm?
- What is the difference between the greedy-choice property and optimal substructure?
- What is the difference between activity selection (EFT) and job scheduling (EST)?
- What is the outline of the proof of optimality of Huffman coding?
- How do the data structures of Kruskal and Prim differ?
- Why does Dijkstra fail with negative edges?
- What are the two required conditions of DP?
- What is the difference between memoization and tabulation?
- Why does greedy fail and DP succeed on the 0-1 knapsack?
The solution of
- Since
$a = 7$ and$b = 2$ ,$n^{\log_2 7} \approx n^{2.81}$ . - Since
$f(n) = n^2 = O(n^{2.81 - \varepsilon})$ , it falls under Case 1. - Therefore
$T(n) = \Theta(n^{\log_2 7})$ .
The LCS of ABCB and BDCAB can be found by filling the table: BCB.
For items
- Set
$c = 14$ and$n_0 = 1$ . - For all
$n \geq 1$ ,$5n^3 + 2n^2 + 7 \leq 5n^3 + 2n^3 + 7n^3 = 14n^3$ holds.
left, right = 0, n-1
while left <= right:
mid = (left + right) // 2
if A[mid] == key: return mid
elif A[mid] < key: left = mid + 1
else: right = mid - 1
return -1
mergeSort(A, p, r):
if p < r:
q = (p+r)//2
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
for i = 1 to m:
for j = 1 to n:
if X[i] == Y[j]: c[i][j] = c[i-1][j-1] + 1
else: c[i][j] = max(c[i-1][j], c[i][j-1])
for i = 1 to n:
for w = 0 to C:
if w[i] > w: K[i][w] = K[i-1][w]
else: K[i][w] = max(K[i-1][w], v[i] + K[i-1][w-w[i]])
D[s] = 0; D[v] = inf for v ≠ s; S = {}
while S ≠ V:
u = argmin D[v] for v ∉ S
S = S ∪ {u}
for v in neighbors(u):
if v ∉ S and D[u] + w(u,v) < D[v]:
D[v] = D[u] + w(u,v)
- 0-3 min: Skim the whole exam
- 3-50 min: Write answers (calculations first, explanations later)
- 50-55 min: Review (especially fork/base cases/boundaries)
- 55-60 min: Buffer
[Definition, 1 sentence] + [Why it is needed, 1 sentence]
+ [Mechanism, 2-4 sentences]
+ [Concrete example/pseudocode/table]
+ [Limitations/trade-offs]
+ [Connections to other concepts]
- State
$c$ and$n_0$ in a Big-O proof - State the DP base cases (row 0 and column 0)
- Dijkstra cannot be used with negative edges
- Quick sort worst case = sorted input + last-element pivot
- Comparison-based lower bound
$\Omega(n \log n)$ - In Floyd-Warshall, k is the outermost loop
- Watch the arrow directions when backtracking
This document covers the why, mechanisms, examples, and connections so that the material of Weeks 1-7 can be understood from the beginning. If, while studying, you wonder why a concept appears where it does, rereading the big picture in Section 8 will make the structure clear.
The key to an answer that shows deep understanding is not rote memorization but internalizing why a concept exists, which other concepts it interlocks with, and what trade-offs it carries.