Home /
Expert Answers /
Computer Science /
6-15-points-examine-the-procedure-does-something-below-and-answer-the-following-questions-proced-pa491

6. [15 points] Examine the procedure DOES_SOMETHING below and answer the following questions. Procedure DOES_SOMETHING(A,x,y) //Input: An array A[0 … n-1] of integers between x and y (x <= y) 1. for j = 0 to y – x do B[j] = 0; 2. for i = 0 to n – 1 do B[A[i] - x] = B[A[i] - x] + 1; 3. for j = 1 to y – x do B[j] = B[j – 1] + B[j]; 4. for i = n – 1 downto 0 do 5. j = A[i] - x; 6. C[B[j] - 1] = A[i]; 7. B[j] = B[j] - 1; 8. return C;

a. What is the function of the procedure DOES_SOMETHING? (5 points)

b. What is the worst-case running time of the procedure? Justify your answer by applying analysis framework. (5 points)

c. If A = [6, 0 2, 0, 1, 3, 4, 6, 1, 3, 2],

what is the output of B after executing statement 1? (1 point)

what is the output of B after executing statement 2? (1 point)

what is the output of B after executing statement 3? (2 point)

what is the output of C after executing the procedure? (1 points)

6. [15 points] Examine the procedure DOES_SOMETHING below and answer the following questions. Procedure DOES_SOMETHING \( (\mathbf{A}, \mathbf{x}, \mathbf{y}) \) //Input: An array \( A\left[\begin{array}{ll}0 & \ldots\end{array}-1\right] \) of integers between \( \mathrm{x} \) and \( \mathrm{y}(\mathrm{x}<=\mathrm{y}) \) 1. For \( j=0 \) to \( y-x \) do \( B[j]=0 \); 2. for \( i=0 \) to \( n-1 \) do \( B[A[i]-x]=B[A[i]-x]+1 \); 3. for \( j=1 \) to \( y-x \) do \( B[j]=B[j-1]+B[j] \); 4. for \( i=n-1 \) downto 0 do 5. \( j=A[i]-x \); 6. \( \quad C[B[j]-1]=A[i] \); 7. \( \quad B[j]=B[j]-1 \); 8. return \( C \); a. What is the function of the procedure DOES_SOMETHING? (5 points) b. What is the worst-case running time of the procedure? Justify your answer by applying analysis framework. (5 points) c. If \( \boldsymbol{A}=[6,02,0,1,3,4,6,1,3,2] \), what is the output of \( \mathbf{B} \) after executing statement 1? (1 point) what is the output of \( \mathbf{B} \) after executing statement 2? (1 point) what is the output of \( \mathbf{B} \) after executing statement 3 ? (2 point) what is the output of \( \mathbf{C} \) after executing the procedure? (1 points)

The function of the procedure DOES_SOMETHI