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

H-491
THIRD YEAR OF COMPUTER SCIENCE AND ENGINEERING (PART-1) EXAMINATION, 2005

COMPUTER ALGORITHM

Day and Date: Wednesday, 07-12-2005 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) Define asymptotic notations with suitable example. [Marks 8]

b) Plot behavioral of graph of function log n, n log n, n2, 2n.. [Marks 8]
Q.2.
a) Prove the complexity of vinery search algorithm is O (log n). [Marks 8]

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




Q.3
a) Explain the greedy approach to slve job sequencing issue with example. [Marks 8]

b) Solve subsequent knapsack issue. N=4, m=30, (p1, p2, p3, p4) = (27,20,24,15) and (w1, w2, w3, w4) = (15, 10,18, 10) using greedy method.[Marks 8]

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

a) Performa Nance analysis algorithm
b) Quick sort algorithm
c) Greedy method
d) Divide and conquer strategy










SECTION-2

Q. 6)
a) discuss all pair shortest path issue with 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 flow shop scheduling issue. [Marks 8]

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

Q.7)
1) Explain traversal technique for graph with suitable example. [Marks 8]

b) Reliability BFS and DFS with suitable example. [Marks 8]

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

a) AND/OR graphs
b) Graph coloring
c) Game trees
d) Hamiltonian cycles

Earning:   Approval pending.