Dynamic Programming vs Memoization & Matrix Chain Multiplication

Part 1: Dynamic Programming vs Memoization

Key idea: Memoization is essentially the top-down (recursive) way of realizing dynamic programming; it "remembers" previously computed results so they are not recomputed.

Part 2: Matrix Chain Parenthesization

Given data

• $A = 30 \times 1$
• $B = 1 \times 40$
• $C = 40 \times 10$
• $D = 10 \times 15$ (the last matrix, written A(10 × 15) in the question)

Dimension array: $$p = [30,,1,,40,,10,,15]$$ $p_0=30,\ p_1=1,\ p_2=40,\ p_3=10,\ p_4=15,\quad n=4$

Recurrence

$$m[i][j]=\min_{i\le k<j}{m[i][k]+m[k+1][j]+p_{i-1},p_k,p_j}$$ Base case $m[i][i]=0$.

Length $l=2$

$m[1][2]=0+0+30\cdot1\cdot40=1200,\ s=1$

$m[2][3]=0+0+1\cdot40\cdot10=400,\ s=2$

$m[3][4]=0+0+40\cdot10\cdot15=6000,\ s=3$

Length $l=3$

$m[1][3]$:

• $k=1:\ 0+400+30\cdot1\cdot10=400+300=700$
• $k=2:\ 1200+0+30\cdot40\cdot10=1200+12000=13200$

$m[1][3]=700,\ s=1$

$m[2][4]$:

• $k=2:\ 0+6000+1\cdot40\cdot15=6000+600=6600$
• $k=3:\ 400+0+1\cdot10\cdot15=400+150=550$

$m[2][4]=550,\ s=3$

Length $l=4$

$m[1][4]$:

• $k=1:\ m[1][1]+m[2][4]+p_0p_1p_4=0+550+30\cdot1\cdot15=550+450=1000$
• $k=2:\ m[1][2]+m[3][4]+p_0p_2p_4=1200+6000+30\cdot40\cdot15=7200+18000=25200$
• $k=3:\ m[1][3]+m[4][4]+p_0p_3p_4=700+0+30\cdot10\cdot15=700+4500=5200$

$$m[1][4]=\min(1000,25200,5200)=1000,\quad s[1][4]=1$$

Optimal parenthesization (from s-table)

• $s[1][4]=1 \Rightarrow (A_1)(A_2A_3A_4)$
• $s[2][4]=3 \Rightarrow (A_2A_3)(A_4)$
• $s[2][3]=2 \Rightarrow (A_2)(A_3)$

Putting it together: $$\big(A,((B,C),D)\big)$$

Result

• Minimum number of scalar multiplications = $1000$
• Optimal order: $(A,((B,C),D))$

Verification of the count:

• $B\cdot C:\ 1\cdot40\cdot10=400$, result $1\times10$
• $(BC)\cdot D:\ 1\cdot10\cdot15=150$, result $1\times15$
• $A\cdot(BCD):\ 30\cdot1\cdot15=450$, result $30\times15$
• Total $=400+150+450=1000$ ✓

Solving $T(n) = 2T(n/2) + n$ Using the Recursion Tree Method

Step 1 - Given Data

• Recurrence: $T(n) = 2T\left(\dfrac{n}{2}\right) + n$
• Branching factor: $a = 2$ (each node makes 2 recursive calls)
• Subproblem shrink factor: $b = 2$ (size divided by 2)
• Cost at a node of size $m$: $m$ (the "$+n$" term)
• Base case: $T(1) = \Theta(1)$

Step 2 - Solve

Building the recursion tree

Level 0:            n                         cost = n
                  /   \
Level 1:       n/2     n/2                    cost = n/2 + n/2 = n
              /  \     /  \
Level 2:   n/4  n/4  n/4  n/4                 cost = 4·(n/4) = n
             ...        ...
Level k:  2^k nodes each of size n/2^k        cost = 2^k·(n/2^k) = n
             ...
Level log n: n leaves each of size 1          cost = n

Cost per level

Key observation: Every level contributes exactly $n$.

Number of levels

The recursion stops when the subproblem size reaches 1:

