1.

Which of the following algorithm is NOT using divide-and-conquer?

A.

Merge sort

B.

Heap sort

C.

Quick sort

Binary search

2. Using divide-and-conquer technique if we know X, what is the minimal number of multiplications we need to compute X^40 ? (Hint: X^N=X^(N/2)* X^(N/2) is one multiplication, ^ is used for the exponential computation)

A.

5

B.

6

C.

7

3. The directed graph: V={V0,V1, V2,V3,V4,V5,V6}. There are the following twelve edges, with edge costs listed as the third item in the triplet: E={ (V0,V2,4), (V1,V0,2), (V1,V3,3), (V3,V0,1), (V3,V2,2), (V3,V5,8), (V3,V6,4), (V4,V1,10), (V4,V3,2), (V4,V6,7), (V5,V2,2), (V6,V5,1)}. If the above graph were undirected, then what would be the cost of its minimum spanning tree?

	A.	9
	B.	10
	C.	11
	D.	12

8