Algorithm代做-CIS 313 FINAL EXAM

Algorithm代做：这是一个涉及复杂度方面的算法题目

Name:

Score:

1

15

2

15

3

15

4

15

5

15

6

15

7

15

um

105

CIS 313 FINAL EXAM

Please print your name at the top of the page. The following eight pages contain seven problems with weight (approximately equal to the time needed, in minutes) given within brackets [15]. Please write your answers in the space provided; the amount of space corresponds to the expected length of the answer. You may want to show intermediate steps for partial credit. A good strategy may be to read all the problems first, and then start with those that seem to be easiest.

Please write legibly!

1. [15] To prove thatf(n) O(g(n)), or equivalentlyg(n)(f(n)), one has to exhibit two constants, candn 0 such thatf(n)cg(n) for allnn 0. For part a and b below answer yes or no and provide a proof of your answer.

(a)Forg 1 , g 2 O(g(n)), f(n) =g 1 (n) +g 2 (n)O(g(n)). Answer:

(b)min{f(n), g(n)}(f(n) +g(n)) Answer:

(c)What is the time complexity of the following code fragment? Give tight upper and lower bounds.
m:=0;
for(int i=0; i<n; i++)
for(int j=0; j<n-i; j++)
for(int k=0; k<i; j++)
m++;

T(n)

2. [15] LetTbe a (min) heap storingnkeys. Give an efficient Algorithm for reporting all the keys inT that are smaller than or equal to a given query keyx(which is not necessarily in T). The keys do not need to be reported in sorted order. Ideally, your algorithm should run inO(k) time, wherekis the number of keys reported.

3. [15] Regarding red-black trees

(a) From the RB tree of figure 1 (dotted lines mean red), delete 30.
(b) Again from the RB tree of figure 1 (the original one, before part (a)), delete 1.

• Figure 1: red-black tree for question

4. [15] Put the following values into an initially empty (2,4)-tree:

15 , 6 , 12 , 30 , 22 , 17 , 10 , 5 , 9 , 14 , 23 , 1 , 17 , 29 , 18 , 24 , 7 , 26 , 35 , 33 , 27.

5. Regarding splay trees

(a) Insert into an initial empty splay tree the values

1 , 5 , 8 , 7 , 3 , 2.

(b) then delete 3

6. [15] The QuickSort algorithm in the text uses the last element of the input sequence as the pivot in a partition subroutine.

(a)Use the decision tree to model operation of a sorting method on three (n= 3) elements as a
comparison-based sorting algorithm.

(b)What is the running time QuickSort on an already sorted sequence?

(c)Show that the best-case time complexity of QuickSort is (nlogn).

7. [15] Give a linear (O(n)) time algorithm sortingnvalues in range 0..n^3 1. (Hint: represent a value xas (i, j, k) wherex=in^2 +jn+k.)