Describe the performance analysis of an algorithm in detail.
Consider the following recurrence T(n) = 3T(n/3) + n obtain asymptotic bound using substitution method.
Write Divide - And - Conquer recursive Quick sort algorithm and analyze the algorithm for average time complexity.
Apply the Greedy method to solve Knapsack problem for given instance. Where n = 3, m = 20, (p1, p2, p3) = (25, 24, 15) and weight (w1, w2, w3) = (18, 15, 10)
Write Kruskal's Algorithm. Generate the MCST for the graph given in Figure 1 by applying Kruskal's algorithm. (graph with vertices A-F)
Obtain a set of optimal Huffman codes for the seven messages (M1, ... , M7) with relative frequencies (q1, ... , q7) = (4, 5, 7, 8, 10, 22, 15). Draw the decode tree for this set of codes.
Solve the following 0/1 Knapsack problem using dynamic programming P = (11, 21, 31, 33), W= (2, 12, 23, 15), C = 42, n = 4.
Explain Floyd Warshall algorithm problem with the graph given in figure. (graph with vertices A-F)
What is multistage graph problem? Discuss its solution based on dynamic programming approach. Also give a suitable algorithm and find its computing time?
Find a solution to the 8-Queens problem using backtracking strategy. Draw the solution space using necessary bounding function.
Solve the traveling salesperson problem using branch and bound technique. A B C A 0 3 4 B 6 0 4 C 3 5 0
What is Backtracking? Discuss any one problem solved by backtracking. Also give its advantages and disadvantages.
Compare and contrast NP-Hard and NP-Complete classes.
Create a B-tree for the following list of elements L = {86, 50, 40, 3, 94, 10, 70, 90, 110, 113, 116} given minimization factor t = 3, minimum degree = 2 and maximum degree = 5.
Write short notes on any two of the following: a) Reliability design b) Correctness proof of Greedy algorithms c) Design and complexity of Parallel Algorithms d) Graph coloring problem
