1 Divide and Conquer
A group of n Ghostbusters is battling n ghosts. Each Ghostbuster is armed with a proton pack, which shoots a stream at a ghost, eradicating it. A stream goes in a straight line and terminates when it hits the ghost. The Ghostbusters decide upon the following strategy. They will pair off with the ghosts, forming n Ghostbuster-ghost pairs, and then simultaneously each Ghostbuster will shoot a stream at his chosen ghost. As we all know, it is very dangerous to let streams cross, and so the Ghostbusters must choose pairings for which no streams will cross. Assume that the position of each Ghostbuster and each ghost is a fixed point in the plane and that no three positions are collinear.
i Argue that there exists a line passing through one Ghostbuster and one ghost such the number of Ghostbusters on one side of the line equals the number of ghosts on the same side. Describe how to find such a line in O(n log n) time.
ii Give an O(n2 log n)-time algorithm to pair Ghostbusters with ghosts in such a way that no streams cross.
Answer:
i -ii: We assume that all the points in the plane are not in same X or Y axis using mark to stand for ghostbuster or ghosts(mark 0 stand for ghostbuster and mark 1 stand for ghosts).(This can not affect the problem because when we get the same X or Y , we can add or minus a very little value to let all points’ X or Y are not same). First we get the deepest point (in other word, the  minimum Y value). Also we compute the other points with this point ‘s angle in X axis and sort these other points with this angle. Then we iterate in this order, and get another mark which is different from the deepest point's mark also we line this two point ,and compute the bottom mark 0 's number and mark 1's number, they are the same , then we find the pair which is the deepest point and the iterate point. So we use this line to divide all points into two parts and  recursive do the same above operation until the points' number is only 2 then we only get the line to connect this two points.
Algorithm:
Get_Pair(points[1-2N])
    if N>1
        initial a array points[1-2N] stand for the points of  ghostbusters and ghosts
        find the deepest point min_Point in the array points
        initial the pair_Point and the index with 0
        get the other 2N-1 points with this min_Point 's angle in X axis and sort these angles
        initial num1 with 0 stand for the number of the other 2N-1 points which's mark is same  with min_Point
        initial num2 with 0 stand for the number of the other 2N-1 points which's mark is not same with min_Point
        for i=1 to 2N-1
            if min_Point's mark is same with points[i]'s mark
                num1++
            else
                num2++
            endif
            if num1+1==num2
                get this point  pair_Point
                index=i
                break;
            endif
        endfor
        print this pair (min_Point,pair_Point)
        using pair_Point to divide points into two parts point_one[1-index-1] and point_two[index+1-2*N]
        Get_Pair(point_one[1-index-1])
        Get_Pair(point_two[index+1-2*N])
    else
        get the line to connect this two points
    endif
We will prove this algorithm is O(n log n) time, first we get the deepest point in O(n) time, next we compute the other points with this deepest point 's angle in X axis in O(n) time, we use quick_sort to sort these n angles in O(n log n). Last we iterator these angles in O(n) to find the pair. So all time we consume is only O(n log n) time.
Next we will prove this algorithm always can find the pair. Now we assume the deepest point stand for the  Ghostbusters using mark=0, so above this point, we have n-1 Ghostbusters(mark=0) and n Ghosts(mark=1). So we can sort n-1 0 and n 1 in whole arrangement, no matter how we sort, we can get a index in 1 , which before this 1 we have the same number of 0 and 1.  We can replace this problem with a new problem, we have a road for (0,0) point to (n-1,n) point , we only can move the one step in the X or Y direction. No matter which road we have, we must cross the line Y=X it means we must get the Ghost. Before this ghost, we have the same number of ghosts and ghostbusters.sort of in order
Last, we will prove that solving this problem is O(n2 log n).
Easily, we get the T(n)=2*T(n/2)+O(n log n).
We use mathematical induction for assuming that T(n)<= O(n2 log n)
n=1, T(1)=O(n log n)<=O(n2 log n)
assume n<k T(n)<=O(n2 log n)
then n=k, T(k)=2*T(k/2)+O(k log k)<=2*O(k2 log (k/2)/ 4)+O(k log k)
                        =O(k2 log(k/2) /2)+O(k log k)
                        <=O(k2 log k)
2 Divide and Conquer
You are interested in analyzing some hard-to-obtain data from two separate databases. Each database contains n numerical values-so there are 2n values total-and you may assume that no two values are the same. You’d like to determine the median of this set of 2n values, which we will define here to be the nth smallest value.
However, the only way you can access these values is through queries to the databases. In a single query, you can specify a value k to one of the two databases, and the chosen database will return the kth smallest value that it contains. Since queries are expensive, you would like to compute the median using as few queries as possible.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。