1. Consider the following generalization of the Blum-Floyd-Pratt-Rivest-Tarjan SELEcT algo- rithm we discussed in class. It partitions the input array inton/71 blocks of size 7 instead of In/5] blocks of size 5 but is otherwise identical. In the pseudocode below, the necessary modifications are indicated in red MOM7SELEC if n r else Our goal is to analyze the running time of this algorithm. (a) In the original algorithm (with blocks of size 5), we observed that 3n/10 elements were smaller than the median-of-medians. How many elements are smaller than the median-of-medians when we use blocks of size 7? (b) Using the previous observation, and the fact that the algorithm takes linear time outside the recursion calls, we observed the worst-case running time of the original selection algorithm to obey the recurrence T(n)- T(n/5) + T(7n/10) +n. State a recurrence for the running time of MoM7SELecT (c) To solve the running time recurrence, we need to sum over all node values in the recursion tree. What is the sum of the nodes values on the ith level of the tree (the root is at level 0)? CS 4349.400 Homework R (due October 24) Fall 2018 (d) Finally, express the asymptotic solution to your recurrence using big-O notation and justify your answer. If your previous answers are correct, then the solution to your recurrence should be O(n) 1. Consider the following generalization of the Blum-Floyd-Pratt-Rivest-Tarjan SELEcT algo- rithm we discussed in class. It partitions the input array inton/71 blocks of size 7 instead of In/5] blocks of size 5 but is otherwise identical. In the pseudocode below, the necessary modifications are indicated in red MOM7SELEC if n r else Our goal is to analyze the running time of this algorithm. (a) In the original algorithm (with blocks of size 5), we observed that 3n/10 elements were smaller than the median-of-medians. How many elements are smaller than the median-of-medians when we use blocks of size 7? (b) Using the previous observation, and the fact that the algorithm takes linear time outside the recursion calls, we observed the worst-case running time of the original selection algorithm to obey the recurrence T(n)- T(n/5) + T(7n/10) +n. State a recurrence for the running time of MoM7SELecT (c) To solve the running time recurrence, we need to sum over all node values in the recursion tree. What is the sum of the nodes values on the ith level of the tree (the root is at level 0)? CS 4349.400 Homework R (due October 24) Fall 2018 (d) Finally, express the asymptotic solution to your recurrence using big-O notation and justify your answer. If your previous answers are correct, then the solution to your recurrence should be O(n)
