Question 1:

a) Suppose you draw the decision tree for mergesort when applied to an array of 4 elements.

- What will be the exact length of the longest path in the tree? (Assume that the optimization described above is not being used.)

- What will be the exact length of the shortest path in the tree? (Assume that the optimization described above is not being used.)

- What will be the exact length of the shortest path in the tree? (Assume that the optimizationdescribed above is being used.)

b) Suppose you draw the decision tree for mergesort when applied to an array of 2^k elements. What will be the exact length of the longest path in the tree? (Assume that the optimization described above is not being used.)

Your answer should be a formula in which k is the only variable. Simplify your formula as much as possible and express it using standard mathematical notation. Use ^ as the exponentiation operator. Your formula cannot contain summations.

Write your formula as a sum or difference of terms, with higher order terms appearing before lower order terms. Include no spaces. Indicate multiplication by adjacency, not by using a multiplication symbol. Use parentheses only where your formula would mean something else if you left them out. Here are some examples:

7k^2-4k+8 (5)2^k+3k-7 

c) Suppose you draw the decision tree for mergesort when applied to an array of 2^k elements. What will be the exact length of the shortest path in the tree? (Assume that the optimization described above is not being used.)

Your answer should be a formula in which k is the only variable. Simplify your formula as much as possible and express it using standard mathematical notation. Use ^ as the exponentiation operator. Your formula cannot contain summations.

Write your formula as a sum or difference of terms, with higher order terms appearing before lower order terms. Include no spaces. Indicate multiplication, not by using a multiplication symbol. Use parentheses only where your formula would mean something else if you left them out. Here are some examples:

7k^2-4k+8 (5)2^k+3k-7

d) Suppose you draw the decision tree for mergesort when applied to an array of 2^k elements. What will be the exact length of the shortest path in the tree? (Assume that the optimization described above is being used.)

Your answer should be a formula in which k is the only variable. Simplify your formula as much as possible and express it using standard mathematical notation. Use ^ as the exponentiation operator. Your formula cannot contain summations.

Write your formula as a sum or difference of terms, with higher order terms appearing before lower order terms. Include no spaces. Indicate multiplication, not by using a multiplication symbol. Use parentheses only where your formula would mean something else if you left them out. Here are some examples:

7k^2-4k+8 (5)2^k+3k-7 

Decision Trees In this quiz, a path is any sequence of edges that leads from the root to a leaf of a tree. The length of a path is the numbe of edges it traverses. So a path from A to B to Cto D has length 3. Here is the pseudocode for standard mergesort: // Sorts A[lo .. hi] into ascending order mergesort (A, lo, hi) if (hi-lo >= 1) mid = (lo+hi)/2 mergesort (A, lo, mid) mergesort(A, mid+1, hi) merge(A, lo, mid, hi) Here is an optimized version that performs the merge operation only if the last element of the first half of the array is greater than the first element of the second half of the array: // Sorts A[lo .. hi] into ascending order mergesort (A, lo, hi) if (hi-lo >= 1) mid = (lo+hi)/2 mergesort(A, lo, mid) mergesort (A, mid+1, hi) if (A[mid] > A[mid+1] merge (A, lo, mid, hi) Decision Trees In this quiz, a path is any sequence of edges that leads from the root to a leaf of a tree. The length of a path is the numbe of edges it traverses. So a path from A to B to Cto D has length 3. Here is the pseudocode for standard mergesort: // Sorts A[lo .. hi] into ascending order mergesort (A, lo, hi) if (hi-lo >= 1) mid = (lo+hi)/2 mergesort (A, lo, mid) mergesort(A, mid+1, hi) merge(A, lo, mid, hi) Here is an optimized version that performs the merge operation only if the last element of the first half of the array is greater than the first element of the second half of the array: // Sorts A[lo .. hi] into ascending order mergesort (A, lo, hi) if (hi-lo >= 1) mid = (lo+hi)/2 mergesort(A, lo, mid) mergesort (A, mid+1, hi) if (A[mid] > A[mid+1] merge (A, lo, mid, hi)