Total No. of Questions 18] [Total No. of Pages 02
M.Sc. DEGREE EXAMINATION, MAY 2018
First Year
COMPUTER SCIENCE
Design Analysis or algorithms
Time 3 Hours Maximum Marks :70
SECTION A
Answer any three of the following questions. × 15 45)
Q1) Explain all asymptotic notations used in algorithm analysis.
Q2) Using Dijkstra's Algorithm to Find a Shortest Path from a to z.
Q3) Explain quick sort algorithm using divide and conquer method. Derive best,
worst and average time complexities of quick sort.
Q4) Solve following knapsack problem using dynamic programming algorithm with
given Capacity Weight and Value are as follows:
15).
Q5) Write the solution of 4-Queens Problem using Backtracking Method.
Solve the Travelling Salesman problem using branch and bound technique.
SECTION B
Answer any five of the following questions. × 4 20)
Q6) Briefly explain about amortized analysis of an algorithm.
Q7) Explain the basic principle of Divide and Conquer method.
Q8) Write about Strassen's matrix multiplication.
Q9) Explain string matching algorithm with suitable example.
Q10) Constrict Huffman code for the following data
Character A B C E
Probability 0.35 0.1 0.2 0.2 0.15
Q11) Differentiate DFS and BFS.
Q12) Find the subset from the given sum using back tracking.
S and d 8.
Q13) Solve the all-pair shortest path problems for given adjacent matrix graph using
Floyd's Algorithm.
0 4 8
0 5 12
0 7
5 0


∞

∞ ∞
SECTION C
Answer all questions. × 1
Q14) Express the function 5n3 5n2 10n in Θ notation.
Q15) Define spanning tree.
Q16) Define principle of optimality.
Q17) Define 0/1 knapsack problem.
Q18) What is basic principle of Branch and Bound method?