Punjab Technical University 2007-5th Sem B.E Computer Science DESIGN AND ANALYSIS OF ALGORITHMS (CS-307) (-2k7) - Question Paper

Paper ID [CS307]

B.Tech (Semester - 5th)

DESIGN AND ANALYSIS OF ALGORITHMS (CS - 307)

Time : 03 Hours
Maximum Marks : 60

Instructions to Candidates :
1) part - A is Compulsory.
2) Attempt any 4 ques. from part - B
3) Attempt any 2 ques. from part - C

part - A
(10 x two = 20)

Q1)

a) What do you understand by Algorithm valuation ?

b) What is Asymptotic Complexity ?

c) elaborate Stored RAM Models ?

d) define a path in an undirected graph.

e) define post order traversal of a tree.

f) What is the time complexity of Merge Sort ?

g) provide an example of dynamic Programming approach.

h) elaborate Union Fibd issues.

i) What is trend Matching ?

j) What is NP Complete issue ?


part - B
(4 x five = 20)

Q2) discuss the relationship ranging from Turing Machine and RAM models.

Q3) define the Dynamic Programming Algirithm for computing the minimum cost order of multiplying a string of n matrices M1 x M2 x M3 x ..... X Mn.

Q4) elaborate position trees? define using examples.

Q5) elaborate NP, NP Hard and NP Complete problems? discuss by giving an example of every.

Q6) discuss the example of a non-deterministic finite automation.


part - C
(2 x 10 = 20)

Q7)
(a) Consider a binary tree with names attached to the vertices. Write an algorithm to print the names in (i) Post Order, (ii) In Order, (iii) Pre Order.
(b) How Binary tree can be used for searching an element? discuss.

Q8)
(a) elaborate String Matching algorithms?
(b) provided a Text string X and a string trend Y, determine all occurrences of Y in X.

Q9)
(a) discuss the alforithm for Fast Disjoint Set Union Algorithm.
(b) provide an example of NP-complete issue.

Earning:   Approval pending.