MORE IN Design and Analysis of Algorithms
SPPU Information Technology (Semester 6)
Design and Analysis of Algorithms
May 2015
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

Answer any one question from Q1 and Q2
1 (a) Solve following recurrence relation:
T(n)=T(n/2)+1
T(1)=1
5 M
1 (b) Analyze merge sort and find time complexity of merge sort.
5 M

2 (a) Write an algorithm to find factorial using recursion. Find the time complexity.
5 M
2 (b) Consider following instance for simple knapsack problem. Find the solution using greedy method.
N=8
P = {11, 21, 31, 33, 43, 53, 55, 65}
W = {1, 11, 21, 23, 33, 43, 45, 55}
M =110
5 M

Answer any one question from Q3 and Q4
3 (a) Write Krushal's algorithm to find minimum spanning tree.
5 M
3 (b) Write Floyd's algorithm for all pairs shortest path and find time complexity.
5 M

4 (a) Solve the following job sequencing problem using greedy algorithm.
N(Number of jobs)=4
Profits associated with jobs (P1, P2, P3, P4) = (100, 10, 15, 27). Deadline associated with jobs (d1, d2, d3, d4) = (2, 1, 2, 1).
5 M
4 (b) What is principle of optimality? Differentiate between greedy and dynamic method.
5 M

Answer any one question from Q5 and Q6
5 (a) Writ recursive backtracking algorithm for sum of subnet problem.
8 M
5 (b) Write an algorithm for 0/1 knapsack problem using backtracking method.
8 M

6 (a) What is backtracking? Write general iterative algorithm for backtracking.
8 M
6 (b) Write short note on:
i) State space tree
ii) Live node
iii) Expanding node (E-node)
iv) Bounding function
8 M

Answer any one question from Q7 and Q8
7 (a) Explain the term:
i) Least cost branch and bound.
ii) Compare backtracking and branch and bound method.
10 M
7 (b) Consider 0/1 Knapsack instance n=4 with capacity 10 kg. such that
 Item Profit (in Rs). Weight (in kg) 1 40 4 2 42 7 3 20 5 4 12 5

Find maximum profit using first in first out branch and bound (FIFOBB) method. Use fixed size formation for state space tree.
8 M

8 What is travelling salesman problem? Find the solution of following travelling salesman problem using branch and bound method.
Cost Matrix =
 ∞ 20 30 10 11 15 ∞ 16 4 2 3 5 ∞ 2 4 19 6 18 ∞ 3 16 4 7 16 ∞
18 M

Answer any one question from Q9 and Q10
9 (a) Prove that Clique problem is NP complete.
8 M
9 (b) Explain how parallel computations are possible using complete binary tree.
8 M

10 (a) Specify one example of NP-hard problem. Also mention that why it is NP hard.
8 M
10 (b) Explain in detail models for parallel computing.
8 M

More question papers from Design and Analysis of Algorithms