MORE IN Analysis of Algorithms
MU Computer Engineering (Semester 4)
Analysis of Algorithms
December 2013
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1(a) Explain divide and conquer strategy. Write control abstraction(General Method)For it.List any four problems that can be solved using divide and conquer.
10 M
1(b)

Explain asymptotic notation.Explain time complexity and space complexity in detail.

10 M

2(a)

Construct the optimal Binary search tree for identifier set

$$(a_{1},a_{2},a_{3},a_{4})=(Cout,float.if,while)\\ with \ p(1:4)=\left(\dfrac{1}{20},\dfrac{1}{5},\dfrac{1}{10},\dfrac{1}{20}\right)\\ and \ q(0:4)=\left(\dfrac{1}{5},\dfrac{1}{10},\dfrac{1}{5},\dfrac{1}{20},\dfrac{1}{20}\right)$$

10 M
2(b) Explain 0/1 knapsack problem using Branch and Bound method.
10 M

3(a) Explain flow shop scheduling with the help of example.
10 M
3(b)

Solve following problem using Kruskal's algorithm which is used to find minimum spanning tree. 10 M

4(a) state graph colouring algorithm.Explain strategy used solving it along with example.
10 M
4(b) Consider following set of frequencies
A=2 B=5 C=7 D=8 E=7 F=22 G=4 H=17
Find Huffman code for same.
10 M

5(a) Explain Binary search.Derive its best case and worst case complexity.
10 M
5(b)

Find shortest path using Djkstra's algorithms for the following graph assume source node is A. 10 M

6(a) Explain 8 Queen problem and strategy used to solve it.
10 M
6(b) Explain job sequencing with dead lines along with example.
10 M

Write short notes on the following: