Accounting and Financial Management (3) Analog and Digital Communication (2) Artificial Intelligence (2) BE(Civil) (2) BE(CSE) (83) BE(ECE) (11) BE(Mech) (10) Business Processes (3) C# and .NET Framework (2) Communication Skills (1) Compiler Design (1) COMPONENT BASED TECHNOLOGY (1) COMPUTER ARCHITECTURE (1) COMPUTER GRAPHICS and MULTIMEDIA SYSTEMS (6) COMPUTER INTEGRATED MANUFACTURING (1) Computer Networks (9) Computer Organization (2) Computer Programming (1) Consumer Behaviour (1) Control Systems (1) Cryptography and Network Security (3) Datastructures and Algorithms (10) Datawarehousing and Mining (1) DBMS (5) DESIGN AND ANALYSIS OF ALGORITHMS (9) DESIGN OF MACHINE ELEMENTS (1) DIGITAL PRINCIPLES AND SYSTEMS DESIGN (3) Discrete Mathematics (1) DISTRIBUTED COMPUTING (2) DSP (8) DYNAMICS OF MACHINERY (2) Economic Foundations (1) ELECTRICAL ENGINEERING (1) ELECTRICAL ENGINEERING AND CONTROL SYSTEMS (1) Electromagnetic Fields (3) ELECTRONIC CIRCUITS (1) ELECTRONIC COMMERCE (4) ELECTRONIC DEVICES AND CIRCUITS (1) EMBEDDED SYSTEMS (1) FUNDAMENTALS OF COMPUTING (2) Graphics and Multimedia (3) HEAT AND MASS TRANSFER (1) HUMAN RESOURCE MANAGEMENT (1) Internet Programming (9) INTRODUCTION TO FINITE ELEMENT ANALYSIS (1) Legal Aspects of Business (1) MANAGEMENT INFORMATION SYSTEMS (1) Marketing Management (1) MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE (4) MATHEMATICS - I (1) MBA (9) MCA (83) MCA QUESTION BANK (2) MECHATRONICS (1) MicroProcessor and Controllers (4) MICROPROCESSORS AND APPLICATIONS (5) MIDDLE WARE TECHNOLOGIES (3) MOBILE COMPUTING (5) NETWORK PROGRAMMING (1) NUMERICAL METHODS (1) OBJECT ORIENTED ANALYSIS AND DESIGN (5) Object Oriented Programming (18) Operating System (2) OPERATING SYSTEMS (9) Organizational Behaviour (2) POWER ELECTRONICS (1) Principles of Management (8) PROBABILITY AND QUEUEING THEORY (2) Probability and Statistics (1) PROBLEM SOLVING AND PROGRAMMING (2) PROCESS PLANNING AND COST ESTIMATION (1) PROFESSIONAL ETHICS AND HUMAN VALUES (1) RANDOM PROCESSES (1) RESOURCE MANAGEMENT TECHNIQUES (2) ROBOTICS (1) Security analysis (1) Service Marketing (1) SIGNALS AND SYSTEMS (1) Software Engineering (8) SOFTWARE PROJECT MANAGEMENT (4) SOFTWARE QUALITY MANAGEMENT (2) System Software (2) TCP/IP PROTOCOL SUITE (3) Theory of Computation (4) Total Quality Management (2) UNIX AND NETWORK PROGRAMMING (4) Visual Programming (2) WEB GRAPHICS (2) WEB TECHNOLOGY (2) XML AND WEB SERVICES (4)

Tuesday, October 26, 2010

CA5153 DESIGN AND ANALYSIS OF ALGORITHMS JULY 2009

M.C.A DEGREE EXAMINATION, JUNE/JULY 2009
SECOND SEMESTER
CA5153 DESIGN AND ANALYSIS OF ALGORITHMS
(REGULATION 2007)
Time: Three hours Maximum: 100 marks
Answer all questions.


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 divide-and-conquer 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 branch-and-bound techniques.
8. Write the three reasons to terminate a search path at the current node in a state-space tree of a branch-and-bound algorithm.
9. What are the two types to show a decision problem is NP-Complete?
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 = 2n-1 + 2n-1. (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 Merge sort algorithm and explain with an example using divide-and-conquer technique. (8)
(b) Explain the working of binary search algorithm using divide-and-conquer with an example. (8)
Or
12(ii).(a) Write the Quick sort algorithm and illustrate the operation of the algorithm with an example. (8)
(b) Describe the Stassen’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 n-Queen problem using backtracking. (8)
(b) Apply the branch-and-bound technique in solving the Traveling Salesman Problem. (8)
Or
14(ii).(a) Illustrate the Branch-and-Bound approach of solving assignment problem. (8)
(b) Solve the following instance of the knapsack problem by the branch-and-bound 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, un decidable problem, and NP-Complete 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)

No comments:

Post a Comment