202401160914
Status: #idea
Tags: DAA

Divide & Conquer Algorithms

Main Steps

1. Dividing the problem into smaller sub-problems
2. Solving these sub-problems
3. Combining the solutions for those smaller sub-problems to solve the original problem

Analysing D&C Algorithms

• We uses recurrence relations
• $T(n)=aT\left(\frac{n}{b}\right)+c(n)$
• $a$ -> Number of sub-problems
• $b$ -> $n/b$ is size of each sub-problem
• $c(n)$ -> TODO

Longest Path Problem

Complete Graph
A graph where every node is connected to every other node by a unique edge.

• In a complete graph, there are at least $(n-1)!$ paths of length $n$
• Hence, $\mathrm{\exists }$ at least an exponential solution (because $n!\ge 2^n$)

Coin Change Problem

• Given a value of $N$, find the minimum number of coins of fixed denominations, each with infinite supply
• Key observations
  • Optimisation problem
  • Making change is possible i.e. solution exists (because 1 is there)
  • Multiple solutions exist
  • Question has 2 parts:
    1. Minimum number of coins required
    2. Which coins are part of the solution?

• This relation has overlapping sub-problems

Optimal Substructure Property

• Optimal solution to the original problem incorporates optimal solutions to the sub-problems

Proof of Optimal Substruvture Property

References