Fall 2020 CIS 606 Midterm You have to TYPE your answers and use a tool to draw figures. Save them in a file called mid.pdf. The cover page should contain your picture, name and your grails login id. Use the following command on grail to submit it BEFORE noon on Oct 20 (EST): turnin -c cis606s -p mid mid.pdf WARNING: Finding the solutions from Internet or discussing with any other person will be considered as CHEATING. 1. Write True or False at the beginning of your answer and give an explanation for each of the following statements. (a) ( 9 points) (True or False) 5n+5 = O(5n) (b) ( 9 points) (True or False) In the algorithm SELECT which uses the median of medians, the input elements are divided into groups of 5. The algorithm can still work in linear time if they are divided into groups of 9. (c) ( 9 points) (True or False) Finding a closest pair of points in 2 dimensions would be harder (in terms of time complexity) if the distance between 2 points (x1, y1) and (x2, y2) were defined as |x1 ? x2| + |y1 ? y2|. Solve the following recurrence by making a change of variables. T (n) = 8T (?n) + 1 3. ( 15 points) Using Figure 6.3 as a model, illustrate the operation of BUILD-MAX-HEAP on the array A = h3, 2, 15, 9, 70, 18, 5, 33, 8i. 4. ( 10 points) Trace in detail how the OS Select(T.root, 18) operates on the following RB tree T . Given two arrays A[1..n] and B[1..n], the elements in the array A are sorted in de- scending order and the elements in the array B are sorted in ascending order. Consider the problem of finding the median of all 2n elements in A and B. (a) Design an algorithm with merging. What is the running time of your algorithm? (b) Design an efficient recursive algorithm based on the prune-and-search approach. You may use a figure to illustrate your algorithm. Give the recurrence relation for the time complexity of your algorithm. Solve your recurrence using the master theorem. Input: array P [1..n] and array Q[1..n], where n is power of 2. Output: array R[1..(2n ? 1)] Two binary operators and ? will be used for calculations. Both are associative. The operation is distributive over ? and has higher precedence than ?. The operator will be used to calculate each pair of operands P [i], 1 ? i ? n, and Q[j], 1 ? j ? n (i.e. one operand in P and the other in Q). The result of P [i] Q[j] will be accumulated into R[i + j ? 1] by using the ? operation. The following is a loop-based algorithm: for i = 1 to n for j = 1 to n R[i + j ? 1] = R[i + j ? 1] ? P [i] Q[j] endfor endfor For example, given P [1..4] and Q[1..4], the output result R[1..7] will be: R[1] = P [1] Q[1] R[2] = P [1] Q[2] ? P [2] Q[1] R[3] = P [1] Q[3] ? P [2] Q[2] ? P [3] Q[1] R[4] = P [1] Q[4] ? P [2] Q[3] ? P [3] Q[2] ? P [4] Q[1] R[5] = P [2] Q[4] ? P [3] Q[3] ? P [4] Q[2] R[6] = P [3] Q[4] ? P [4] Q[3] R[7] = ? P [4] Q[4] Use the Divide and Conquer approach to develop an efficient algorithm which uses fewer operations. You may draw a figure to illustrate your idea. Give the recurrence relation for the time complexity of your algorithm. Solve your recurrence using the master theorem. Hint: Split the array P [1..n] into two subarrays A[1.. n ] and B[1.. n ]. Also split the 2 2 array Q[1..n] into two subarrays C[1.. n ] and D[1.. n ]. 2 2
Looking for solution of this Assignment?
WHY CHOOSE US?
We deliver quality original papers |
Our experts write quality original papers using academic databases.We dont use AI in our work. We refund your money if AI is detected |
Free revisions |
We offer our clients multiple free revisions just to ensure you get what you want. |
Discounted prices |
All our prices are discounted which makes it affordable to you. Use code FIRST15 to get your discount |
100% originality |
We deliver papers that are written from scratch to deliver 100% originality. Our papers are free from plagiarism and NO similarity.We have ZERO TOLERANCE TO USE OF AI |
On-time delivery |
We will deliver your paper on time even on short notice or short deadline, overnight essay or even an urgent essay |