CS557AL Midterm Exam
Studentâ€™s Name: _____________________________________
All work must be your own. Turn in an electronic format (PDF or MS Word file) and any
supporting programs (source code and test cases). Show your work in all the details for
NOTE: No extensions or late submissions for anything other than major emergency.
What are the theta values for the recurrences given below in Q1-Q5? (Any method could be used
to find the solution and to prove it. Show your work in details)
(Q1) [5 pts.] T(n) = 4T(n/4) + n
(Q2) [5 pts.] T(n) = T(n-4) + n
(Q3) [5 pts.] T(n) = 25T(n/5) + n**3
(Q4) [5 pts.] T(n) = 7T(n/2) + n**2
(Q5) [10 pts.] T(n) = T(n/3) + T(n/4) + n**2
(Q6) [10 pts.] Exactly how many times is BLOCK1 executed in turns of the parameter n?
for i = 1, n
for j = i, n
(Q7) [15 pts.] Assume the complete binary tree numbering scheme used by Heapsort (with the
root location marked as â€œ0â€) and apply the Heapsort algorithm to the following key
sequence (3,22,5,16,10,2,8). Answer the following questions:
(a) What value is in the root node of the INITIAL STRUCTURE (NOT HEAP!)?
(b) What value is in location 4 of the initial HEAP?
(c) After a single deletion (of the parameter at the heap root) and tree restructuring,
what value is in location 4 of the new HEAP?
(Q8) [10 pts.] What is the average performance of Quicksort assuming every input permutation
is equally likely?
(Q9) [10 pts.] What is the worst case performance of Quicksort?
(Q10) [25 pts.] Implement the following algorithm (it means create the code in any
programming language that you are familiar with):
Let C(n,k) be the number of combinations of n items taken k at a time.
C(n,k) = 1 if n = k or k = 0
C(n,k) = C(n – 1,k – 1) + C(n – 1,k)
Implement this algorithm (above) in two ways:
(a) recursive variant
(b) non-recursive variant.
a) What is the order (THETA) of this algorithm worst case if recursion is used?
b) What is the order (THETA) of the non-recursive version of this algorithm?
ATTN: Submit your Final Exam Report in electronic format (PDF or MS Word)
Purchase answer to see full