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 marks) 2(b) Explain 0/1 knapsack problem using Branch and Bound method.(10 marks) 3(a) Explain flow shop scheduling with the help of example.(10 marks) 3(b)

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

(10 marks) 4(a) state graph colouring algorithm.Explain strategy used solving it along with example.(10 marks) 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 marks) 5(a) Explain Binary search.Derive its best case and worst case complexity.(10 marks) 5(b)

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

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

Write short notes on the following:

7(a) Radix sort(5 marks) 7(b) Tries(5 marks) 7(c) Randomised Algorithm(5 marks) 7(d) Strassen's matrix multiplication.(5 marks)