L8-L9 (Divide and Conquer, MergeSort)

Question 1

What is the basic idea of divide and conquer (in 3 steps)?

Answer 1

1. Break the problem into subproblems that are smaller versions of the same problem (and can be solved independently)
2. Recursively solve these subproblems
3. Appropriately combine their answers

Question 2

Divide conquer algorithms can the applied to a problem of size n by:
1. dividing into a subproblems of size roof(n/b)
2. combining their answers in O(n^d) time

With the master theorem, what would the runtime be? Start with the recurrence relation

Answer 2

We start with the recurrence relation.
T(n) = aT(roof(n/b)) + O(n^d), for some constants a > 0, b > 1 and d>= 0

Runtime:
if d > log_b(a) => O( n^d )
if d = log_b(a) => O( n^d log n )
if d < log_b(a) => O( n^(log_b(a) )

Question 3

Write out the psudeocode for the mergesort algorithm, assuming the merge() function has been implemented

Answer 3

input: a list of numbers
output: the list of sorted numbers

func mergeSort(A):
if len(A) > 1:
return merge(
mergeSort(A[0:roof(len(A)/2)],
mergeSort(A[roof(len(A)/2):len(A)]
)
else:
return a

Question 4

What does the merge() function do in mergeSort? whats its runtime?

Answer 4

merge() accepts 2 sorted arrays and returns a combined sorted array of these 2 arrays. Runtime is O(n_1 + n+2) = O(n), where n_1 and n_2 are the lengths of the 2 input arrays

Question 5

For mergeSort, what is the:
- Best-case runtime
- Worst-case runtime
- Average-case runtime

Answer 5

• O(n log n) best case
• O(n log n) worst case
• O(n log n) average case

In all cases, the algorithm divides the input array in half (log n) times, running the merge function (which takes O(n) time) times on each division