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

(Solved): 6. [15 points] Examine the procedure DOES_SOMETHING below and answer the following questions. Proced ...

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)

We have an Answer from Expert