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
Sorting
Order Statistics
Today
Binary Search
Closest Pair of Points
Search
Problem: Given a sorted list L and a number x, find the location of x in L.
Naïve Algorithm: Try every element of L.
O(n) time.
Usually, you cannot beat O(n) because any algorithm needs to read the entire input. However, since the list is guaranteed to be sorted, we can do better here.
Divide
Split L into two lists.
Could search for x in each
T(n) = 2T(n/2)+O(1) → Too slow
Use sorting to figure out which list to check.
If L[i] > x, location must be before i.
If L[i] < x, location must be after i.
If L[i] = x, we found it.
Binary Search
BinarySearch(L,i,j,x)
\\Search between L[i] and L[j]
If j < i, Return ‘error’
k ← [(i+j)/2]
If L[k] = x, Return k
If L[k] > x
Return BinarySearch(L,i,k-1,x)
If L[k] < x
Return BinarySearch(L,k+1,j,x)
O(1)
T(n/2)
Question: Runtime
We get a runtime recurrence:
T(n) = O(1) + T(n/2)
What is T(n)?
O(log(n))
O(n1/2)
O(n1/2 log(n))
O(n)
O(n log(n))
Master Theorem:
a = 1, b = 2, d = 0
a = bd
O(ndlog(n)) = O(log(n))
Binary Search Puzzles
You have 27 coins one of which is heavier than the others, and a balance. Determine the heavy coin in 3 weightings.
Lots of puzzles have binary search-like answers. As long as you can spend constant time to divide your search space in half (or thirds). You can use binary search in O(log(n)) time.
Closest Pair of Points (Ex 2.32)
Problem: Given n points in the plane (x1,y1)…(xn,yn) find the pair (xi,yi) and (xj,yj) whose Euclidean distance is as small as possible.
Naïve Algorithm: Try every pair of points. O(n2) time.
Divide and Conquer Outline
Divide points into two sets by drawing a line.
Compute closest pair on each side.
What about pairs that cross the divide?
Observation
Suppose closest pair on either side at distance δ.
Only need to care about points within δ of dividing line.
Need to know if some pair closer than δ.
Main Idea
Proposition: Take the points within δ of the dividing line and sort them by y-coordinate. Any one of these points can only be within δ of the 8 closest points on either side of it.
This means that we only need to check a few pairs of points crossing the line.
Idea: Points on each side separated by δ. Not enough room for many of them nearby.
Proof
Nearby points must have y-coordinate within δ.
Subdivide region into δ/2-sided squares.
At most one point in each square.
δ
δ
δ
δ
< δ
Algorithm
CPP(S)
If |S| ≤ 3
Return closest distance
Find line L evenly dividing points
Sort S into Sleft, Sright
δ ← min(CPP(Sleft),CPP(Sright))
Let T be points within δ of L
Sort T by y-coordinate
Compare each element of T to 8 closest
on either side. Let min dist be δ’.
Return min(δ,δ’)
O(n) (median of x-coordinates)
O(n)
2T(n/2)
O(n log(n))
O(n)
Runtime
We have a recurrence
T(n) = O(n log(n)) + 2 T(n/2).
This is not quite covered by the Master Theorem, but can be shown to give
T(n) = O(n log2(n)).
Alternatively, if you are more careful and have CPP take points already sorted by y-coordinate, you can reduce to O(n log(n)).
Fast Fourier Transform
We will not cover this in class.
It is a great example of a divide and conquer algorithm.
Very important algorithm. Allows you to:
Multiply n-bit numbers in O(n log2(n)) time.
Decompose a signal into frequencies.
Remove noise from signals.
It is highly recommended that you look it up in the book if you:
Have familiarity with complex numbers
Already know what a Fourier transform is
Are motivated to put in some extra time