Divide and Conquer

October 01, 2019 | 9 Minute Read

CSE 202 Lecture 2-4

Divide and Conquer

Divide and Conquer

recursion is to break into smaller subproblems (of the same type), solving it recursively (use the same solution).
divide and conquer is a very specific form of recursion.

Example 1: Given a list of numbers, sort them.

Input: $a_1 …. a_n$ Output: sorted list

Key Questions:

How to make $a_1 …. a_n$ of smaller size?
How do we put the solutions together?
When does the recursion stop?

Merge-Sort ($a_1…..a_n$), length of list = y

cut the list in half subproblem, do merge-sort on each half to sort it, whenever y >= 2.
- when y = 1 we cannot split. This also prevents infinte recursion.
how to combine two sorted list? $O(n)$

Prove of correctness.

prove by induction.

when n= 1, sorting them is trivial. assume n<k, it’s true. let’s see n=k+1, subproblems of size smaller, as long as merging is correct, it is correct. mergine we are extracting the smallest? Cause we are taking the smallest in the sorted. Therefore merge is correct.

Analyze complexity

Define time complexity: $T(n)$ = worst case # of steps taken to sort a list of length n.
why n? cause longer the list, the longer it will take to sort.
why worst case? becuase sometimes we are lucky yo have a sorted list. Most of the time we have no control over the input to the program.
it’s possible to do best, average case.

Recursive helps us figure out complexity.

T(1) = 1 T(n) = 2(T(n/2)) + time it takes to merge(linear time) = 2T(n/2) + cn ( c depend on what kind of operation bout count on)

** Solving recursion relationship into explicit function like logn**

review theta, omega, big-O
solve the T(n) = n logn

Quick Sort

select pivot element, partition the list into left (less than pivot) right side.
- all in left are <= right
- partitioning algorithm. prove the correctness. list with pointer with both end
- how to select pivot? so that each part is not empty, and subproblem is of smaller size.
for each part, recursive do quick sort.
put them together is just concatenation. O(1)

** if we select a bad pivot and bad partition algorithm** T(n) = T(1) + T(n-1) ==> O(n^2) worst case.

** simple way to fix it. **

select randomly? hope we can get a more even partition?? randomized algorithm
- the probability is 1/n to get exactly in the middle. Luck is not on our side.
- T(n/4) + T(3/4n) solve? worst case 50% of change we will randomly select a pivot here is no worse than this. this end up to be nlogn.
  - why? see all elements as sorted. The middle 50% falls into the 25%-75%.
  - we expect to try twice, to get a right split.
  - try twice, success with right partition, and then proceed with recursion.
  - average case analysis nlogn.
if we select two and use the average as pivot??
there’s a O(n) to find the median algorithm. But the time constant is bigger.
randomness don’t care about the input.

Proof of correctness

correctness of partition algorithm. all left <= pivot; pivot <= all right thus all right >= left make sure not empty. <– the partitioning algorithm takes care of it. what if all elements are them same?? prove by induction.

What is the best sorting used in practice nowadays.

Example 2: Integer multiplication

Given 2 n-bit numbers $x$ ans $y$, return the $x \times y$.

Naive algorithm: elementary school way

takes $\theta(n^2)$