STUPIDSID
Answer any one question from Q1 and Q2
1 (a)
Solve following recurrence relation:
T(n)=T(n/2)+1
T(1)=1
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
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).
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
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.
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
Find maximum profit using first in first out branch and bound (FIFOBB) method. Use fixed size formation for state space tree.
| 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 = |
|
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