CSCE 221 Chapter 10

« previous | Tuesday, March 8, 2011 | next »

Divide and Conquer (D&C)

(See wikipedia:Master Theorem→)

Recurrence Relation

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

• $T(n)$ represents the time to solve a problem of size $n$
  • $aT(n/b)$ can be separated into several subproblems if divided unequally (e.g. $T(n/3)+T(2n/3)$)
• $a$ represents the number of subproblems that we'll have to recurse over
• $b$ represents the size of subproblems we'll recurse over
• $D(n)$ represents the time to partition into subproblems
• $C(n)$ represents the time to combine subproblem solutions to get a total solution

(not in chapter)

Example

Multiply two $n$-bit integers:

1. Divide: split I and J into high- and low- order bits

   $\begin{array}{rl}I& =I_h{2}^{\frac{n}{2}}+I_l\\ J& =J_h{2}^{\frac{n}{2}}+J_l\end{array}$

2. Multiply parts and adding:

   $\begin{array}{rl}I*J& =(I_h{2}^{\frac{n}{2}}+I_l)*(J_h{2}^{\frac{n}{2}}+J_l\\ & =I_h{J}_h{2}^n+I_h{J}_l{2}^{\frac{n}{2}}+I_l{J}_h{2}^{\frac{n}{2}}+I_l{J}_l\end{array}$

3. Recurrence Relation: $T(n)=4T\left(\frac{n}{2}\right)+n$

Merge Sort D&C

1. Divide: divide $S$ into $S_1$ and $S_2$
2. Recurse: divide $S_1$ and $S_2$ recursively until base case is of size 0 or 1
3. Conquer: combine solutions of $S_1$ and $S_2$

Algorithm mergeSort(Sequence S,Comparator c) {
  if (S.size() > 1) {
    (S_1, S_2) = partition(S, n/2);
    mergeSort(S_1);
    mergeSort(S_2);
    S := merge(S_1,S_2);
  }
}

Algorithm merge(Sequence A, Sequence B) {
  S = Sequence();
  while (!A.isEmpty() && !B.isEmpty()) {
    if (A.first().element() < B.first().element()) {
      S.insertLast(A.remove(A.first()));
    } else {
      S.insertLast(B.remove(B.first()));
    }
  }
  while (!A.isEmpty()) {
    S.insertLast(A.remove(A.first()));
  }
  while (!B.isEmpty()) {
    S.insertLast(B.remove(B.first()));
  }
  return S;
}

Analysis

Depth	# Sequences	Size of each Sequence
0	1	$n$
1	2	$\frac{n}{2}$
2	4	$\frac{n}{4}$
…	…	…
$i$	$2^i$	$\frac{n}{2^i}$

The merge() algorithm takes $O(n)$ time, where $n$ is the size of $S_1$ and $S_2$.

Time function recurrence relation: $T(n)=2T\left(\frac{n}{2}\right)+O(1)+O(n)$

$T(n)$ forms a binary tree of height $O(\log n)$, where an $O(n)$ function is called at each level. Therefore $O(T(n))=O(\log n)\times O(n)=O(n\log n)$.

Brute force analysis:

$\begin{array}{rl}T(n)& =2T\left(\frac{n}{2}\right)+O(1)+O(n)\\ & =2T\left(\frac{n}{2}\right)+n\\ & =2(2T\left(\frac{n}{4}\right)+\frac{n}{2})+n\\ & =4T\left(\frac{n}{4}\right)+2n\\ & =4(2T\left(\frac{n}{8}\right)+\frac{n}{4})+2n\\ & =8T\left(\frac{n}{8}\right)+3n\\ & =\dots \\ & =2^{i}T\left(\frac{n}{2^i}\right)+in\\ i& =\log n& \text{because we stop when}\frac{n}{2^i}=1\\ \therefore T(n)& =nT(1)+n\log n\end{array}$

Therefore, merge sort is $O(n\log n)$

Parallel Algorithm

D&C is very useful for parallel processing: $T(n)=T\left(\frac{n}{2}\right)+O(n)=O(n)$

Quick Sort

Thursday, March 10, 2011

1. Divide: Pick a random element $x$ called a pivot and partition $S$ into $L$ elements less than $x$, $E$ elements equal to $x$, and $G$ elements greater than $x$.
2. Recur: Sort $L$ and $G$
3. Conquer: Combine/join $L$, $E$, and $G$.

Algorithm partition(Sequence S, Position p) {
  Sequence L, E, G;
  x = S.remove(p);
  while (!S.isEmpty()) {
    y = S.remove(S.first());
    if (y < x) L.insertLast(y);
    else if (y == x) E.insertLast(y);
    else G.insertLast(y);
  }
  // sort L, E, and G
  return merge(L, E, G);
}

Analysis

Best Case (we pick the middle element every time; $P(n)=\frac{1}{n^n}$):

$T(n)=2T\left(\frac{n}{2}\right)+O(n)+O(1)=\mathrm{\Theta }(n\log n)$

Worst Case (we pick smallest or largest element every time):

$T(n)=T(n-1)+O(n)+O(1)=\mathrm{\Theta }\left(n^2\right)$

Summary of Comparison-based Algorithms

Algorithm	Time	Notes
selection-sort	$O(n^2)$	in-place, slow (good for small inputs)
insertion sort	$O(n^2)$	in-place, slow (good for small inputs)
quick-sort	$O(n\log n)$	in-place, randomized, fastest (good for large inputs)
heap-sort	$O(n\log n)$	in-place, fast (good for large inputs)
merge-sort	$O(n\log n)$	sequential data access, fast (good for large inputs)

Bucket-Sort

Not comparison-based and uns in linear time.

Input: A sequence of key/value paired items with key range 0-9 (inclusive).

Lexicographic sort (sort by key, then by item)

1. Create a bucket array of size 10 (chained array like what was used for dictionaries)
2. Stick items in their buckets depending on key element
3. pull items out of bucket (don't worry about arranging by value element)

In General:

• Keys range from [0, N−1]
• Create a bucket array $B$ of size $N$
• Phase 1: Empty the sequence by moving each item into its bucket $B[k]$
• Phase 2: For i=0..N-1, move the items to the end of the sequence

def bucketSort s, n
  b = Array.new(n)
  while !s.isEmpty do
    f = s.first
    (k,o) = s.remove f
    B[k].insertLast (k,o)
  end
  for 0.upto(N-1) do |i|
    while !B[i].isEmpty do
      f = B[i].first
      (k,o) = B[i].remove f
      s.insertLast (k,o)
    end
  end
end

In order to sort lexicographically, we bucket-sort based on the last element in the tuple, then bucket sort in reverse up to the 1st tuple element. The reason this works is because bucket-sort is stable

Example

Sort (3,3) (1,5) (2,5) (1,2) (2,3) (1,7) (3,2) (2,2):

1. bucket-sort by 2nd: (1,2) (3,2) (2,2) (3,3) (2,3) (1,5) (2,5) (1,7)
2. bucket-sort by 1st: (1,2) (1,5) (1,7) (2,2) (2,3) (2,5) (3,2) (3,3)

Radix Sort

1. Break an integer into digit tuples:

   e.g. 746 → (7,4,6); 10 → (0,1,0)

2. Perform bucket-sort on the ones place, tens place, hundreds place, etc.
3. et voila!

def radixSort s, n
  # s is a sequence of d-tuples such that each place in the tuple is between 0 and n-1
  for d.downto(1) do |i|
    # set key k of each item of s to i-th dimension x_i
    bucketSort(s,n)
  end
end

Runs in $O(d(n+N))$ time, where $d$ is the number of "digits" (thus number of iterations), $n$ is the number of items to sort, and $N$ is the number of buckets.

Example

In computers, we use binary numbers:

• Bits can be 0 or 1

  We can look at many bits. We'll call this number $i$ (i.e. $i=2$: 00, 01, 10, 11)

• $N=2^i$
• $d=B/i$, where $B$ is the number of bits in an integer.

Now the running time is $O\left(\frac{B}{i}(n+2^i)\right)$. The best value to choose for $i$ would be one that balances $d$ and $N$ somehow.

---

Thursday, March 24, 2011

$O(d(n+N))$

Balance $d$ and $N$ for $b$-bit binary integers:

• $i=lo{g}_{2}n$
• $d=2^i=n$
• $N=b/i=b/{\log }_{2}n$

$O(\frac{b}{{\log }_{2}n}(2n))$

Selection

Tuesday, March 29, 2011

Choose the $k$ smallest element from an array (also called order statistics):

• Minimum: $k=1$ — 1^st order statistic
• Maximum: $k=n$ — n^th order statistic
• Median: $k=n/2$

Naïve solution: sort and select $k$th item.

Linear Looking

Algorithm minimum(A) {
  m = A[1];
  for i in 2..n {
    M = min(m, A[i]);
  }
  return m;
}

Runs in $O(n)$ time. (no better)

If we want to find the $k$th smallest element, we have to perform k scans, so $O(kn)$

Quick-select

Randomized selection algorithm based on "prune-and-search" paradigm (similar to D&Q)

Prune: pick a pivot element x and partition S into subsets less, equal, and greater.

Search: Depending on $k$, answer must be in only one of those subsets. Recurse on that half only

def partition S, p
  # input: Sequence (S) position (p) of pivot
  # output: three subsequences based on pivot value: L (less than), E (equal to), and G (greater than)

  l = e = g = Sequence.new
  x = s.remove(p)
  while !s.isEmpty? do
    y = s.remove(s.first)
    if y < x do
      l.insertLast(y)
    else if y == x do
      e.insertLast(y)
    else do
      g.insertLast(y)
    end
  end
  return l,e,g
end

Runs in $O(n)$ Best and Average; $O(n^2)$ Worst case.

Deterministic Selection

(See wikipedia:Selection algorithm#Linear general selection algorithm - Median of Medians algorithm→)

Solves in $O(n)$ worst-case

Idea: recursively use the selection algorithm itself to find a good pivot for quick-select:

1. Divide $S$ into $n/5$ sets of 5 each
2. Find a median in each set.
3. Create a sequence of all the medians of the chunks-of-five
4. Recursively call this algorithm on the sequence of medians.

Analysis

$n/5$ columns, $n/10$ bigger/smaller than Median of Medians (MoM)

$3n/10$ elements bigger/smaller than MoM.

$T(n)=T\left(\frac{7}{10}n\right)+n=O(n)$