Bengal Engineering and Science University 2006 B.E Computer Science and Engineering Design and Analysis of Algorithms - Question Paper

the ques. paper is with the attachment.

Ex/BESUS/ CST-604/06

B.E. (CST) Part-Ill 6th Semester Examination, 2006

Design and Analysis of Algorithms (CST-604)

Full Marks : 100

Answer Q. 1 and any FOUR from the rest

1. Briefly argue on the following statements (any eight) :

a)    Sorting algorithms cannot have linear time complexity without some assumptions about the distribution.

b)    Fractional Knapsack exhibits greedy choice property, but 0-1 Knapsack does not.

c)    Polygon triangulation problem can be mapped to matrix chain multiplication.

d)    Conventional algorithm for primality testing cannot have polynomial time complexity.

e)    Choice of hash function has a role in the performance of dynamic set operations,

f)    Connected components of a graph can be found using a sequence of UNION-FIND operations.

g)    Multiplication of two polynomials can be achieved in linear time by proper representation but the valuation cannot be done in linear time.

h)    Selection of the middle most element of an array does not require sorting of the array elements.

i)    Travelling salesman problem is as hard as finding Hamiltonian cycle in a graph.

j) Searching of an element takes less time in open addressing scheme, compared to searching time in case of chaining. k) Kruskal's algorithm for finding the minimum spanning tree takes less time due to its choice of data structure.

2.    Describe the FFT algorithm to achieve multiplication of two polynomials. Analyze the time complexity of the algorithm.    [9+8]

3.    Formulate the matrix chain multiplication problem. Describe a polynomial time algorithm for its solution. Show how the algorithm works for the matrices with given dimensions :

(3 x 4) x (4 x 2) x (2 x 5) x (5 x 3)

4.    Discuss the theory of matroids in connection with greedy algorithms. Show how the minimum spanning tree of a graph can be found using matriod theory. |8+9]

5.    Describe algorithms to achieve :    [7+10]

a)    Worst case linear time to select the i¹ smallest element of an array.

b)    O(nig* n) complexity in disjoint set operations.

6.    Describe RSA based Public Key Cryptosystem. In this context, discuss the algorithms along with their time complexities for implementing the cryptosystem.

[8+91

7.    Define NP-Completeness. Explain how the fate of NP-Complete problems are linked together. Argue why circuit satisfiability problem should be as hard as any other problem in NP. Does that imply it (CSAT) is NP Complete ? [3+4+7+3]

Attachment: bengal-engineering-and-science-university-2006-b-e-computer-science-and-engineering-1071-1.pdf

Earning:   Approval pending.