subject : analysis of algorithms
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[ii 1 iff player iwon the match against player j. Our goal is to produce a ranking for all n players, where a ranking is defined1 as a list R[1..q] (with q S n) of different players such that for all jE 1..q-1, R[i won the match against Ri+1]. To illustrate, let us consider the array M given by 20 X 01 0 0 1 1 3 0 1 X 1 01 0 1 4 0 0 0 X 0 1 0 0 50 1 1 X 0 0 6 0 1 0 0 X1 0 70 0 1 1 0 0 X 0 8 0 0 0 1 1 X where [7,4] is a ranking (since player 7 has beaten player 4), [1,3] is a ranking, and even [2,8,6,5] is a ranking (since player 2 has beaten player 8 who has beaten player 6 who has beaten player 5) It turns out (perhaps surprisingly) that there will always exist at least one ranking. This is due to the fact 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 [1,3]: not by putting one in front of the other, since neither [7,4,1,3] nor [1,3,7,4] are valid rankings, but into [1,7,3,4] a) Write a general algorithm that merges a ranking for p players with a ranking for q players, producing a ranking for p + q players (such that if player j is ranked higher than player j in one of the input rankings then jis ranked higher than j also in the output ranking) Prove (a key part may be to state a suitable loop invariant) that your algorithm always produces a ranking. Also state the asymptotic running time of your algorithm (in terms of p and q) b) Based on the "divide and conquer" paradigm, write a recursive algorithm Rank to construct a ranking for n players, given an array M[1.n,1..n]. Analyze the running time of your algorithm (in terms of n), by stating and solving a recurrence c) Use your results from Questions a and bto state a general result about paths in directed graphs. (Your result should say that under certain conditions, a certain kind of path exists.) 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[ii 1 iff player iwon the match against player j. Our goal is to produce a ranking for all n players, where a ranking is defined1 as a list R[1..q] (with q S n) of different players such that for all jE 1..q-1, R[i won the match against Ri+1]. To illustrate, let us consider the array M given by 20 X 01 0 0 1 1 3 0 1 X 1 01 0 1 4 0 0 0 X 0 1 0 0 50 1 1 X 0 0 6 0 1 0 0 X1 0 70 0 1 1 0 0 X 0 8 0 0 0 1 1 X where [7,4] is a ranking (since player 7 has beaten player 4), [1,3] is a ranking, and even [2,8,6,5] is a ranking (since player 2 has beaten player 8 who has beaten player 6 who has beaten player 5) It turns out (perhaps surprisingly) that there will always exist at least one ranking. This is due to the fact 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 [1,3]: not by putting one in front of the other, since neither [7,4,1,3] nor [1,3,7,4] are valid rankings, but into [1,7,3,4] a) Write a general algorithm that merges a ranking for p players with a ranking for q players, producing a ranking for p + q players (such that if player j is ranked higher than player j in one of the input rankings then jis ranked higher than j also in the output ranking) Prove (a key part may be to state a suitable loop invariant) that your algorithm always produces a ranking. Also state the asymptotic running time of your algorithm (in terms of p and q) b) Based on the "divide and conquer" paradigm, write a recursive algorithm Rank to construct a ranking for n players, given an array M[1.n,1..n]. Analyze the running time of your algorithm (in terms of n), by stating and solving a recurrence c) Use your results from Questions a and bto state a general result about paths in directed graphs. (Your result should say that under certain conditions, a certain kind of path exists.)