$$\frac{n}{2^k} = 1 \implies 2^k = n \implies k = \log_2 n$$

Number of levels $= \log_2 n + 1$ (levels $0$ through $\log_2 n$).

Summing all levels

$$T(n) = \sum_{i=0}^{\log_2 n} n = n ,(\log_2 n + 1) = n\log_2 n + n$$

Final result

$$\boxed{T(n) = \Theta(n \log n)}$$

This matches the complexity of Merge Sort, which obeys the same recurrence.

Extended Euclidean Algorithm: GCD of 12 and 16

Step 1 - Extract: Given Data

• First integer: $a = 16$ (larger)
• Second integer: $b = 12$

Goal: Find $\gcd(16, 12)$ and integers $x, y$ such that $16x + 12y = \gcd(16,12)$.

Step 2 - Solve

Forward Pass (Euclidean Algorithm)

The last non-zero remainder is $4$, so:

$$\gcd(16, 12) = 4$$

Back-Substitution (Extended Part)

Express the GCD as a linear combination $16x + 12y = 4$.

From Step 1:

$$4 = 16 - 12 \times 1$$

Rearranging:

$$4 = 16 \times (1) + 12 \times (-1)$$

Therefore:

$$x = 1, \quad y = -1$$

Verification

$$16 \times (1) + 12 \times (-1) = 16 - 12 = 4 \checkmark$$

Also confirming GCD independently: divisors of 12 are ${1,2,3,4,6,12}$, divisors of 16 are ${1,2,4,8,16}$; the greatest common divisor is indeed $4$.

Result

Subset Sum Using Backtracking

STEP 1 - EXTRACT (Given Data)

• Set of integers: $W = {5, 6, 10, 11, 15}$ (already in ascending order)
• Number of elements: $n = 5$
• Target sum: $M = 21$

Goal: find all subsets whose elements sum to exactly $21$.

STEP 2 - SOLVE

Method

For the sum-of-subsets backtracking algorithm, keep track of:

• $s$ = sum of elements included so far
• $r$ = sum of remaining elements not yet considered

Total sum $= 5+6+10+11+15 = 47$.

Bounding (pruning) conditions at element $w_k$:

1. Prune if $s + w_k > M$ (including this element overshoots the target).
2. Prune if $s + r < M$ (even including everything left cannot reach the target).

Manual enumeration of valid subsets

Since the total is only 47 and target 21, I enumerate feasible include/exclude branches.

Branch: include 5 (s=5)

• include 6 (s=11): include 10 → $s=21$ ✅ {5,6,10}
  • exclude 10 (r left = 11+15=26, s+r=37 ok): +11 → 22 > 21 prune; exclude 11: +15 → 26 > 21 prune. No solution.
• exclude 6 (s=5): include 10 (s=15): +11→26 prune; exclude 11: +15→30 prune. No solution.
  • exclude 10 (s=5): +11→16, then +15→31 prune, exclude 15→16 no; exclude 11 (s=5): +15→20 no. No solution.

Branch: exclude 5 (s=0)

• include 6 (s=6): include 10 (s=16): +11→27 prune; +15→31 prune. No solution.
  • exclude 10 (s=6): +11→17 then +15→32 prune, exclude→17 no; exclude 11 (s=6): +15 → $21$ ✅ {6,15}
• exclude 6 (s=0): include 10 (s=10): +11 → $21$ ✅ {10,11}
  • exclude 11 (s=10): +15→25 prune. No solution.
  • exclude 10 (s=0): +11→11 then +15→26 prune; +15 alone→15 no. No solution.

Verification of each solution

$$5+6+10 = 21 \checkmark \qquad 6+15 = 21 \checkmark \qquad 10+11 = 21 \checkmark$$

(Check no others: any subset with 15 needs 6 more → only {6}; any with 11 needs 10 more → only {10}; without 11 and 15, max useful combos {5,6,10}=21. Confirmed complete.)

Final Answer: All Subsets Summing to 21

There are 3 subsets of ${5,6,10,11,15}$ that sum to $21$.

Class P and NP Problems, and Approximation Algorithms

Class P Problems

