Question 1

----------

 

Ans: T(n) = Theta( (log n) ^ 2 )

 

Method 0: 

   T(n) = 4 T( Sqrt(n) ) + log n

   Let n = 2^k

   Let U(k) = T(2^k)

   Then, T(2^k) = 4 T ( 2^(k/2) ) + log (2 ^ k).

   Hence, U(k) = 4 U (k/2) + k

   By Master Theorem, U(k) = Theta ( k^ 2 )

   Hence, T(n) = Theta ( (log n) ^ 2) )

 

Method 1: Expand the tree, you find a depth of log ( log (n) ) and each level has work=  2^i * log n. Summing provides the same solution.

 

Question 2

----------

 

Answer (one of many):

 

Let i = some element

Let c(i) = count of that element

 

1) Build a max-heap over (i, c(i)) , using c(i) as the 'priorities'

2) Index (hash) each element i into its location in the max-heap

 

Now, 

ADD = look up each element, increment and fix the heap

DELETE = look up, decrement, fix heap

SIZE OF INTERSECTION = keep pop-ing the heap until the count drops

 

Cost of any operation = k log Q

 

Question 3

----------

 

Here's a cute solution:

 

We are given the graph and the two nodes, s & t.

 

Let

g [v] = min dist from s to v

h [v] = min dist from t to v

 

g and h can both be computed using Dijkstra's algorithm efficiently (nothing new).

 

Now, for each edge (u, v), consider going from  s--u  v -- t  (cost=g[u]+h[v], hence skipping the edge (u, v) ).

Consider this for each edge and select the one which gives the shortest path.

 

Proof/Claims:

1) The path chosen will have the longest edge removed (if not, there exists an even shorter path the algo should have considered - namely, take the true longest edge and use that instead!)

2) It works!!

 

Timing analysis:

 

2 Dijkstra algorithms will consume O(VlogV+E) time implemented using Union-heap. And the searching through edges will take O(E) time. Hence it is as efficient, asymptotically as the usual shortest path Dijkstra algorithm.

 

Question 4

----------

 

a) Convert array to heap --> In general, this takes linear time (for any array, sorted or not).

   In this case, it takes exactly n time, you can fill the heap bottom up.

 

b) Expected Time = 2

   Each element has a probability of 1/n of being selected.

   Fixing time for each element = 1 + distance from leaf

   Hence, all bottom elements (n/2 elements) need just 1, next level (n/4 elements) needs 2, etc

   So, expected time = 1/n * ( 1*n/2 + 2*n/4 + 3*n/8 ... ) = 2