# Shivaji University 2005 B.E Computer Science CA - Question Paper

Sunday, 19 May 2013 05:35Web

H-491

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)**describe 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)**explain maximum and minimum finding algorithm with exampl

**e.**[Marks 8]

Q.3

**a)**discuss 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)**discuss flow shop scheduling issu

**e.**[Marks 8]

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

Q.7)

**1)**discuss 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. |