M.C.A. DEGREE EXAMINATION, MAY 2017
Second Year
Computer Algorithms
Time 3 Hours Maximum Marks 70
SECTION A × 15 45)
Answer any three of the following
Q1) Explain about asymptotic notations used to measure the running time of algorithm.
Q2) Write a sub routine for merge sort illustrate for data n 10 and also compute its
complexity.
15, 26, 19, 29, 14, 11, 22, 7.
Q3) What is optimal binary search tree? Construct an optimal binary search tree for the
following items with probabilities given in the table below.
Items 1 2 3 4 5
Probability 0.24 0.22 0.23 0.3 0.01
Q4) Constrict Huffman code for the following data
P 0.1 p p 0.3, p 0.14, p 0.12 and p 0.24
Encode the text CAD and Decode 10011011011101
Q5) Illustrate branch and bound technique with suitable example.
SECTION B × 4 20)
Answer any five of the following
Q6) Represent the following functions in terms of Big O and Omega notation:
1.5 3 f =3n log n
Q7) Briefly explain about divide and conquer method.
Q8) Write about DFS based topological sorting problem with suitable example.
Q15) State job sequencing problem.
Q16) What is meant by Hamilton Cycles?
Q17) Define backtracking.
Q18) Define connected and bi-connected components.