2. Divide-and-Conquer and Induction Proofs

The Cook-Levin Theorem states that the Boolean Satisfiability Problem (SAT) is NP-complete.# Divide-and-Conquer Technique

Divide-and-Conquer

Divide-and-Conquer is a general algorithm design paradigm:

• Divide: divide the input data $S$ into two disjoint subsets $S_1$ and $S_2$
• Recur: solve the subproblems associated with $S_1$ and $S_2$
• Conquer: combine the solutions for $S_1$ and $S_2$ into a solution for $S$

Link to original

Proof by Induction

Proof by Induction

Proof by Induction consists of:

• Base Case: show that solution holds for $n=1$
• Inductive Case:
  1. Assume that it holds for $n=k$.
  2. Substitute to confirm it also holds for $n=k+1$.

Link to original

Example 1: Show $T(n)=2^n-1$ for all $n\ge 1$.

Let $T(n)$ be a recursion relation defined by:

$$\begin{array}{c}T(1)=1,T(n)=2T(n-1)-1\\ \text{for all }n>1\end{array}$$

1. Base Case: Show $T(n)=2^n-1$ for $n=1$. $T(1)=1$ from definition $T(1)=2^1-1=1$ (R.H.S.)
2. Inductive Case: Assume that $T(k)=2^k-1$ for $k\ge 1$. We then have that for $n=(k+1)$: $$\begin{array}{rl}T(n)& =2T(n-1)+1\\ T(k+1)& =2T(k)+1\\ & =2(2^k-1)+1\\ & =2^{k+1}-1\end{array}$$ This is our Induction Hypothesis with $k+1$ substituted, hence by induction $T(n)=2^{n-1}$ for all $n\ge 1$.

Example 2: Show that $T(n)=\frac{n^2+n}{2}$ for all $n\ge 1$.

Let $T(n)$ be a recursion relation defined by:

$$\begin{array}{c}T(1)=2,T(n)=T(n-1)+n\\ \text{for all }n>1\end{array}$$

1. Base Case: Show $T(n)=\frac{n^2+n}{2}$ for $n=1$. $T(1)=1$ from definition $T(1)=\frac{1^2+1}{2}=1$
2. Inductive Case: Assume that $T(k)=\frac{k^2+k}{2}$ for $k\ge 1$. We then have that for $n=k+1$: $$\begin{array}{rl}T(n)& =T(n-1)+n\\ T(k+1)& =T(k)+k+1\\ & =\frac{k^2+k}{2}+k+1\\ & =\frac{k^2+3k+2}{2}\\ & =\frac{k^2+2k+1+k+1}{2}\\ & =\frac{(k+1{)}^2+(k+1)}{2}\end{array}$$ This is our Induction Hypothesis with $k+1$ substituted, hence by induction $T(n)=\frac{n^2+n}{2}$ for all $n\ge 1$.

Proof by Strong Induction

Proof by Strong Induction

Proof by Strong Induction consists of:

• Base Case: Show that solution holds for $n=1$.
• Inductive Case:
  1. Assume it holds for all $m\le k$.
  2. Substitute to confirm it also holds for $n=k+1$.

Link to original

Example 3: Show that $T(n)\ge n{\log }_{2}n$ for all $n\ge 1$.

Let $T(n)$ be a recursion relation defined by:

$$\begin{array}{c}T(1)=1,T(n)=2T\left(\begin{array}{c}\lceil \frac{n}{2}\rceil \end{array}\right)+n\\ \text{for all }n>1\end{array}$$

1. Base Case: Show that $T(n)\ge n{\log }_{2}n$ for $n=1$: $$\begin{array}{rl}T(n)& \ge ?n{\log }_{2}n\\ 1& \ge ?1\cdot {\log }_2(1)\\ 1& \ge 0\end{array}$$
2. Inductive Case: Assume that $T(m)\ge m{\log }_{2}m$ for all $m\le k$ for some $k\ge 1$. We then have that for $n=k+1$: $$\begin{array}{rl}T(k+1)& =2\cdot T\left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right)+(k+1)\\ T(k+1)& \ge 2\left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right){\log }_2\left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right)+(k+1)\\ SGTSheet& \ge 2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right){\log }_2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)+(k+1)\\ T(k+1)& \ge (k+1){\log }_2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)+(k+1)\\ T(k+1)& \ge (k+1)\left[\begin{array}{c}{\log }_2(k+1)-{\log }_2(2)\end{array}\right]+(k+1)\\ T(k+1)& \ge (k+1)\left[\begin{array}{c}{\log }_2(k+1)-1\end{array}\right]+(k+1)\\ T(k+1)& \ge (k+1){\log }_2(k+1)-(k+1)+(k+1)\\ T(k+1)& \ge (k+1){\log }_2(k+1)\end{array}$$

Example 4: Fibonacci Number proof

Check slides for this, unlikely to come up.