Bengal Engineering and Science University 2007 B.E Computer Science and Engineering Design and Analysis of Algorithms - Question Paper
The ques. paper is with the attachment.
Ex/BESUS/ CST-604/ 07 B.E. (CST) Part-Ill 6th Semester Examination, 2007
Design and Analysis of Algorithms (CST-604)
Time : 3 hours Full Marks : 100
Answer any FIVE questions.
1. Define matroid. Formulate greedy algorithm on weighted matroid. Prove the correctness of the algorithm. Show how matroid theory may be exploited to find the Minimum Spanning Tree of a given graph. [2+4+8+6J
2. Describe an algorithm to perform the selection of the middlemost element of an array :
a) in average case linear time.
b) in worst case linear time.
Present the proof of correctness as well as time complexity analysis for both.
110+10]
3. Which kind of problem is candidate for dynamic programming? Why is the matrix chain multiplication problem suitable for dynamic programming? Describe how polygon triangulation problem may be solved using the same algorithm as matrix chain multiplication. [4+6+10]
4. List the operations on disjoint sets. Show how the following choice of data structure work towards improvement of time complexity of the disjoint set operations :
(a) Linked list (b) Disjoint Set Forests. [4+6+10]
5. Formulate the polynomial multiplication problem using different representations. Show how the roots of unity may be exploited to perform faster multiplication-mathematical proof only is required. Show also mathematically how the conversion from one representation to the other can be done using the same algorithm. [4+8+8|
6. What are the requirements of a public - key crypto system? Show how RSA crypto system meets these requirements. Describe the steps involved, together with time complexity, in implementing RSA crypto system. [4+6+10]
7. Define NP-Complete class. Why is circuit satisfiability problem considered to be NP-Complete? Give an outline of the proof for Travelling Salesman Problem being NP-complete. [4+8+8]
8. Write short notes on (any two) : [10x2]
a) Dynamic set operations
b) Sorting in linear time
c) Data compression using greedy strategy.
|
Attachment: |
| Earning: Approval pending. |
