Total No. of Questions [Total No. of Pages 02
M.C.A. DEGREE EXAMINATION, MAY- 2018
Second Year
COMPUTER ALGORITHMS
Time Hours Maximum Marks :70
SECTION A
Answer any three questions. x 15 45)
Q1) Explain the properties of an algorithm with an example.
Explain about Worst case, best case and Average Case Complexity.
Q2) Discuss about quick sort algorithm with suitable example and derive its
complexities.
Q3) Solve the following job sequence problem.
n p2, p3, p4) 10, 15, d2, d3, d4) 1). Find the
optimal Sequence and profit.
Q4) Explain Backtracking Method. What is N-Queens Problem? Give solution of
Queens Problem using backtracking Method.
Q5) Explain how branch and bound technique differs from back tracking. Solve the
Travelling Salesman problem using branch and bound algorithms.
SECTION B
Answer any five questions from the following. x 4 20)
Q6) Briefly explain about amortized analysis of algorithm.
Q7) What is Divide and Conquer Technique? Give the use of it for binary Searching
method.
Q8) State and explain about quick hull problem.
Q9) Constrict Huffman code for the following data: 0.1 p 0.3,
0.14, 0.12 and 0.24. Encode the text CAD and Decode
10011011011101.
Q10) Explain Chained Matrix Multiplication with example.
Q11) Solve the all pair shortest paths problem for the digraph with weight matrix.
0 3
2 0
7 0 1
6 0
∞
∞


∞ ∞
Q12) Explain the Graph coloring problem. And draw the state space tree for m=3
colors n=4 vertices graph.
Q13) Solve the knapsack problem by branch and bound technique.
SECTION C
Answer all questions. x 1
Q14) Define Big notation.
Q15)What is spanning tree?
Q16)What is meant by optimal binary search tree?
Q17) Define backtracking.
Q18) State subset sum problem.