Assume that you are given the following linear time algorithm: BSTNode *BuildBST(A, n): It takes an array and its size as arguments, builds a binary search tree, and returns a pointer to its root in θ(n) time. A BSTNode structure contains pointers LC, RC of type BSTNode* pointing to the left child and right child of that node respectively. In Step 1 above, you used the above function to write pseudocode to output the array in ascending order in linear time. Step 2: Explain in great detail why the algorithm you wrote is a linear time algorithm. 

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

In this question, you will use dynamic programming to determine the longest common subsequence of   and . Step 3. Provide the length of the longest common subsequence: [length]Also give the longest common subsequence: [lcs] Format: If is your answer for the longest common subsequence, you would enter your answer in all caps with no spaces: RJQ

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)