CSE 531 Homework Assignment 2Due in class on Tuesday, Sep 25.September 9, 2007There are totally 5 problems, 10 points each. You should do them all. We will grade only4 problems chosen at my discretion. If it so happens that you don’t do one of the problem wedon’t grade, then no points will be deducted.Problem 1. A climatologist has a large data set of tem peratures recorded daily for more thana century. To study global warming trend, he would like to find a p eriod during which thedaily average temperature was increased the most. Specifically, he has an array of averagetemperatures t = [t1, t2, . . . , tn], where tiis the average te mperature of the ith day on record.He would like to find a pair of day (i, j) for which i < j and tj− tiis the largest among all suchpairs. Help him design an O(n lg n)-time divide-and-conquer algorithm to find such a pair.Problem 2. An FTP server has a large batch of file downloading requests to process. Thereare n requests in the batch. For 1 ≤ i ≤ n, the ith request came at time tiasking for a file ofsize fibytes. The tiare distinct and are not sorted in any order. The total number of requestedbytes is F =Pni=1fi. Unfortunately, the server can only serve F/2 bytes at this moment.The server wants to serve the maximum amount of data, while honors requests which comefirst. Hence, the server needs to find a request k, for some 1 ≤ k ≤ n, such that the total numberof bytes requested before tkis no more than F/2, and that the total number of bytes requestedafter tkis strictly less than F/2. (We do not count request k as before or after tk.)(a) Show that such a request k always exists.(b) De vise a O(n)-time algorithm to find such a request k.(After tkis found, a simple scan through all requests will pick out requests to be processed.Hint: linear-select might help.)Problem 3. Let t = [t1, . . . , t2n−1] be any array of 2n − 1 real numbers. For each such t, definean n × n matrix At= (aij)1≤i,j≤nby setting aij= ti−j+n. This type of matrices arise quitenaturally in the study of discrete time random proces se s, when we often have to perform matrixoperations involving these matrices.(a) Let v be any column vector with n coordinates, i.e. v ∈ Rn. Show how to compute theproduct Atv in time O(n lg n) for any t and v.(b) Le t s, t be any two arrays of 2n − 1 real numbers. Show how to compute the productAsAtin time O(n2).Problem 4. We are given n intervals on the real line, i.e. [ai, bi], ai≤ bi, for 1 ≤ i ≤ n.Each interval overlaps at least d − 1 other intervals, for some 1 ≤ d ≤ n. Moreover, no intervalcontains another.You want to crazy-sort these intervals in the following sense: you are to produce a permu-tation (i1, i2, . . . , in) of {1, . . . , n} such that, for all j ∈ {1, . . . , n} there exists a cj∈ [aij, bij]satisfying c1≤ c2≤ · · · ≤ cn. Devise an O(n lgnd)-time algorithm to crazy-sort these intervals.1Problem 5. The Buffalo Tennis Association is ab out to establish a new Tennis tournamentcalled the Bufopen. The organizers do not agree with the current “binary tree ” format of theGrand Slams. They think it is unfair to the second best player as he/she could have been beatenin rounds before the final match by the champion, and thus does not have a chance to be therunner-up. (Pretty much everyone belonging to Federer’s branch is out of luck. Think Rodick!)Here we assume the players’ strengths are totally ordered, namely if player A beats playerB, and B beats C, then we can safely conclude that A is stronger than C without playing C.Consequently, the organizers of the Bufopen ask the students of CSE 531 to design atournament which can decide the best and the second best players in as few matches as possible.1. Design such a tournament which uses only n + dlg ne − 2 matches, where n ≥ 2 is the totalnumber of players.2. If we also want to determine the third best player, in addition to the first and the secondbest, how many matches do you need in total?3. Suppose there is a tournament format which determines the mth best player X, where1 < m ≤ n. Show that after the tournament, one can identify the set of m − 1 players whoare stronger than X without any additional matches.(Hint: Let S be the set of players who have beaten X directly or indirectly, then allplayers in S are stronger than X. Prove that if |S| < m − 1, then there is some otherordering of players’ strengths for which X is no longer the mth strongest, but the matches’results are exactly the same as