5-6

Question 1

How does a divide and conquer algorithm work?

Answer 1

If the data structure is an atom case it is processed directly, else we divide it into two or more smaller pieces, and apply the algorithm recursively.

Question 2

How does binary search work?

Answer 2

Needs sorted data, find the middle index and compare with what is being searched for. If the searched for item is less search the left subarray, if greater than the middle search the right subarray. If an empty array is returned we have split too much and the item is not in the array.
Has a complexity of O(log n).

Question 3

How do we merge to sorted arrays?

Answer 3

Compare two keys, put the lower one in the array and increment the index for the main array and the sub array the lower key came from. Repeat. Merge is O(n).

Question 4

How does mergesort work?

Answer 4

Repeatedly split an array and once at the bottom rebuild by merging the pieces.

Question 5

How do we solve a recurrence?

Answer 5

We need to get rid of the f(n) on the right hand side of the equation, try to simplify the pattern and then substitute, turning the f(n-k) into f(1), e.g by making k = n-1. This is not proof yet.
We must show that f and the new function g are the same function. Do this using induction.