B.E. Sixth Semester (Computer Science and Engineering) (CB.CS.) Summer 2023 Design and Analysis of Algorithms - 6 KS 02
1. a) What is efficiency of algorithms. Explain in details the means to improve the efficiency of algorithms.
b) Convert the following factorial function from a recursive implementation to at iterative one
fact (n) = 1 for n = 1
=n*fact fir n > 1
OR
2. What is asymptotic notation? Explain the Big O, Thets and Omega notation along with the
properties of these notations (13 MARKS)
3. a) What is divide and conquer? Give the control abstraction of divide & conquer.
b) Explain Strassen's matrix multiplication method to improve the performance.
OR
4. a) Explain convex hull problem Explain the algorithms for finding convex hulls based on D & C strategy
b) Where does the D & C strategy fail? Explain the class of problems for which D & C is unsuitable.
5. a) Explain the knapsack algorithm and find an optimal solution to the instance m=5 and w=100 (capacity)
(W1 W2 W3 W4 W5)=(10, 20, 30, 40, 50)
(V1 V2 V3 V4 V5) = (20, 30, 66, 40, 60)
W1----W5 Are weights and V1----V5 Are profit
b) Explain job scheduling with deadlines and find a solution to the scheduling problem when n = 7
(P1 P2------P7)=(3, 5, 20, 18, 1, 6, 30)
(D1 D2-----D7) = (1, 3, 4, 3, 2, 1, 2)
OR
6. a) Write the Kruskal and Prim's algorithm. Construct minimum spanning tree (MST) for the following graph.
7. a) Solve the following traveling salesperson problem & find optimal path.
b) Distinguish between greedy method and dynamic programming. Give its advantages and disadvantages.
OR
8) Explain chained matrix multiplication algorithm for dynamic programming state how the algorithm works to calculate the product of five matrices.
M1 is 4x10 M2 is 10x3 M3 is 3x12 M4 is 12x20 M5 is 20x7
9. a) Explain Breath first search (BFS) algorithm with an example.
b) Explain M-colouring problem with an example.
OR
10. a) Explain Hamiltonian cycle with an example.
b) Explain Backtracking strategy for the 8-queens problem.
11. a) Explain the notion of complexity.
b) Explain:
i) Worst case behaviour.
ii) Average case behaviour.
iii) Probabilistic average case analysis.
OR
12. a) Explain polynomial (P) and nonpolynomial time (NPT) algorithm.
b) Explain the step counting principle.
