____________________________________________________________________________________

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

maximum score.

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

{BLOCK1}

}

(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?

1

CS557AL: Algorithms

Midterm Exam

Summer 2022

____________________________________________________________________________________

(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

else

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?

GOOD LUCK!

ATTN: Submit your Final Exam Report in electronic format (PDF or MS Word)

2

Purchase answer to see full

attachment