1(4% each) Multiple Choice (Fill only one answer in the blank of each problem).

(1) _______ Integers 9, 10, 5, 6, and 3 are inserted into a data structure in that order. An item is deleted by using only a basic data structure operation. If the deleted item is a 3, the data structure cannot be a

a. vector                                                                          b. list

c. queue                                                                       d. stack

(2)  _______What is the efficiency class of ∑1   ?

A: Θ(1)              B: Θ (log n)       C: Θ (n)                           D: Θ (n log n)                 E: Θ (n2)

(3) _______Which of the following functions has the highest growth rate?

a. n + 100log n                                                              b. n*log n

c. n10                                                                                                                       d. 2n

(4) _______Which operation is not supported in constant time by a deque

a. Insertion at the front or rear item     b. Access of the front or rear item

c. Deletion of the front or rear item       d. Access and deletion of the minimum item

(5) _______ An algorithm takes 5 seconds for an input size of 100. If the algorithm complexity is quadratic, approximately how long does it take to solve a problem of size 200?

a. 10 seconds                                                  b. 20 seconds

c. 30 seconds                                                 d. 40 seconds

2. (5% each) For each of the following algorithm in pseudo-code, indicate the time efficiency using Big- Theta (Θ) notation. You need to 1) identify the basic operation, and 2) justify your results by doing          summation or listing and solving the recurrence relation of T(n), which is the number of basic operations. It is your decision to make on the method you use to solve the recurrence.

(1)  for i = 1 to n do  for j = 1 to i do

a[i][j]=  0;

(2)  sum = 0;

for i = 0 to i = n - 1 do

for j = i + 1  to  j = n do

++sum;

(3)  Algorithm comp(n)

if n < 2 then return 1 ;

return comp( n / 2 ) + 1;

(4)   Algorithm f(n)

if n=0 return 1;

return 2*f(n-1)+ n*n;

3. ( 15%) (1) Show that x17 can be computed with six or fewer multiplications (and no addition, shifts or other operations).

(2) Applying the method in (1), write a recursive algorithm to evaluate the power of xn, where n is a positive large integer. What is the computing time efficiency of the algorithm?

4 ( 15%). Consider the following graph:

(1). Write down the adjacency matrix and adjacency lists specifying this graph.

(2) Starting at vertex a and resolving ties by the vertex alphabetical order, traverse the graph by depth- first search and construct the corresponding DFS stack and depth-first search tree.

5. ( 15%) How would you design a stack which, in addition to push and pop, also has a function min   which returns the minimum element? Push, pop and min should all operate in O(1) time. Your design should be given in pseudo code.