Lecture notes for CS 512, Algorithm Design

Lecture Notes for CS 512, Algorithm Design

19 April 2000, Divide and Conquer

sometimes the optimal subproblem property, or the repeated subproblem property, or the greedy-choice property doesn't apply - then what
sometimes a polynomial algorithm needs to be asymptotically faster - how
divide and conquer
1. based on a fundimental problem solving technique
2. fairly simple to apply
  1. divide the problem into subproblems
  2. solve each subproblem, usually recursively
  3. combine the subproblems back into the original problem
3. few assumptions or properties required to apply
4. nearly equal divisions can lead to logarithmic asymptotic behaivor
example - merge sort
1. divide the array to be sorted in half
2. recursively merge sort the two halves
3. combine the two sorted halves back into a single sorted array
4. ```
merge-sort(A)
  if size(A) > 1
    m <- floor((l + r)/2
    Al <- merge-sort(A[l, m])
    Ar <- merge-sort(A[m + 1, r])
    A <- merge(Al, Ar)
  fi
  return A
```
5. each iteration does Theta(n) work and it gets done log n times - Theta(n log n)
divide and conquer run-times
1. each iteration of divide and conquer
  1. reduces the probem into b subproblems, each of which have size n/b;
  2. it takes D(n) to divide the problems and C(n) to recombine the solved subproblems
  3. the iterations stop the when subproblems are small enough to be solved in constant time
2. T(n) = Theta(1) if n < c
  
  = bT(n/b) + D(n) + C(n) otherwise
3. this recurrence relation unrolls into straightforward solutions
4. sticking points
  1. make sure n divides into relatively equal parts - unbalanced subparts could lead to super-log solutions, e.g. insertion sort
  2. make sure the combination part is correct and cheap - order O(n)
example - nearest neighbor
1. straightforward algorithm takes O(|V|²) time
2. how can the problem size be reduced?
  1. divide into halves - quick reduction, pairs are easy; recombination is difficult
  2. nearest-neighbor properties make reconbination simpler - sorted strips
  3. the cost is O(|V| log² |V|) because of the double sort
  4. start out sorted and keep it sorted; only takes O(|V|) to do, reducing cost to O(|V| log |V|))

This page last modified on 18 April 2000.

T(n)	=	Theta(1)	if n < c
	=	bT(n/b) + D(n) + C(n)	otherwise