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.

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:

7(a)
Radix sort

5 M

7(b)
Tries

5 M

7(c)
Randomised Algorithm

5 M

7(d)
Strassen's matrix multiplication.

5 M

More question papers from Analysis of Algorithms