MANGALORE INSTITUTE OF MANAGEMENT & SCIENCE
# 68, Ullal Main Road, Near, Bangalore University Qtrs, Bangalore-560056
PREPARATORY EXAM – JULY 2023
IV Semester BCA – DESIGN AND ANALYSIS OF ALGORITM
Time: 2 hours 30 minutes REG NO: Max. Marks: 60
Instruction: Answer any FOUR questions from each part
PART- A
I. ANSWER ANY 4 QUESTIONS Each question carries 2 marks 4x2=8
1. List the methods of computing the time efficiency of algorithm.
2. Write the diagrammatic representation of Decrease- by- a-constant.
3. Define Space and Time Trade-off’s.
4. Define Greedy Technique
5. Define Principle of Optimality.
6. What is Hamiltonian Circuit problems?
PART-B
II. ANSWER ANY 4 QUESTIONS Each question carries 5 marks 4 x 5 = 20
7. With a note on combinatorial problem.
8. Write a note on Fake coin problem.
9. Write a program to find an using Brute- Force based algorithm.
10.Write DIJIKKSTRA’s algorithm to find the shortest path from a given vertex.
11. Write the Huffman’s algorithm construct an optimal prefix code.
12. Construct a solution space tree for a set S={11,13,24,7} and M=31.
PART-C
III. ANSWER ANY 4 QUESTIONS Each question carries 8 marks 4 x 8 = 32
13.Explain the mathematical Analysis for finding the duplicate elements in an Array.
14. Explain how to generate optimal BST using Dynamic Pramming.
15. Explain N-Queens Problem. Solve 4-Queens Problem and Write the solution space tree.
16.Apply Warshall’s algorithm to the following graph
17. Apply DIJIKSTRA’s algorithm for the following graph.
18.Find the optimal solution for a Knapsack problem with M=40,N=4,{w1,w2,w3,w4}={20,25,10,15} and
[p1,p2,p3,p4]=[20,40,35,45].
********ALL THE BEST********
