Announcements
Announcements
Homework 3 Due on Friday
Please fill out feedback survey: https://forms.gle/Rs1Jz4XZpaQqag13A
Last Time
Divide & Conquer
Split into smaller subproblems
Solve Recursively
Recombine to get answer
Master Theorem
Master Theorem
Theorem: Let T(n) be given by the recurrence:
Then we have that
Today
MergeSort
Order Statistics
Note on Proving Correctness
There’s a general procedure for proving correctness of a D&C algorithm:
Use Induction: Prove correctness by induction on problem size.
Base Case: Your base case will be the non-recursive case of your algorithm (which your algorithm does need to have).
Inductive Step: Assuming that the (smaller) recursive calls are correct, show that algorithm works.
Sorting
Problem: Given a list of n numbers, return those numbers in ascending order.
Example:
Input: {0, 5, 2, 7, 4, 6, 3, 1}
Output: {0, 1, 2, 3, 4, 5, 6, 7}
Divide and Conquer
How do we make a divide and conquer algorithm?
Split into Subproblems
Recursively Solve
Combine Answers
– Split list in two
– Sort each sublist
– ???
Merge
Problem: Given two sorted lists, combine them into a single sorted list.
We want something that takes advantage of the individual lists being sorted.
Merge Idea
List A
List B
Increasing
Increasing
Smallest is one of these
Merge
Merge(A,B)
C ← List of length Len(A)+Len(B)
a ← 1, b ← 1
For c = 1 to Len(C)
If (b > Len(B))
C[c] ← A[a], a++
Else if (a > Len(A))
C[c] ← B[b], b++
Else if A[a] < B[b]
C[c] ← A[a], a++
Else
C[c] ← B[b], b++
Return C
Runtime: O(|A|+|B|)
MergeSort
MergeSort(L)
If Len(L) = 1 \\ Base Case
Return L
Split L into equal L1 and L2
A ← MergeSort(L1)
B ← MergeSort(L2)
Return Merge(A,B)
O(n)
O(n)
2T(n/2)
Question: Runtime
What is the runtime of MergeSort?
O(n)
O(n log(n))
O(n2)
O(n log(3))
O(n2 log(n))
Master Theorem:
a = 2, b = 2, d = 1
a = bd
O(nd log(n)) = O(n log(n))
Example
05274631
0527
4631
05
27
46
31
0
5
2
7
4
6
3
1
05
27
46
13
0257
1346
01234567
Optimaility
O(n log(n)) is optimal for comparison based sorting algorithms.
Another Sorting Algorithm
Repeatedly take the smallest remaining element and put it in the list.
Naïve implementation takes O(n2) time.
Use priority queues.
Heap Sort
HeapSort(L)
Priority Queue Q
For x in L
Q.Insert(x)
List C
While(Q not empty)
C ← C.Append(Q.DeleteMin())
Return C
O(n) Inserts
O(n) DeleteMins
Runtime O(n log(n))
Order Statistics
Suppose that we just want to find the median element of a list, or the largest, or the 10th smallest.
Problem: Given a list L of numbers and an integer k, find the kth largest element of L.
Naïve Algorithm: Sort L and return kth largest.
O(n log(n)) time.
Divide Step
Select a pivot x ∈ L. Compare it to the other elements of L.
= x
< x
> x
Which list is our answer in?
Answer is > x if there are ≥ k elements bigger than x.
Answer is x if there are < k elements bigger and ≥ k elements bigger than or equal to x.
Otherwise answer is less than x.
Only recurse on one list
Order Statistics
Select(L,k)
Pick x ∈ L
Sort L into L>x, L
Return Select(L>x,k)
Else if Len(L>x)+Len(L=x) ≥ k
Return x
Return
Select(L
O(n)
???
???
Runtime
Runtime recurrence
T(n) = O(n) + T(sublist size)
Problem: The sublist we recurse on could have size as big as n-1. If so, runtime is O(n2).
Need to ensure this doesn’t happen.
Randomization
Fix: Pick a random pivot.
n/4
n/4
n/2
x
There’s a 50% chance that x is selected in the middle half.
If so, no matter where the answer is, recursive call of size at most 3n/4.
On average need two tries to reduce call.
Question: Runtime
We get a runtime recurrence:
T(n) = O(n) + T(3n/4)
What is T(n)?
O(log(n))
O(n3/4)
O(n)
O(n log(n))
O(n2)
Master Theorem:
a = 1, b = 4/3, d = 1
a < bd
O(nd) = O(n)
Note
The algorithm discussed does give the correct answer in expected O(n) time.
There are deterministic O(n) algorithms using similar ideas, but they are substantially more complicated.