Solve the following recurrence relation T(n) = 7T(n/2) + cn^2.
Show how quick sort sorts the following sequence of keys 65, 70, 75, 80, 85, 60, 55, 50, 45. Solve the recurrence relation of quick sort using substitution method.
Explain merge sort algorithm and find the complexity of the algorithm.
Write an algorithm for single source shortest path and apply it for the following graph. (graph image with vertices A-H)
How the Optimal Merge Pattern algorithm works? Explain with a suitable example.
Apply Kruskal's algorithm to find the minimum spanning tree of a graph with weighted edges. (graph image with vertices 0-8)
What is multistage graph problem? Discuss its solution based on dynamic programming approach. Also give a suitable algorithm and find its computing time?
Compute the optimal solution for knapsack problem using greedy method N = 5, M = 10, (p1, p2, p3, p4, p5) = (10, 15, 10, 12, 8), (w1, w2, w3, w4, w5) = (3, 3, 2, 5, 1).
Design a three stage system with device types D1, D2 and D3. The costs are , and respectively. The Cost of the system is to be no more than . The reliability of each device is 0.9, 0.8 and 0.5 respectively.
Briefly explain the Hamiltonian cycle using backtracking with a example.
Solve the following instance of travelling sales person problem using Branch Bound. inf 20 30 10 11 15 inf 16 4 2 3 5 inf 2 4 19 6 18 inf 3 16 4 7 16 inf
Explain the P, NP-Hard and NP-complete classes? Give the relation between them.
Explain the purpose of design and complexity of parallel algorithms in detail.
Write short notes on any two of the following: a) Logic Optimization b) Optimal merge patterns c) Data Transfer Optimization d) 8 queen's problem using backtracking
