Berhampur University 2007 M.Tech Computer Science Design & Analysis of Algorithms - Question Paper

Full Marks - 60
every ques. 15 marks
~~~~~~~~~~~~~~~~~~~~~~~~
1.a. What is an algorithm? State & discuss basic properties of an algorithm. (8 marks)
b. discuss the Space & time complexities. (7 marks)

or

a. Describs the kruskal's algorithms for finding the minimum spanning three.
b. What is an optimal Binary Three? Write an algorithm for inserting an element into a binary search tree.

2.a. What is the principle of optimality? discuss with 2 examples.
b. discuss the Dynamic Programming methid.

or

a. discuss the greedy technique with Kuapsack issue as an example.
b. discuss the probelm of job Scheduling with dead lines with an example.

3.a. discuss Branch & Bound Technique using traveling salesman issue as an example.
b. discuss the Back Tracking Strategy.

or

a. define merge sort algorithm using Divide-and-conquer strategy.
b. discuss how the above merge sort algorithm sorts the subsequent losts or numbers 5,8,6,3,7,2.

4.a. define NP-Hard probelm with suitable eample.
b. discuss the difference ranging from NP-Hard and NP-Complete issue.

or

a. State and prove Cook's theorem.

~~~~~Best of Luck~~~~~

Earning:   Approval pending.