Could have a solution of this pastpaper klog n Theta nlog k

Could have a solution of this pastpaper?

k^log n = Theta (n^log k). Dijkstra\'s shortest path algorithm may not work correctly for graphs with negative edges. It takes linear time to compute a topological sort of a digraph. It is asymptotically faster to square an n-bit integer than to multiply two n-bit integers. One can find a minimum spanning tree in a graph by using the red rule only. Define the following terms: A shortest-path tree in a weighted graph. The red rule for the Greedy-MST algorithm. Determine tight asymptotic bounds for the following two recurrences. T(n) = 9T(n/3) + 6n^2. T(n) = 6T(n/3) + 9n^2. Design a divide-and-conquer algorithm to merge k sorted lists, each with n elements, into a single sorted list. Analyze the running time of your algorithm. Design an algorithm to find connected components of a graph G = (V, E) using the following operations on disjoint sets: Make-Set(x), Find(x), and Union(x, y).

Solution

Answer:

1) (5) . a) False, it is not theta (n^logk ) , it is theta(k^logn).

b) True , Dijkstra\'s algorithm does not work for the graphs having negative cycles , because it may give different shortest paths all time.

c) True,

d) True , as n + n = O(n) , but n *n = O(n^2) , so n +n is faster.

e) False , there are lot of methods to find MST in a graph, red rule is not the only one.

2 . 4) a) The set of all edges connecting all nodes such that the sum of edge lengths from the source is minimized. It is called shortest path tree.

b) Suppose we have a cycle with no red with no red edge. We select an edge with maximum weight and color it with the red.

3. 4) a) T(n) = 9T(n/3) + 6n^2

Solution :- Here a = 9 , b = 3 ,therefore loga base b = log9 base 3 = 2 , c = 2 . Now c = loga base b , therefore T(n) = theta(n^clog^k+1n = theta(n^2logn) .

Therefore T(n) = theta(n^2logn)

b) T(n) = 6T(n/3)+ 9n^2

Here a = 6 , b = 3, therefore loga base b = log6 base 3 = 1.63 , c = 2 , therefore c > log a base b.

Therefore T(n) = theta(f(n) = theta(9n^2) = theta(n^2).