Shivaji University 2007 B.E Computer Science COMPUTER ALGORITHM - exam paper

H-266
THIRD YEAR OF COMPUTER SCIENCE AND ENGINEERING (PART-1) EXAMINATION, 2007
SHIVAJI UNIVERSITY, KOLHAPUR
COMPUTER ALGORITHM

Day and Date: Friday, 29-11-2007 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 asymptotic notations in detail. [Marks 8]



Q.2
a) Prove the complexity of binary search algorithm is O (log n). [Marks 8]

b) discuss merge sort algorithm and show that its complexity is O(n logn) [Marks 8]

Q.3
a) Define spanning tree. discuss Kruskals algorithm to obtain minimum spanning tree with example. [Marks 8]

b) Explain Greedy approach to solve Job Sequencing issue. [Marks 8]

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

a) Huffman code
b) Quick sort algorithm
c) Analysis of algorithm









SECTION-2

Q. 6)
a) discuss any 2 traversal techniques of binary tree with suitable example. [Marks 8]

b) describe articulation point. discuss biconnected components of graph with suitable example. [Marks 8]



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

b) discuss Hamilton cycle with suitable example [Marks 8]

Q.7)
a) Explain sum of subsets and its solution using Backtracking approach. [Marks 8]

b) Reliability design with suitable example. [Marks 8]

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

a) AND-OR graphs
b) Graph coloring
c) Flow shop scheduling

Earning:   Approval pending.