Define Time Complexity. Describe different notations used to represent these complexities.
Write an algorithm for Strassen's matrix multiplication and analyze the complexity of algorithm.
Show that the average case time complexity of quick sort is O(nlogn).
Describe in detail job sequencing with deadlines problem. Let n = 4, (P1, P2, P3, P4) = (100, 10, 15, 27) and (d1, d2, d3, d4) = (2, 1, 2, 1) find the optimal solution for the given values.
Write an algorithm for single source shortest path and apply it for the following graph. (graph with vertices A-F)
Discuss the importance of proving both the greedy choice property and the optimal substructure property for establishing the correctness of a greedy algorithm.
Explain Floyd Warshall algorithm problem with the graph given in figure. (graph image vertices 0-7)
Write an algorithm to solve Knapsack problem using Greedy technique. Find the optimal solution to the Knapsack instance n = 7, m = 15 (P1, P2, P3 ... P7) = (10, 5, 15, 7, 6, 18, 3) (W1, W2, W3 ... W7) = (2, 3, 5, 7, 1, 4, 1)
Describe how dynamic programming can be used to solve reliability design problems.
Describe graph coloring problem and write an algorithm for m-coloring problem.
Explain the 4-queen problem using backtracking algorithm.
Explain the method of reduction to solve travelling sales person problem using branch and bound.
Compare and contrast NP-Hard and NP-Complete classes
What are B-trees? How are they created? Explain with a suitable example.
Write short notes on any two of the following. a) Data Stream Algorithms b) Approximations Algorithms c) Data Transfer Optimization d) Huffman coding
