Andhra University 2005 M.C.A DESIGN AND ANALYSIS OF ALGORITHMS - Question Paper

2005 Andhra University M.C.A Computer Applications DESIGN AND ANALYSIS OF ALGORITHMS ques. paper

MCA 2.1.4

DESIGN AND ANALYSIS OF ALGORITHMS

First ques. is Compulsory

ans any 4 from the remaining

ans all parts of any ques. at 1 place.

Time: three Hrs.
Max. Marks: 100

1. Explain:
a. Asymtotic Notation.
b. Lower Bounds.
c. NP-hard issues.
d. Minimal spanning Tree.
e. Convex Hull issue.
f. Memory Functions.
g. Topological Sorting.

2. define divide and conquer strategy for multiplying 2 n-bit numbers. Derive its time complexity.


3. a. discuss quick sort Algorithm.
b. Show how the quick sort algorithm sorts the subsequent sets of keys.
(1,1,1,1,1,1,1) and (5,5,8,3,4,3,2)

4. a. discuss how you can use greedy technique for Huffman coding.
b. discuss the greedy technique with knopsack issue as an example.

5. discuss issue Reduction using linear programming as an example.

6. discuss Dynamic Programming Technique for construction of optimal binary search trees with the help of an example.

7. Outline Template of a backtracking algorithm. discuss a backtracking solution to the Hamiltonian circuit issue.

8. discuss branch and bound technique. Apply it to the subsequent instance of Assignment issue.

Job1 Job2 Job3 Job4
Person A nine two seven eight
Person B six four three seven
Person C five eight one eight
Person D seven six nine four

Earning:   Approval pending.