B.E.
5th SEMENSTER (CSE)
Examination - December, 2011
ANALYSIS
AND DESIGN OF ALGORITHMS
Paper : CSE-306-E
Note
: Attempt any five questions. All questions carry equal marks.
1. (a) What is the recurrence relation ? Solve the
following relation by recursive method :
P(n) = 2T(n/2 + 10 ) + n 10
(b)
What are priority queues and explain their application with algorithm Suitable examples. 10
2. (a) Explain Strassen’s matrix
multiplication. Can you change the same technique to get lower time complexity
algorithm. 10
(b) Explain the algorithm of merge sort and compare time complexity with
heap sort. 10
3. (a) Explain the greedy approach for
the algorithm design ? Devise a solution for fractional knapsack using greedy
approach ? Give its time complexity. 10
(b)Explain the job sequencing with deadlines problem using suitable
example. 10
4. Explain the concept of optimal Binary
Search trees with suitable example showing its applications. 20
5. (a) What is graph coloring? Write the
algorithm to find chromatic number of a graph. 10
(b)Discuss N-Queens problem and analyze the time complexity of the same. 10
6. Discuss branch and bound strategy by
solving any instance of 0/1 Knapsack problem and analyze the time complexity
for the same. 20
7. (a) Explain deterministic and non
deterministic algorithm with suitable examples.
(b) Explain the following :
(i) NP-Hard
(ii) NP-Complete
8. Explain the following :
(i)
LC
– search
(ii)
Huffman
codes
(iii)
TSP
is NP-Complete
No comments:
Post a Comment