HW01 Solution

Description

Please read the instructions carefully. You have to use the companion answer sheet (which is a llable PDF le) to type/select your answers to the questions described here. Adobe Acrobat Reader can be found at https://get.adobe.com/reader/. Hand-written assignment (or photo of it) will not be graded. Submit the lled PDF le of the answer sheet on Gradescope, following the link on Canvas. You should name your le using the format CSE310-HW02-LastName-FirstName.pdf.

Q1 (4 points) We have the recurrence relation T (n) = 8 T (n=2) + n³: Suppose that we want to use the Master method to solve T (n). We need to decide the case and derive the conclusion.

1. On the answer sheet, decide which case of the Master method this recurrence falls into, by checking the corresponding box.

2. On the answer sheet, decide the asymptotic notation of T (n) by checking the correspond-ing box.

Q2 (10 points) There are two algorithms A and B for solving the same problem. Algorithm A has a worst-case time complexity T_A(n) that satis es the recurrence relation

T_A(n) = 7 T_A(n=2) + n³ log n;

where n is the input size. Algorithm B has a worst-case time complexity T_B(n) that satis es the recurrence relation

T_B(n) = 8 T_B(n=2) + n²;

where n is the input size. Suppose that you want to use the Master method to nd the asymptotic notations for T_A(n) and T_B(n), and to decide which algorithm is faster.

1. On the answer sheet, decide which case of the Master method T_A(n) falls into, by checking the corresponding box.

2. On the answer sheet, decide the asymptotic notation of T_A(n) by checking the corre-sponding box.

3. On the answer sheet, decide which case of the Master method T_B(n) falls into, by checking the corresponding box.

4. On the answer sheet, decide the asymptotic notation of T_B(n) by checking the corre-sponding box.

5. On the answer sheet, decide which algorithm is faster by checking the corresponding box.

Q3 (4 points) This question tests your understanding of activation records as taught in class.

1. Assume that we want to apply Quicksort to sort the array A with 5 elements where the initial values of the array elements (from A[1] to A[5]) are A : 19 16 13 25 22 . How many times do we push an activation record (for quicksort or partition) onto the runtime stack before the completion of the algorithm? Note that Quicksort(A, 1, 5) is the rst activation record pushed onto the runtime stack.

2. Assume that we want to apply mergesort to sort the array A with 5 elements where the

initial values of the array elements (from A[1] to A[5]) are A : 19 16 13 25 22

• How many times do we push an activation record (for mergesort or merge) onto the runtime stack before the completion of the algorithm? Note that mergesort(A, 1, 5)

is the rst activation record pushed onto the runtime stack.

Q4 (12 points) Assume that we use Quicksort (as in the textbook) to sort the array A with 5 ele-ments where the initial values of the array elements (from A[1] to A[5]) are A : 19 16 13 25 22

• This question tests your understanding of the algorithm by following the element-wise com-parisons made in the execution of the algorithm. Here an element-wise comparison means the comparison of one element of the array with another element of the array or the key set in a particular step of the algorithm (Line 4 in Partition). Since the algorithm may move the elements of the array, you need to show the values of the elements being compared (rather than the form of A[i]). The rst element-wise comparison is

19 22?

On the answer sheet, answer the following questions by checking the corresponding box.

1. What is the 2nd element-wise comparison?

2. What is the 4th element-wise comparison?

3. What is the 6th element-wise comparison?

4. What is the 7th element-wise comparison?

In order to answer the above questions correctly, you need to execute the algorithm on the given input step by step.

Q5 (10 points) On your scratch paper, draw the portion of the decision tree for insertion sort on 5 elements a₁; a₂; a₃; a₄; a₅ that contains the path from the root node to the permutation

• a₃; a₂; a₁; a₅; a₄ >. Then answer the following questions on the answer sheet. Here the 1st node on the root to leaf (< a₃; a₂; a₁; a₅; a₄ >) path is the root node, which contains the comparison a₁ > a₂ ? .

1. What is comparison at the 2nd node on the root to leaf path?

2. What is comparison at the 3rd node on the root to leaf path?

3. What is comparison at the 4th node on the root to leaf path?

4. What is comparison at the 5th node on the root to leaf path?

5. What is comparison at the 6th node on the root to leaf path?

Q6 (12 pts) This question tests your understanding of the time complexities of sorting algorithms.

1. In the decision tree for insertion sort on n elements, what is the length of the shortest root-to-leaf path? Check the corresponding box on the answer sheet.

2. In the decision tree for insertion sort on n elements, what is the length of the longest root-to-leaf path? Check the corresponding box on the answer sheet.

3. In the decision tree for quicksort on n elements, what is the length of the shortest root-to-leaf path? Check the corresponding box on the answer sheet.

4. In the decision tree for quicksort on n elements, what is the length of the longest root-to-leaf path? Check the corresponding box on the answer sheet.

5. In the decision tree for mergesort on n elements, what is the length of the shortest root-to-leaf path? Check the corresponding box on the answer sheet.

6. In the decision tree for mergesort on n elements, what is the length of the longest root-to-leaf path? Check the corresponding box on the answer sheet.

3