Answer Happy

PLEASE DO NUMBER THREE
PLEASE DO NUMBER THREE
PLEASE DO NUMBER THREE
PLEASE DO NUMBER THREE
Analysis of Algorithm
Problem 1. (Category: Divide and Conquer] Consider a tennis tournament where each of the n participants (numbered 1..n) plays every other player exactly once; each such match will result in a victory for one of the players, as recorded in array M[1..n, 1..n] where M[i,j] = 1 iff player i won the match against player j. Our goal is to produce a ranking for all n players, where a ranking is defined as a list R[1..q] (with q <n) of different players such that for all i E 1..q-1, R won the match against Rſi + 1]. To illustrate, let us consider the array M given by 2 8 Pico 0 1 1 2 3 0 1 x 7 1 1 0 X 0 3 4. 1 X 1 1 0 1 1 0 0 0 0 0 4 1 1 1 X 0 1 1 1 0 0 1 1 5 6 7 8 5 6 0 0 1 1 1 0 1 0 X 1 0 x 0 0 1 1 0 1 1 X 1 1 1 0 0 0 0 X 000 where [7, 4] is a ranking (since player 7 has beaten player 4), (2, 3] is a ranking, and even (1, 8, 5, 6] is a ranking (since player 1 has beaten player 8 who has beaten player 5 who has beaten player 6). It turns out that it is always possible to merge rankings for two disjoint set of players into a ranking for the union of those players. For the above matches, we can for example merge [7, 4] and [2, 3]: not by putting one in front of the other, since neither (7,4,2,3] nor [2,3,7,4) are valid rankings, but into [2, 7, 3, 4] by checking 4 and 3 first, 3 beats 4, so we write down 4 first as the last one in the new ranking (X, X, X, 4]), and then we check 3 with 7, 7 beats 3, so we write down 3 before 4 ([X, X, 3, 4]), and finally 2 beats 7, so we write down ([X, 7, 3, 4]), and finally we write down 2 ([2, 7, 3, 4]). (35 points) 1. Merge [2, 7, 3, 4) and (1, 8, 5, 6) into a ranking (such that player 2 is still ranked higher than player 7 who is ranked higher than 3 who is ranked higher than 4. And similarly for the ranking as in (1, 8, 5, 6) should be kept). 2. Sketch a general algorithm Merge(A[1..p], B[1..q]) for merging a ranking for p players and a ranking for a players, into a ranking for p+q players (such that if player i is ranked higher than player j in one of the input rankings then i is still ranked higher than j in the output ranking). You can just give the pseudocode and analyze the running time of it. 3. Based on the “divide and conquer” paradigm, write a recursive algorithm Rank(P[1..n]) to construct a ranking for n players, given (as implicit parameter) an matrix (2D dimension array) M[1..n, 1..n], by making use of the merging algorithm from the previous question. You can just give the pseudocode and its running time. 1