Announcements
Announcements
• Homework 3 Due on Friday
• Please fill out feedback survey:
https://forms.gle/Rs1Jz4XZpaQqag13A
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?
1. Split into Subproblems
2. Recursively Solve
3. 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 L 1 and L 2 A ← MergeSort(L 1 ) B ← MergeSort(L 2 ) Return Merge(A,B) O(n) O(n) 2T(n/2) Question: Runtime What is the runtime of MergeSort? A) O(n) B) O(n log(n)) C) O(n2) D) O(n log(3)) E) 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
) ≥ k
Return Select(L
>x
,k)
Else if Len(L
>x
)+Len(L
=x
) ≥ k
Return x
Return
Select(L
)-Len(L
=x
))
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)?
A) O(log(n))
B) O(n3/4)
C) O(n)
D) O(n log(n))
E) 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.