Total No. of Questions 18] [Total No. of Pages 02
M.Sc. DEGREE EXAMINATION, MAY 2017
First Year
Computer Science
Design and Analysis of Algorithms
Time 3 Hours Maximum Marks 70
SECTION A
Answer any Three questions × 15 45)
Q1) Discuss various asymptotic notations used to measure the running time of algorithm.
Q2) Divide and conquer paradigm involves three steps at each level of recursion. What are
all they? Show that merge-sort algorithm closely follows these steps. Illustrate the
operation of merge sort on the array A 41, 52, 26, 38, 57, 49}
Q3) Given weight vector w2, w3, w4, w5, w6, w7) and profit
vector p2, p3, p4, p5, p6, 15, 18, and Knapsack of capacity
15. Find optimal solution for 0/1 knapsack problem
Q4) Construct Minimum spanning tree for the following graph using prims algorithm

SECTION B × 4 20)
Answer any five from the following

Q7) State and describe the connected and bi-connected components
Q8) Describe the activity selection problem for job sequencing.
Q9) Compare and contrast DFS and BFS.
Q10) What do you mean by dynamic programming? What is difference between dynamic
programming and greedy method?
Q11) Describe any string matching algorithm. Also calculate its time complexity.
Q12) State and explain about 4 queen's problem.
Q13) Find the subset from the given sum using back tracking.
S and d 8
SECTION C
Answer all questions. × 1
Q14) State quick hull problem.
Q15) What is Huffman tree?
Q16) What is the best and worst case complexities of merge srot?
Q17) State general method of branch and bound.
Q18) Define optimal BST.