Search This Blog
CS2251 DESIGN AND ANALYSIS OF ALGORITHMS NOVEMBER/DECEMBER 2010 ANNA UNIVERSITY QUESTION PAPER QUESTION BANK IMPORTANT QUESTIONS 2 MARKS AND 16 MARKS
B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2010
Fourth Semester
Computer Science and Engineering
CS 2251 — DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2008)
Time : Three hours Maximum : 100 Marks
Answer ALL questions
PART A — (10 × 2 = 20 Marks)
1. If 0 1 .... ) ( a n a n a n f mm + + = , then prove that ) ( ) ( m n O n f = .
2. Establish the relationship between O and .
3. Trace the operation of the binary search algorithm for the input –15, –6, 0, 7,
9, 23, 54, 82, 101, 112, 125, 131, 142, 151, if you are searching for the
element 9.
4. State the general principle of greedy algorithm.
5. State the principle of optimality.
6. Compare divide and conquer with dynamic programming and dynamic
programming with greedy algorithm.
7. Explain the idea behind backtracking.
8. Define and solve the graph colouring problem.
9. Define NP Hard and NP Completeness.
10. What is a Minimum spanning tree?
PART B — (5 × 16 = 80 Marks)
11. (a) (i) Explain briefly the Time Complexity estimation, space complexity
estimation and the trade off between Time and Space complexity. (6)
(ii) Solve the following recurrence equations completely
(1) ∑ −
=
≥ + = 1
1
2 if , 1 ) ( ) (
n
i
n i T n T
1 if , 1 ) ( = = n n T . (4)
(2) ) 2 ( 6 ) 1 ( 5 ) ( − − − = n T n T n T (3)
(3) n n
n
T n T lg
2
2 ) ( +
= . (3)
Or
(b) (i) Write the linear search algorithm and analyse for its best, worst
and average case time complexity. (10)
(ii) Prove that for any two functions ) (n f and ) (n g , we have
)) ( ( ) ( n g n f θ = if and only if )) ( ( ) ( n g O n f = and )) ( ( ) ( n g n f = . (6)
12. (a) (i) Write a recursive algorithm to determine the max and min from a
given element and explain. Derive the time complexity of this
algorithm and compare it with a simple brute force algorithm for
finding max and min. (10)
(ii) For the following list of elements trace the recursive algorithm for
finding max and min and determine how many comparisons have
been made.
22, 13, –5, –8, 15, 60, 17, 31, 47. (6)
Or
(b) (i) Write the container loading greedy algorithm and explain. Prove
that this algorithm is optimal. (8)
(ii) Suppose you have 6 containers whose weights are 50, 10, 30, 20,
60, 5 and a ship whose capacity is 100. Use the above algorithm to
find an optimal solution to this instance of the container loading
problem. (8)
13. (a) (i) Write and explain the algorithm to compute the all pairs source
shortest path using dynamic programming and prove that it is
optimal (8)
(ii) For the following graph having four nodes represented by the
matrix given below determine the all pairs source shortest path (8)
0 6
1 0 7
0 2
3 0
∞ ∞
∞
∞ ∞
∞ ∞
Or
(b) (i) Write the algorithm to compute the 0/1 knapsack problem using
dynamic programming and explain it. (8)
(ii) Solve the following instance of the 0/1, knapsack problem given the
knapsack capacity is W = 5 (8)
Items Weight Value
1 2 12
2 1 10
3 3 20
4 2 15
132 132 132
53099 3
14. (a) Write an algorithm to determine the Sum of Subsets for a given Sum and
a Set of numbers. Draw the tree representation to solve the subset sum
problem given the numbers set as {3, 5, 6, 7, 2} with the Sum = 15. Derive
all the subsets. (8 + 8)
Or
(b) Write an algorithm to determine Hamiltonian cycle in a given graph
using back tracking. For the following graph determine the Hamiltonian
cycle. (8 + 8)
15. (a) Explain with an algorithm as to how 0/1 knapsack problem is solved
using branch and bound technique. Apply branch and bound technique to
solve the following 0/1 knapsack instance if W = 10. (8 + 8)
Items Weight Value
1 4 40
2 7 42
3 5 25
4 3 12
Or
(b) Write an algorithm and explain to determine Biconnected Components.
Prove the theorem that two biconnected components can have at most
one vertex as common and this vertex is an articulation point. (10 + 6)
