Once upon a time, in a picturesque town, a highly competitive examination was held, with substantial...

 

Transcribed Image Text:

Once upon a time, in a picturesque town, a highly competitive examination was held, with substantial rewards to the victors. It attracted huge numbers of people to join from all over the world. As one of the participants in the competition, Bob was eager to find out his result. However, the only information Bob has is his rank and a list of the (anonymous) student scores that are stored in an array S. He designed the algorithms below to find his score from his ranking. Algorithm 1 findMyScore 1: Input: S = [81,82,81]: a list of student scores; l: the length of the list; re {ala € N*,ze [1,1]}: the rank. 2: Initialization: i← 1. 3: if 1 = 1 then score 5: else if l = 2 then 6: 7: 8: 9: 10: else 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: if S[1] > S[2] then 7: 8: 9: 10: S[1], S[2] = S(2], S[1] // sort array end if score S[r] // find the score as the r-th element in the sorted array S[r] // base case, if there is only one element in the array, the score is that element. while i ≤l do pivot = S[i] rank, Sget Rank (S, 1, pivot) if rank 1/3 and rank <21/3 then if rank = r then score + pivot else if rank <r then score = find MyScore(S[rank :], 1-rank +1,r-rank + 1) // find score with rank r- rank in the last 1-rank + 1 elements. else end if end if 25: 26: i+i+1 27: end while 28: end if 29: Return score. else score = find MyScore(S[: rank],i,r) // find the score with rank r in the first i elements. break Algorithm 2 get Rank = 1: Input: S [81, 82, 2: Initialization: S' 3: while i ≤l do ← 4: if S[i] < n then 5: 6: S'[left] = S[i] left = left + 1 end if i+i+1 S'[right] = S[i] right right-1 = 81]: a list of numbers; 1: the length of the list; n: a number. [0,0,...,0]: a list of zeros with length l; left+1; right+l; i+ 1. 11: 12: end while 13: Return left, S'. (a) To check if his algorithm works, Bob tried a toy example: the scores S = [66, 95, 13, 7, 14], and the rank = 3. Briefly explain how Algorithm 1 processes the input to obtain Bob's score. (b) Assuming that the class is huge, with thousands of students, Bob wanted to have a rough idea about how long the algorithm would take as a function of the problem size 1. (i) Derive the average-case time complexity of Algorithm 1 in terms of (Big Theta). (ii) Derive the worst-case time complexity of Algorithm 1 in terms of (Big Theta). When doing the calculations, you may assume: (1) No two scores are the same. (2) The rank of a score is the number of scores smaller or equal to it. (3) The list index starts from 1, i.e., S[1] denotes the first element in the list S. (4) It is ok to ignore the ceiling and floor operation in , O and calculation. (5) The scores are randomly and independently distributed, i.e., any given score S[i] is ranked j th with probability of 1/1, where 1 ≤ i ≤l and 1 ≤ i ≤l, where l is the number of scores. Once upon a time, in a picturesque town, a highly competitive examination was held, with substantial rewards to the victors. It attracted huge numbers of people to join from all over the world. As one of the participants in the competition, Bob was eager to find out his result. However, the only information Bob has is his rank and a list of the (anonymous) student scores that are stored in an array S. He designed the algorithms below to find his score from his ranking. Algorithm 1 findMyScore 1: Input: S = [81,82,81]: a list of student scores; l: the length of the list; re {ala € N*,ze [1,1]}: the rank. 2: Initialization: i← 1. 3: if 1 = 1 then score 5: else if l = 2 then 6: 7: 8: 9: 10: else 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: if S[1] > S[2] then 7: 8: 9: 10: S[1], S[2] = S(2], S[1] // sort array end if score S[r] // find the score as the r-th element in the sorted array S[r] // base case, if there is only one element in the array, the score is that element. while i ≤l do pivot = S[i] rank, Sget Rank (S, 1, pivot) if rank 1/3 and rank <21/3 then if rank = r then score + pivot else if rank <r then score = find MyScore(S[rank :], 1-rank +1,r-rank + 1) // find score with rank r- rank in the last 1-rank + 1 elements. else end if end if 25: 26: i+i+1 27: end while 28: end if 29: Return score. else score = find MyScore(S[: rank],i,r) // find the score with rank r in the first i elements. break Algorithm 2 get Rank = 1: Input: S [81, 82, 2: Initialization: S' 3: while i ≤l do ← 4: if S[i] < n then 5: 6: S'[left] = S[i] left = left + 1 end if i+i+1 S'[right] = S[i] right right-1 = 81]: a list of numbers; 1: the length of the list; n: a number. [0,0,...,0]: a list of zeros with length l; left+1; right+l; i+ 1. 11: 12: end while 13: Return left, S'. (a) To check if his algorithm works, Bob tried a toy example: the scores S = [66, 95, 13, 7, 14], and the rank = 3. Briefly explain how Algorithm 1 processes the input to obtain Bob's score. (b) Assuming that the class is huge, with thousands of students, Bob wanted to have a rough idea about how long the algorithm would take as a function of the problem size 1. (i) Derive the average-case time complexity of Algorithm 1 in terms of (Big Theta). (ii) Derive the worst-case time complexity of Algorithm 1 in terms of (Big Theta). When doing the calculations, you may assume: (1) No two scores are the same. (2) The rank of a score is the number of scores smaller or equal to it. (3) The list index starts from 1, i.e., S[1] denotes the first element in the list S. (4) It is ok to ignore the ceiling and floor operation in , O and calculation. (5) The scores are randomly and independently distributed, i.e., any given score S[i] is ranked j th with probability of 1/1, where 1 ≤ i ≤l and 1 ≤ i ≤l, where l is the number of scores.

Answer rating: 100% (QA)

a In order to get Bobs score Algorithm 1 processes the input as follows Nondecreasing orderly sortin... View the full answer