L10 (Medians and Matrix Multiplication)

Question 1

What is the formal definition of the median of a list of numbers?
What if there is an even number of elements?

Answer 1

• The median of a list of numbers is a number such that half the numbers are smaller and half are bigger
• If there is an even number of elements, we will arbitrary take the smaller of the 2 choices (in some cases we take the mean of the 2)

Question 2

Describe an algorithm to find the median of an array of unsorted numbers which runs in O(n log n) time

Answer 2

Sort the array & then take the roof(n/2) element

Question 3

Suppose we’d like to perform matrix multiplication on two n x n matrices. If we brute force it, how long does it take?

Answer 3

There are n^2 entries in each matrix, and we need to perform n calculations per entry. Therefore, it would take O(n^3) time to brute force the matrix multiplication

Question 4

Explain how divide and conquer can be used to create a matrix multiplication for matrices X and Y which are both n x n

What would the runtime be?

Answer 4

1. Divide X and Y into four n/2 x n/2 blocks
2. Apply Strassen’s Algorithm

Runtime would be O(n^2.81), which is faster than O(n^3)

The recurrence relation is:
T(n) = 7T(n/2) + O(n^2)

Question 5

Describe an algorithm to find the median of an array of unsorted numbers which runs in O(n) time

Answer 5

1. Choose a pivot element from the array at random.
2. Partition the array so that all elements smaller than the pivot are on the left side, and all elements greater than the pivot are on the right side.
3. Check if the pivot element is the median. If it is, return it. If not, compare its index to the index of the desired median (which is (n-1)/2 for an array of length n) and either recurse on the left or right subarray, or return the median if the pivot index equals the desired median index.
4. Repeat until the median is found.

Question 6

Using the Split-Selection algorithm to find the median of an unsorted array of n numbers,

• What is the average runtime
• What is the worst case runtime? and how would this happen?

Answer 6

• Average is O(n) time
• Worst Case is O(n^2) time. This happens when the random number which we pick is ALWAYS the smallest element and we have to pick the random number v and call split n times

Question 7

We can compute the ______, ______, and ______ of an array of unsorted numbers in O(n) time average case and O(n^2) worst case using the ___________ algorithm

Answer 7

min
max
median
split-select