MATH 302 Lecture 17

« previous | Wednesday, October 26, 2011 | next »

Chapter 8.3: Divide and Conquer Algorithms

Examples:

• Binary Search on Sorted List: $f(n)=f\left(\frac{n}{2}\right)+2$
• Merge Sort: $f(n)=2f\left(\frac{n}{2}\right)+n$
• Recursive Max/Min of Unsorted List: $f(n)=2f\left(\frac{n}{2}\right)+2$
• Multiplying 2n-bit Numbers: $f(2n)=3f(n)+c(n)$

In general, form is:

$f(n)=af\left(\frac{n}{b}\right)+g(n)$

Note: the book restricts the last term to powers of n

Master Theorem

The master theorem provides a general boilerplate solution for solving recurrence relations (like divide and conquer algorithms) that satisfy a particular format.

Definition

Let $f$ be an increasing function satisfying a recurrence relation:

$f(n)=af\left(\frac{n}{b}\right)+c{n}^d$

Whenever

• $n=b^k$ for some $k\ge 1$, $a\ge 1$
• $b$ is an integer > 1
• $c$ and $d$ are real numbers ≥ 0

Then

$f(n)=af\left(\frac{n}{b}\right)+c{n}^d=\{\begin{array}{ll}\mathrm{\Theta }\left(n^d\right)& a<b^d\\ \mathrm{\Theta }(n^d\log n)& a=b^d\\ \mathrm{\Theta }\left(n^{{\log }_{b}a}\right)& a>b^d\end{array}$

Proof

Proposition. If $a=b^d$ and $n$ is a power of $b$, then a function $f$ satisfying the recurrence relation $f(n)=af(n/b)+c{n}^d$ is of the form $f(n)=f(1)n^d+c{n}^d{\log }_{b}n$

Proof. Let $k={\log }_{b}n$. Then

$\begin{array}{rl}f(n)& =c{n}^d+ac{\left(\frac{n}{b}\right)}^d+a^{2}c{\left(\frac{n}{b^2}\right)}^d+\dots +a^{k-1}c{\left(\frac{n}{b^{k-1}}\right)}^d+a^{k}f(1)\\ & =a^{k}f(1)+\sum _{j=0}^{k-1}{a}^{j}c{\left(\frac{n}{b^j}\right)}^d\\ & =a^{k}f(1)+\sum _{j=0}^{k-1}c{n}^d\\ & =a^{k}f(1)+kc{n}^d\\ & =a^{{\log }_{b}n}f(1)+c({\log }_{b}n)n^d\\ & =b^{d{\log }_{b}n}f(1)+c({\log }_{b}n)n^d\\ & =n^{d}f(1)+c({\log }_{b}n)n^d\\ & =O(n^d\log n)\end{array}$

Counting

Product Rule

Suppose we have to make $n_1$ choices followed by $n_2$ choices. For example, selecting what to wear from $n_1$ shirts and $n_2$ pants. For each shirt you choose, there are $n_2$ possible pants to choose from. Therefore, the total number of choices is their product: $n_1{n}_2$

Addition Rule

When choices are independently selected. For example, when choosing a representative for a high school: there are $n_1$ freshmen, $n_2$ sophomores, $n_3$ juniors, and $n_4$ seniors. There are $\sum _{i=1}^4{n}_i$ ways to choose a representative among all high school students.

Inclusion-Exclusion

Just like in statistics:

$|A\cup B|=\left|A\right|+\left|B\right|-|A\cap B|$

For example: How many bit strings of length $n$ either begin with 1 or end with 00?

• There are $2^{n-1}$ bit strings that begin with 1
• There are $2^{n-2}$ bit strings that end with 00
• There are $2^{n-3}$ bit strings thta begin with 1 and end with 00

Therefore, there are $2^{n-1}+2^{n-2}-2^{n-3}$ bit strings that begin with 1 or end with 00.

Division Rule

How many 3-item subsets can be made from a set of $n$ elements?

There are $n$ ways to choose the first element, $n-1$ ways to choose the second element, and $n-2$ ways to choose the last element. Since the three elements can be rearranged in 3! = 6 ways, and inclusion in a set does not rely on the order, we divide the total number of ways to choose the set by 6:

$\frac{n(n-1)(n-2)}{3}=(\genfrac{}{}{0ex}{}{n}{3})$

Counting Functions

How many functions are there from {a, b, c, d} to {1, 2, 3}?

For each element in the domain (a, b, c, and d), there are 3 targets to choose from in the codomain. Therefore, the number of possible functions is 3 · 3 · 3 · 3 = 3⁴

In general, for a domain containing $d$ items and a codomain containing $c$ items, the number of possible functions from the domain to the codomain is $c^d$

One-to-One Functions

For a one-to-one function, once an element in the codomain has been chosen, it cannot be pointed to by any element in the domain. Therefore, the number of possible one-to-one functions is <math>c(c-1)(c-2)\dots(c-d+1) = \frac{c!}{(c-d)!}