Bubble sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. A list with n elements requires n-1 passes for sorting. In each pass, element a[i] is compared with a[i+1] ...

Item 1 2 3 4 5 6 7 --------------------------- Value 12 10 20 15 2 3 50 Weight (kg) 2 1 3 2 12 10 1 Missing data: The knapsack capacity $W$ is not given in the problem. This is essential to solve the fractional knapsack. This solution as...

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.

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$.

Bubble sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. A list with n elements requires n-1 passes for sorting. In each pass, element a[i] is compared with a[i+1] ...

Item 1 2 3 4 5 6 7 --------------------------- Value 12 10 20 15 2 3 50 Weight (kg) 2 1 3 2 12 10 1 Missing data: The knapsack capacity $W$ is not given in the problem. This is essential to solve the fractional knapsack. This solution as...

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.

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$.

Feature Recursion Backtracking --------- Definition A technique where a function calls itself directly or indirectly to solve a problem An algorithmic strategy that builds a solution incrementally and abandons a partial candidate as soon...

Aspect Dynamic Programming Greedy Strategy --------------------------------------------- Global optimality Guarantees a globally optimal solution by examining all relevant subproblem combinations May settle for a locally optimal choice t...

Statement: Cook's theorem states that the Boolean Satisfiability Problem (SAT) is NP-Complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean...

An optimal solution is the best possible feasible solution to a problem: the one that maximizes or minimizes the objective function (maximum profit, minimum cost, shortest path, etc.) while satisfying all constraints. Among all feasible ...

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

Short Notes: Asymptotic Notations and Complexity Classes

a) Big Oh, Big Omega, and Big Theta

Big Oh O(g(n)) - Asymptotic Upper Bound

Big Oh notation gives the asymptotic upper bound of a function.

Definition: A function f(x) is said to be O(g(x)) if and only if there exist two positive constants c and x₀ such that:

For all x >= x₀ : f(x) <= c * g(x)

This means g(n) is the upper bound of f(n). The algorithm will never take more time than this bound.

Example: If f(n) = 3n² + 4n + 1, then:

• 3n² + 4n + 1 <= 14n² for all n >= 1
• Therefore, f(n) = O(n²) with c = 14, x₀ = 1

Big Omega Ω(g(n)) - Asymptotic Lower Bound

Big Omega notation gives the asymptotic lower bound of a function.

Definition: A function f(x) is said to be Ω(g(x)) if and only if there exist two positive constants c and x₀ such that:

For all x >= x₀ : f(x) >= c * g(x)

This means g(n) is the lower bound of f(n).

Example: If f(n) = 3n² + 4n + 1, then:

• 3n² + 4n + 1 >= 3n² for all n >= 1
• Therefore, f(n) = Ω(n²) with c = 3, x₀ = 1

Big Theta Θ(g(n)) - Asymptotic Tight Bound

Big Theta notation gives the asymptotically tight bound of a function.

Definition: A function f(x) is said to be Θ(g(x)) if and only if there exist three positive constants c₁, c₂ and x₀ such that:

For all x >= x₀ : c₁ * g(x) <= f(x) <= c₂ * g(x)

This means g(n) is both an upper and lower bound of f(n).

Example: If f(n) = 3n² + 4n + 1, g(n) = n², choose c₁ = 1, c₂ = 14, n₀ = 1:

• 1 * n² <= 3n² + 4n + 1 <= 14 * n² for all n >= 1
• Therefore, f(n) = Θ(n²)

b) Class P, Class NP, and NP-Complete

Class P (Polynomial Time)

• Class P is the set of all decision problems that can be solved by a deterministic algorithm in polynomial time O(n^k) for some constant k.
• These are considered tractable (efficiently solvable) problems.
• Examples: Sorting, searching, shortest path (Dijkstra's), GCD computation.

Class NP (Non-deterministic Polynomial Time)

• Class NP is the set of all decision problems for which a given solution (certificate) can be verified in polynomial time by a deterministic algorithm.
• NP does not necessarily mean the problem cannot be solved in polynomial time; it means verification is polynomial.
• Every problem in P is also in NP (P ⊆ NP), but whether P = NP is an unsolved problem in computer science.
• Examples: Boolean satisfiability (SAT), Hamiltonian cycle, Subset sum.

NP-Complete

• A problem X is NP-Complete if:

  1. X belongs to NP (its solution can be verified in polynomial time), AND
  2. Every other problem in NP can be reduced to X in polynomial time (X is NP-Hard).

• NP-Complete problems are the hardest problems in NP.

• If any NP-Complete problem can be solved in polynomial time, then all NP problems can be solved in polynomial time (i.e., P = NP).

• Examples: SAT problem, Travelling Salesman Problem (TSP), Knapsack problem, Graph Coloring.

Relationship Summary

P ⊆ NP
NP-Complete ⊆ NP
If P = NP, then all NP-Complete problems become P

Definition: The Random Access Machine (RAM) model is a model for counting the steps in an algorithm in order to analyze its time complexity. In this model: - Basic operations (+, -, , /) are counted as 1 step - Memory references (read/wr...

$$x \equiv 1 \pmod{3}, \quad x \equiv 2 \pmod{5}, \quad x \equiv 0 \pmod{7}$$ $i$ remainder $ai$ modulus $mi$ --------- 1 1 3 2 2 5 3 0 7 Check coprimality: $\gcd(3,5)=\gcd(5,7)=\gcd(3,7)=1$. Moduli are pairwise coprime, so CRT gives a u...

A Vertex Cover of a graph G = (V, E) is a set of vertices C ⊆ V such that every edge in G is incident to at least one vertex in C. The optimization problem is to find the vertex cover with the fewest vertices (optimal vertex cover C). S...