Define time complexity. Describe different notations used to represent time complexity.
Discuss Strassen's matrix multiplication as well as classical O(n^2) one. Determine when Strassen's method outperforms the classical one.
Explain partition exchange sort algorithm and trace this algorithm for n = 8 elements: 24, 12, 35, 23, 45, 34, 20, 48.
State the Job - Sequencing with deadlines problem. Find an optimal sequence to the n = 5 Jobs where profits (P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) and deadlines (d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3).
A thief enters a house for robbing. Thief can carry a maximum weight of 6kg into his bag. There are 3 items in the house with weights (w1, w2, w3) = (2, 3, 4) and profits (p1, p2, p3) = (1, 2, 5) what items should thief can take will get the maximum profit? He either takes or leaves the item.
Explain prim's and Kruskal's algorithm shown in figure with the following example. (graph with vertices 1-7)
Solve the following instance of 0/1 Knapsack problem using Dynamic programming. n = 3; (W1, W2, W3) = (3, 5, 7); (P1, P2, P3) = (3, 7, 12); M = 4.
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.
Discuss about Multistage graph problem. Also give a suitable algorithm and find its computing time.
Write an algorithm to determine the Hamiltonian cycle in a given graph using backtracking.
Solve the following instance of travelling sales person problem using Least Cost Branch Bound. (graph with vertices 1-5 and weights)
Construct state space tree for solving four queen's problem using backtracking.
Explain the P, NP-Hard and NP-complete classes? Give the relation between them.
Show the inorder, preorder and postorder for the following tree (tree with nodes A-G)
Write short notes on any two of the following a) Data Transfer Optimization and Logic Optimization b) Differentiate between prim's algorithm and Kruskal's algorithm c) Parallel algorithms d) Approximation Algorithms
