PLEASE DO NUMBER THREE
PLEASE DO NUMBER THREE
PLEASE DO NUMBER THREE
Analysis of Algorithm
- Please Do Number Three Please Do Number Three Please Do Number Three Please Do Number Three Analysis Of Algorithm 1 (316.04 KiB) Viewed 45 times
PLEASE DO NUMBER THREE PLEASE DO NUMBER THREE PLEASE DO NUMBER THREE PLEASE DO NUMBER THREE Analysis of Algorithm
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
PLEASE DO NUMBER THREE PLEASE DO NUMBER THREE PLEASE DO NUMBER THREE PLEASE DO NUMBER THREE Analysis of Algorithm
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
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
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!