1. Divide and Conquer

Definition – Divide and Conquer

A technique for designing fast algorithms in three steps:

  1. Divide the problem into subproblems of the same form as the original;
  2. Conquer: solve the subproblems independently, usually recursively (with the same technique);
  3. 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

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)

Callstartendmiddletab[middle]Decision
10941623 > 16 → right half
25975623 < 56 → left half
356523found at index 5

Each call halves the range: .

⚠️ The slide’s code mixes K and k (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 ConquerDynamic Programming
Directiontop-downbottom-up (smallest subproblems first)
Repeated subproblemssolved again each timesolved once, stored in a table
Timecan be exponentialoften much lower
Spacelowhigher (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)

iF = F0+F1F0F1
start–01
2111
3212
4323
5535
6858
VersionTimeSpace
Recursive (stack)
Fibo1 (DP table)
Fibo2

⚠️ Fibo1 never frees its array (add delete[] F;) and writes F[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 > w

Complexity: — 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 –

ObjectWeightBenefit
123
234
345
456
012345
0000000
1003333
2003447
3003457
4003457

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 knapsack

Trace for the example

ikV[i,k]V[i-1,k]Decision
4577equal → skip 4
3577equal → skip 3
2573different → take 2,
1230different → 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 programmingMemoization
Directionbottom-uptop-down (recursive)
Subproblems solvedall of themonly those needed
Best whenall subproblems are neededthe 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)

ObjectWeight (t)Utility
1510
2440
3630
4350
012345678910
000000000000
100000101010101010
2000040404040405050
3000040404040405070
40005050505090909090

Notable cells: ; ; .

Traceback

ikV[i,k]V[i-1,k]Decision
4109070take 4,
374040skip 3
274010take 2,
1300skip 1

Best utility 90 with objects {2, 4} (7 tons).