Code No.
F-12183/CBCS
FACULTY OF INFORMATICS
M.C.A. (2 Years Course) II-Semester (CBCS) (Backlog) Examination, March /April 2024
Subject: Design and Analysis of Algorithms
Time: 3 Hours Max. Marks: 70
Note: I. Answer one question from each unit. All questions carry equal marks.
II. Missing data, if any, may be suitably assumed.
Unit – I
1. a) What are the characteristics of an Algorithm? How to evaluate the performance of an
Algorithm?
b) Explain about Randomized Algorithms.
5
(OR)
30
2. a) What is Queue? Explain about various Queue Operations.
b) Give an account on Graph Data Structures.
-1
Unit – II
3. a) Define Divide and Conquer? Illustrate the algorithm for merging two sorted sets using Auxiliary
Storage.
U
b) Discuss about Strassen's Matrix Multiplication Problem.
(OR)
O
4. a) Describe the Algorithm for greedy strategies for the knapsack problem.
b) Explain about the Greedy algorithm for sequencing unit time jobs with deadlines and profits.
Unit – III
5
5. a) Discuss about Multistage graph algorithm corresponding to forward approach.
30
b) Explain about the algorithm for all pairs shortest path Problem.
(OR)
-1
6. a) What is Binary Tree? Describe in order and pre order traversal techniques with example.
b) Illustrate the Breadth First Search Algorithm with Example.
Unit – IV
U
7. a) What is Back Tracking? Explain about Recursive Backtracking Algorithm.
b) Discuss about the solution for 8-Queens Problem.
O
(OR)
8. a) Explain about Graph Coloring Problem.
b) Discuss about Travelling Salesperson Problem.
Unit – V
9. a) Illustrate Cook’s Theorem.
b) Give an account on Non-Deterministic Sorting Algorithm.
(OR)
10. a) Discuss about Node Cover Decision Problem.
b) Explain about NP-Hard Code Generation Problem.
**
