Assignment No2 - Algorithm Design
Uploaded by
jaggadakoo0420Assignment No2 - Algorithm Design
Uploaded by
jaggadakoo0420Assignment 2
Q.1 Explain Depth First Search traversal of Graph using an example.
Q.2 State the Greedy Knapsack? Find an optimal solution to the Knapsack instance n=3, m=20, (P1, P2,
P3) = (25, 24, 15) and (W1, W2, W3) = (18, 15, 10).
Q.3 Explain Breadth First Search traversal of Graph using an example.
Q.4 What do you mean by Searching? Explain Binary search with help of example.
Q.5 Discuss the plan of Divide and Conquer algorithm?
Q.6 Discuss Kruskal’s algorithm for finding minimum spanning tree. Give proper example.
Q.7 Discuss general characteristics of greedy method. Mention any two examples of greedy method that
we are using in real life.
Q.8 Solve the following Knapsack Problem using greedy method. Number of items = 5, knapsack capacity
W = 100, weight vector = {50, 40, 30, 20, 10} and profit vector = {1, 2, 3, 4, 5}.
Q.9 Explain Asymptotic notation. Arrange the growth rate of 2^n, n^2,1, log n, n logn, 3^n and n in
increasing order of growth.
Q.10 Write an algorithm for N – queen’s problem. Give time and space complexity for 8 – queen’s
problem.