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

Sunday, 20 January 2013 12:50Web

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 exampl

**e.**[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 exampl

**e.**[Marks 8]

Q.3

a) Explain the greedy approach to slve job sequencing issue with exampl

**e.**[Marks 8]

b) Solve subsequent knapsack issu

**e.**N=4, m=30, (p1, p2, p3, p

**4)**= (27,20,24,

**1**and (w1, w2, w3, w

**5)****4)**= (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 exampl

**e.**[Marks 8]

**b)**Let n=4 and probabilities with which identifiers (a1, a2, a3, a4)= (do, if, int, whil

**e)**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 issu

**e.**[Marks 8]

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

Q.7)

1) Explain traversal technique for graph with suitable exampl

**e.**[Marks 8]

b) Reliability BFS and DFS with suitable exampl

**e.**[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. |