Dr Bhim Rao Ambedkar University 2006 B.Tech Information Technology Computer Algorithm - Question Paper

Q-138
THIRD YEAR OF COMPUTER SCIENCE AND ENGINEERING (PART-1) EXAMINATION, 2006

COMPUTER ALGORITHM

Total Marks: 100
Time: 10.00p.m. To 1.00p.m.

Instructions:

Instructions:
1) Solve any 3 ques. from SECTION-1
2) Solve any 3 ques. from SECTION-2
3) Figures to right shows full marks

SECTION-1

Q.1.
a) Explain time and space complexity with example. [Marks 8]

b) Explain binary search with example. [Marks 8]



Q.2
a) Prove the merge sort complexity is O (n log n) [Marks 8]

b)discuss the maximum and minimum finding algorithm with example. [Marks 8]

Q.3
a) Explain the primes and kruskals algorithm to obtain minimum spanning tree with example. [Marks 8]

b) Solve subsequent job sequencing issue. For 7 jobs profit factors are (45,5,20,18,6,30,70) and dead lines are (1,3,4,3,2,1,2). [Marks 8]

Q.4 Write a short notes on (any three): [Marks 18]

a) Divide and conquer algorithm design technique
b) Quick sort algorithm
c) Selection algorithm
d) Optimal storage on tapes algorithm










SECTION-2

Q. 6)
a) discuss multistage graph with suitable example. [Marks 8]

b) Let n=4 and probabilities with which identifiers (a1, a2, a3, a4)= (do, if, int, while) are searched are (4,4,2,2) and probability of unsuccessful searched are q(0:4)=(3,4,1,1,1) find optimal binary searched tree.[Marks 8]



Q.6)
a) Explain the solution for all pairs shortest path issue using dynamic programming. [Marks 8]

b) discuss eight queens issue and its solution using backtracking. [Marks 8]

Q.7)
a) Explain subsequent term with suitable example. [Marks 8]

1) Articulation point in graph
2) biconnected components
b) Reliability BFS and DFS with suitable example. [Marks 8]

Q.8) Write a short notes on (any three): [Marks 18]

a) Principle of optimality
b) Graph coloring
c) Game trees
d) Hamiltonian cycles

Earning:   Approval pending.