Download Model question papers & previous years question papers
Posted Date: 05 Jan 2011 Posted By:: Swapna Member Level: Bronze Points: 5 (Rs. 1)

2009 Anna University Chennai M.C.A M.C.A DEGREE EXAMiNATION, JUNE/JULY CA5153 DESIGN AND ANALYSIS OF ALGORITHMS (REGULATION 2007) Question paper
PART A – [10 X 2 = 20 marks]
1.What is amortized efficiency? 2.Write the names of the basic asymptotic efficiency classes with their growth functions. 3.Define the internal path length of an extended binary tree. 4.State the Triomino Puzzle problem. 5.What are the differences between dynamic programming and divideandconquer techniques? 6.Give two reasons why the memory function approach is unattractive for the problem of computing a binomial coefficient. 7.Write the differences between backtracking and branchandbound techniques. 8.Write the three reasons to terminate a search path at the current node in a statespace tree of a branchandbound algorithm. 9.What are the two types to show a decision problem is NPComplete? 10.What is halting problem?
PART B – [5 X 16 = 80 marks]
11.(a) Briefly discuss the sequence of steps typically required in designing and analyzing an algorithm. (10) (b) Design a recursive algorithm for computing 2n for any nonnegative integer n which is based on the formula 2n = 2n1 + 2n1. (6) Or 11(ii).(a) Write a recursive algorithm for the Tower of Hanoi puzzle. Obtain the recurrence equation. (8) (b) Solve the recurrence equation which is to be obtained the above by the method of backward substitution. (8)
12.(a) Write a Mergesort algorithm and explain with an example using divideandconquer technique. (8) (b) Explain the working of binary search algorithm using divideandconquer with an example. (8) Or 12(ii).(a) Write the Quicksort algorithm and illustrate the operation of the algorithm with an example. (8) (b) Describe the Strassen's Matrix Multiplication technique. (8)
13.(a) Write and explain the dynamic programming algorithm for computing a binomial coefficient. Obtain the time efficiency of the algorithm. (8) (b) Explain the importance of optimal binary search tree. (8) Or 13(ii).(a) Explain the Warshall's algorithm for computing the transitive closure of a directed graph. (8) (b) Design a dynamic programming algorithm and explain for finding an optimal order of multiplying n matrices. (8)
14.(a) State and explain the nQueen problem using backtracking. (8) (b) Apply the branchandbound technique in solving the Traveling Salesman Problem. (8) Or 14(ii).(a) Illustrate the BranchandBound approach of solving assignment problem. (8) (b) Solve the following instance of the knapsack problem by the branchandbound algorithm, with W = 16. (8) Item Weight Value 1 10 100 2 7 63 3 8 56 4 4 12
15.(a) Explain the procedure to solve the Traveling salesman Problem with approximation algorithms. (10) (b) Give short notes on decision problems, undecidable problem, and NPComplete problem. (6) Or 15 (ii) (a) Explain how the knapsack problem is solved with approximation algorithm. (8) (b) Apply the nearest algorithm to the instance defined by the distance matrix below. Start the algorithm at the first city, assuming that the cities are numbered from 1 to 5. (8)
Return to question paper search


Submit Previous Years University Question Papers and
make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.