Punjab Technical University 2010-2nd Sem B.Sc BioInformatics M.Sc(BI) (nd) DESIGN AND ANALYSIS OF ALGORITHMS - Question Paper

[Total No. of Pages : 02

Roll No........................

Total No. of Questions : 13]

J-3537[S-1393]

M.Sc. (BI) (Semester - 2^nd)

DESIGN AND ANALYSIS OF ALGORITHMS (M.Sc. (BI) - 203)

Time : 03 Hours Instruction to Candidates:

1)    Section-A is compulsory.

2)    Attempt any Nine questions from Section-B.

Section - A

(15 x 2 = 30)

a)    Differentiate between Binary and Binary Search Tree.

b)    What are maximum and minimum numbers of elements in a heap of height h?

c)    What is space complexity?

d)    What are the various steps in the design of an algorithm?

e)    The order of complexity of binary search (successful case) in best case is.......in average case is.........and in worst case is............

f)    What are the various techniques for design of algorithm?

g)    Which is more efficient Breadth first Search or Depth first Search?

h)    What is lower bound?

i)    What is the algorithm for in-order traversal? j)    Give brief concept of Divide & Conquer.

k)    What is a solution space in the backtracking technique?

l)    Give an example of an algorithm, which is infinite in nature.

m)    What are Explicit & Implicit constraints?

n)    Differentiate b/w complete & full binary tree.

o)    What is recursion? What are its drawbacks?

(9 x 5 = 45)

Q2) Define algorithm? Also explain the different criteria that all algorithms must satisfy.

Q3) Solve 4- queen problem using backtracking.

Q4) How does Heap sort work?

Q5) What is NP-hard and NP-complete with example?

Q6) Explain the different terminologies that we use for trees and graphs.

Q7) Explain why we use asymptotic notation. Also define the following notations:

(a)    big O

(b)    Omega

(c)    Theta

Q8) Give algorithms for the Graph traversal techniques.

Q9) What type of operations can be performed on strings? Explain at least two operations on strings with algorithms.

Q10) What are the advantages of dynamic programming over the greedy method?

Q11) Write an algorithm to delete an element from a linked list. Also mention the worst case running time for this operation.

Q12) Explain the concept of Connected and Bi-connected components in Graphs.

Q13) What are approximation algorithms? Define absolute approximation and E-approximation with example.

nnn

J-3537[S-1393]    2

Attachment: punjab-technical-university-2010-b-sc-bioinformatics-23491-1.pdf

Earning:   Approval pending.