1. Divide and Conquer
Definition – Divide and Conquer
A technique for designing fast algorithms in three steps:
- Divide the problem into subproblems of the same form as the original;
- Conquer: solve the subproblems independently, usually recursively (with the same technique);
- Combine the subproblem solutions into the solution of the original problem.
It generally leads to a recursive algorithm.
flowchart TD P["Problem of size n"] --> S1["Subproblem 1 (size n/2)"] P --> S2["Subproblem 2 (size n/2)"] S1 --> R1["Solution to subproblem 1"] S2 --> R2["Solution to subproblem 2"] R1 --> R["Solution to the original problem"] R2 --> R
Binary Search
Search a key in a sorted array:
- Let be the key in the middle of the array.
- If → found.
- If → search the first half.
- If → search the second half.
Can be implemented recursively or iteratively.
template <class Elem>
int binarySearch(Elem *tab, int start, int end, Elem k) {
if (start > end) return -1; // not found
int middle = (start + end) / 2;
if (tab[middle] == k) return middle;
else if (tab[middle] < k)
return binarySearch(tab, middle + 1, end, k);
else
return binarySearch(tab, start, middle - 1, k);
}Worked example – search in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0–9)
| Call | start | end | middle | tab[middle] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 23 > 16 → right half |
| 2 | 5 | 9 | 7 | 56 | 23 < 56 → left half |
| 3 | 5 | 6 | 5 | 23 | found at index 5 |
Each call halves the range: .
⚠️ The slide’s code mixes
Kandk(C++ is case-sensitive) — use one name. Also, binary search only works on a sorted array.
2. Dynamic Programming
Definition – Dynamic Programming (Bellman, 1950s)
An improvement of divide and conquer, introduced for optimization problems in operational research. The (optimal) solution of size is expressed as a function of the (optimal) solutions of subproblems of size .
D&C vs DP
| Divide and Conquer | Dynamic Programming | |
|---|---|---|
| Direction | top-down | bottom-up (smallest subproblems first) |
| Repeated subproblems | solved again each time | solved once, stored in a table |
| Time | can be exponential | often much lower |
| Space | low | higher (the table) |
DP increases space (table) but reduces time, sometimes enormously.
Worked example – Fibonacci
Naive recursion recomputes the same values many times:
flowchart TD F5["F(5)"] --> F4["F(4)"] F5 --> F3a["F(3)"] F4 --> F3b["F(3)"] F4 --> F2a["F(2)"] F3a --> F2b["F(2)"] F3a --> F1a["F(1)"] F3b --> F2c["F(2)"] F3b --> F1b["F(1)"]
is computed twice, three times… → .
DP version (table):
int Fibo1(int n) {
int *F = new int[n + 1];
int result = n;
F[0] = 0; F[1] = 1;
for (int i = 2; i <= n; i++)
result = F[i] = F[i-1] + F[i-2];
return result;
}Space-optimized version (answer to “a better solution to avoid the space complexity?”): only the last two values are needed.
int Fibo2(int n) {
int F0 = 0, F1 = 1, F = n;
for (int i = 2; i <= n; i++) {
F = F0 + F1;
F0 = F1;
F1 = F;
}
return F;
}Trace of Fibo2(6)
| i | F = F0+F1 | F0 | F1 |
|---|---|---|---|
| start | – | 0 | 1 |
| 2 | 1 | 1 | 1 |
| 3 | 2 | 1 | 2 |
| 4 | 3 | 2 | 3 |
| 5 | 5 | 3 | 5 |
| 6 | 8 | 5 | 8 |
| Version | Time | Space |
|---|---|---|
| Recursive | (stack) | |
Fibo1 (DP table) | ||
Fibo2 |
⚠️
Fibo1never frees its array (adddelete[] F;) and writesF[1]out of bounds when .
3. The 0/1 Knapsack Problem
Definition – Knapsack problem
A knapsack of capacity and a set of objects; object has weight and benefit . Find that
Naive algorithm: test all subsets → .
DP formulation
= maximum benefit with capacity using objects :
- : best solution without object ;
- : take object (replacing some items).
The table has rows and columns .
Algorithm
for w = 0 to W: V[0,w] = 0
for i = 1 to n: V[i,0] = 0
for i = 1 to n
for w = 1 to W
if w_i <= w // object i can fit
if b_i + V[i-1, w-w_i] > V[i-1, w]
V[i,w] = b_i + V[i-1, w-w_i]
else
V[i,w] = V[i-1, w]
else
V[i,w] = V[i-1, w] // w_i > wComplexity: — pseudo-polynomial.
⚠️ “Pseudo-polynomial” because is a number, not an input size: doubling the number of digits of squares the work. So DP is not a polynomial algorithm for knapsack in general.
Worked example –
| Object | Weight | Benefit |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
| 4 | 5 | 6 |
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 | 0 | 0 | 3 | 4 | 4 | 7 |
| 3 | 0 | 0 | 3 | 4 | 5 | 7 |
| 4 | 0 | 0 | 3 | 4 | 5 | 7 |
Key cells:
- : , → 3.
- : , → 7.
- : → 5.
- : → 7.
- : → 7.
Maximum benefit .
Finding the objects (traceback)
The table already contains everything needed.
i = n, k = W
while i > 0 and k > 0
if V[i,k] != V[i-1,k]
mark object i as in the knapsack
i = i-1, k = k - w_i
else
i = i-1 // object i not in the knapsackTrace for the example
| i | k | V[i,k] | V[i-1,k] | Decision |
|---|---|---|---|---|
| 4 | 5 | 7 | 7 | equal → skip 4 |
| 3 | 5 | 7 | 7 | equal → skip 3 |
| 2 | 5 | 7 | 3 | different → take 2, |
| 1 | 2 | 3 | 0 | different → take 1, |
Optimal solution: objects {1, 2}, weight 5, benefit 7.
4. Memoization
Definition – Memoization
(Not a misspelling of “memorization”.) A technique for calculations where the same input always yields the same result, the calculation is lengthy, and is likely to be repeated on the same input. It is a cross between computing the answer and looking it up in a table: compute once, store, reuse.
DP vs memoization
| Dynamic programming | Memoization | |
|---|---|---|
| Direction | bottom-up | top-down (recursive) |
| Subproblems solved | all of them | only those needed |
| Best when | all subproblems are needed | the recursive form is easier / not all subproblems are needed |
Rule: on a new subproblem → solve it and store the result; on an already solved one → read it from the table.
Memoized knapsack
for w = 0 to W: V[0,w] = 0
for i = 1 to n: V[i,0] = 0
for i = 1 to n
for w = 1 to W
V[i,w] = -1 // "not computed yet"
mKnapsack(i, w)
if V[i,w] < 0 // not computed yet
if w < w_i
value = mKnapsack(i-1, w)
else
value = max(mKnapsack(i-1, w), b_i + mKnapsack(i-1, w-w_i))
V[i,w] = value
return V[i,w]Called as mKnapsack(n, W).
⚠️ The sentinel only works because benefits are non-negative. If values can be negative, use a separate “computed” flag.
5. Hands-on – Space Shuttle (capacity 10 tons)
| Object | Weight (t) | Utility |
|---|---|---|
| 1 | 5 | 10 |
| 2 | 4 | 40 |
| 3 | 6 | 30 |
| 4 | 3 | 50 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| 2 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 50 |
| 3 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 70 |
| 4 | 0 | 0 | 0 | 50 | 50 | 50 | 50 | 90 | 90 | 90 | 90 |
Notable cells: ; ; .
Traceback
| i | k | V[i,k] | V[i-1,k] | Decision |
|---|---|---|---|---|
| 4 | 10 | 90 | 70 | take 4, |
| 3 | 7 | 40 | 40 | skip 3 |
| 2 | 7 | 40 | 10 | take 2, |
| 1 | 3 | 0 | 0 | skip 1 |
Best utility 90 with objects {2, 4} (7 tons).