Author: Anonymous

In this question, you will construct the max heap that results from using BUILD-MAX-HEAP to create a heap from the following array:  . Steps 1-5 were performed above, yielding the finished max heap in Step 5. Now fill in the array A to give the array representation of the max heap. A[ 1 ] A[ 2 ] A[ 3 ] A[ 4 ] A[ 5 ] A[ 6 ] A[ 7 ] A[ 8 ] A[ 9 ] A[ 10 ] A[ 11 ] [12] [10] [11] [7] [8] [5] [9] [6] [2] [4] [3]

In this question, you will find the maximum subarray of the array A = [1, -2, 8, -25, 3, 4, -1, 3] using the θ(nlog(n)) divide and conquer algorithm discussed in class. Step 1: Give the algorithm FIND-MAXIMUM-SUBARRAY(A, low, high) which finds the maximum subarray of A from starting index “low” to ending index “high”, and returns the maximum sum. That is, complete the code following the right brace “{“: FIND-MAXIMUM-SUBARRAY(A, low, high){

Use the Substitution Method to prove that the solution to  T(n) = 2T(n/3) + n  is O(n).

A point (4, -3) on the terminal side of angle θ is given. Find the exact value of the indicated trigonometric function. Find cos θ and csc θ.

This Bonus Question is worth 10 points if answered correctly, and will be added to any final score which you earn from the base 100 points possible.  If you choose not to attempt it, then it will not take any points away from the base 100 points which you can earn (i.e. it will add “0”, as listed on Canvas). Give a linear time algorithm for the maximum subarray problem.  Also justify the correctness and time complexity, at least informally.  Hint:  Solve A[1 … j+1] using information from the solution of A[1 … j].  You may need more than just the optimum solution for A[1 … j].

In this question, you will construct the max heap that results from using BUILD-MAX-HEAP to create a heap from the following array:  . Step 1 is constructing the initial heap.  Fill in tree which results after constructing the initial heap below. [A5] / \ [A8] [A12] / \ / \ [A7] [A3] [A11] [A9] / \ / \ [A6] [A2] [A4] [A10]    

Use the Master Theorem to give tight asymptotic bounds for the following recurrence: T(n) = 3T(n/2) + n2log(n)

In this question, you will find the maximum subarray of the array A = [1, -2, 8, -25, 3, 4, -1, 3] using the θ(nlog(n)) divide and conquer algorithm discussed in class. Step 6: Use Master Theorem to demonstrate how the asymptotic bound θ(nlog(n)) is achieved for T(n) given in Step 5.  (Note: T(n) must be correct in order to receive credit in this step.)

Use the Master Theorem to give tight asymptotic bounds for the following recurrence: T(n) = 3T(n/2) + n2log(n)

Solve the problem. For the equation y = – 3cos(2x – 2π), identify (i) the amplitude, (ii) the phase shift, and (iii) the period. Graph one cycle of the function on your paper. Be sure to label each value of x on the x axis and each value of y on the y-axis.