Class P (Polynomial time) is the class of decision problems that can be solved by a deterministic algorithm in polynomial time, i.e., in O(n^k) time for some constant k, where n is the size of the input.

• These are considered "efficiently solvable" problems.
• Examples: Sorting, Shortest path (Dijkstra's), GCD computation, Matrix multiplication.

Class NP Problems

Class NP (Non-deterministic Polynomial time) is the class of decision problems for which a given solution (certificate) can be verified in polynomial time by a deterministic algorithm, even though finding the solution may take exponential time.

• Every problem in P is also in NP (P ⊆ NP), but whether P = NP is still an unsolved open question.
• Examples: Travelling Salesman Problem (TSP), 0/1 Knapsack, N-Queens, Subset Sum, Graph Coloring.

Key Distinction:

• P: Can be solved in polynomial time.
• NP: Solution can be verified in polynomial time.

Why Do We Need Approximation Algorithms? (Justification):

"An approximate algorithm is a way of approach NP-completeness for the optimization problem. This technique does not guarantee the best solution. The goal of an approximation algorithm is to come as close as possible to the optimum value in a reasonable amount of time which is at the most polynomial time."

Justification:

1. NP-complete problems are intractable: Many real-world optimization problems (TSP, Knapsack, Graph Coloring) are NP-complete. Exact algorithms for these problems require exponential time O(2^n), which is computationally infeasible for large inputs.

2. Polynomial time is needed in practice: Waiting exponential time for an exact solution is not practical in real-world applications. Approximation algorithms provide solutions in polynomial time.

3. Near-optimal solutions are acceptable: In many practical scenarios, a solution that is close to optimal (say within 10% of the best) is good enough. Approximation algorithms guarantee such near-optimal solutions.

4. Heuristic approach: Approximation algorithms (also called heuristic algorithms) use smart strategies to avoid exhaustive search while still producing useful results.

5. Guaranteed approximation ratio: A good approximation algorithm provides a provable bound on how far the solution is from the optimal, giving confidence in the result.

Summary Table:

Conclusion: Since NP-complete problems cannot be solved exactly in polynomial time (unless P = NP), approximation algorithms are essential to obtain good-enough solutions efficiently in real-world applications.

Sequential Search: Time & Space Complexity + Master Theorem Rules

Part 1: Time and Space Complexity of Sequential Search

Sequential search (also called linear search) compares the search element with each element in the list one by one from the beginning.

Time Complexity

Since the loop executes at most n times, the overall time complexity is O(n).

Space Complexity

• Sequential search only requires a fixed number of variables (search element, loop counter, etc.)
• No extra data structure is used
• Therefore, space complexity = O(1) (constant space)

Part 2: Master Theorem Rules for Asymptotic Bounds

The Master Theorem is used to find the time complexity of divide-and-conquer recursive algorithms whose recurrence relation is of the form:

$$T(n) = aT\left(\frac{n}{b}\right) + f(n)$$

Where:

• a >= 1 : number of subproblems
• b > 1 : factor by which input size is reduced
• f(n) : cost of work done outside the recursive calls

Let p = log_b(a)

Rule 1: f(n) is polynomially smaller than n^p

If:

$$f(n) = O(n^{p - \epsilon}) \quad \text{for some } \epsilon > 0$$

Then:

$$T(n) = \Theta(n^p) = \Theta(n^{\log_b a})$$

The recursive work dominates.

Rule 2: f(n) is asymptotically equal to n^p

If:

$$f(n) = \Theta(n^p) = \Theta(n^{\log_b a})$$

Then:

$$T(n) = \Theta(n^p \log n) = \Theta(n^{\log_b a} \cdot \log n)$$

Both the recursive work and the combining work are equal, so a log factor is added.

Rule 3: f(n) is polynomially larger than n^p

If:

$$f(n) = \Omega(n^{p + \epsilon}) \quad \text{for some } \epsilon > 0$$

AND the regularity condition holds:

$$a \cdot f\left(\frac{n}{b}\right) \leq c \cdot f(n) \quad \text{for some } c < 1$$

Then:

$$T(n) = \Theta(f(n))$$

The combining work dominates.

Summary Table