QUESTION BANK 2020

SIDDHARTH INSTITUTE OF ENGINEERING & TECHNOLOGY :: PUTTUR

Siddharth Nagar, Narayanavanam Road – 517583

MODEL QUESTION BANK( DESCRIPTIVE)

Subject with Code :Design and Analysis of Algorithms(18MC9122) Course & Branch: MCA
Year & Sem: II-MCA& II-Sem Regulation: R18

UNIT –I
Introduction& Divide and Conquer
1. a. Explain the properties of an algorithm with an example. [4M]
b. Give the algorithm for matrix multiplication and find the time complexity of the algorithm using step
count method. [8M]
2.Write Divide – And – Conquer recursive Merge sort algorithm and derive the time complexity of this
algorithm. [6M]
3.a. Differentiate between Bigoh and omega notation with example. [6M]
b.Distinguish between Algorithm and Psuedocode. [6M]
4.a.Define time complexity and space complexity. Write an algorithm for adding n natural numbers and
find the space required by that algorithm. [7M]
b.What are the different mathematical notations used for algorithm analysis. [5M]
5. List out the steps that need to design an algorithm. [5M]
6.Explain how many algorithms can you write for solving find the prime numbers. Compare which is the
simplest and the most efficient. [8M]
7.a. Differentiate between Best, average and worst case efficiency. [6M]
b.Explain Strassen's algorithm for matrix multiplication with the help of an example. [6M]
8.a. Discuss the concepts of asymptotic notations and its properties. [7M]
b.What do you mean by randomization? [5M]
9.Discuss the General plan for analyzing efficiency of Non recursive & Recursive algorithms Understand
and Selection Sort with example? [12M]
10. a. What do you mean by dynamic programming? [5M]
b. Describe asymptotic notation. [7M]
11. Define Merge sort with example. [8M]
12. Describe Quick Sort with suitable example. [8M]

DESIGN AND ANALYSIS OF ALGORITHMS Page 1

QUESTION BANK 2020

UNIT –II
Greedy Method and Dynamic Programming
1.What is a Minimum Cost Spanning tree? Explain Kruskal’s Minimum cost spanning tree algorithm
with suitable example. [8M]
2. Explain how Matrix – chain Multiplication problem can be solved using dynamic programming with
suitable example. [12M]
3. a. Why do we perform topological sorts only on DAGs? Explain [8M]
b.Explain the applications of depth first search algorithm. [5M]
4. a. State the Greedy Knapsack Problem. [6M]
b.Find an optimal solution to the knapsack instance n=4 objects and the capacity of knapsack m=15,
profits (10, 5, 7, 11) and weight are (3, 4, 3, 5). [6M]
5. a. Explain Recursive Binary search algorithm with suitable examples. [5M]
b.Write Control Abstraction of Greedy method. [7M]
6. a. Explain partition exchange sort algorithm and trace this algorithm for n =8 elements: 24,12, 35,
23,45,34,20,48. [6M]
b. Differentiate between greedy method and dynamic programming. [6M]
7. a. Explain the general principle of Greedy method and also list the applications of Greedy method.[6M]
b. Explain the Travelling sales man problem. [6M]
8. a. Explain the greedy technique for solving the Job Sequencing problem. [6M]
b.What is Minimum cost spanning tree? Explain an algorithm for generating minimum cost spanning
tree and list some applications of it. [6M]
9. a. Write the algorithm to compute 0/1 Knapsack problem using dynamic programming and explain it.
[7M]
b. Explain the Single source shortest path problem with an example. [5M]
10. a.What is the time complexity of the Job sequencing with deadlines using greedy algorithm? [6M]
b.State the principle of optimality. Find two problems for which the principle does not hold.[6M]
11. Briefly explain Multistage graphs with suitable examples? [5M]
12. Describe job scheduling with deadlines? [5M]

DESIGN AND ANALYSIS OF ALGORITHMS Page 2

QUESTION BANK 2020

UNIT –III
Basic Traversal and Search Techniques , Back Tracking
1. Explain any one application back tracking with example? [8M]
2. Describe in detail 8-queens problem using back tracking? [8M]
3.Explain 0/1 knapsack problem by using backtracking with an examples? [7M]
4.Briefly explain the optimal binary search trees with example? [7M]
5. Describe in detail graph coloring using back tracking? [8M]
6. Explain 0/1 knapsack problem by using dynamic programming with an examples? [8M]
7. Explain DFS with suitable example? [5M]
8. What is Spanning trees explain with suitable examples? [6M]
9. Describe Bi-connected components. [6M]
10. Determine Sum of subsets problem? [5M]
11. Explain techniques for binary trees? [7M]
12. Discuss about Connected Components. [5M]
13. What are the Techniques about Graphs explain it? [5M]
14. Explain Hamiltonian cycles with examples. [8M]

UNIT –IV
Branch and Bound, Lower Bound Theory
1.Explain the general method of branch and bound?[12M]
2.Apply branch and bound to 0/1 knapsack problem and elaborate it?[8M]
3.3.Explain the method of reduction to solve TSP problem using branch and bound? [12M]
4.Explain the principles of FIFO branch and bound? [8M]
5. a. Explain the properties of LC-search? [6M]
b. Explain control abstraction of LC-branch and bound?[6M]
6. Briefly explain the FIFO brach and bound solution with example? [12M]
7. Briefly explain the LC brach and bound solution with example? [12M]
8. State 0/1 knapsack problem and design an algorithm of LC Branch and Bound and find the solution for
the knapsack instance with any example? [12M]
9.Explain any one application of branch and bound? [12M]
10. Apply the branch-and- bound technique in solving the travelling salesman problem? [12M]

DESIGN AND ANALYSIS OF ALGORITHMS Page 3

QUESTION BANK 2020

UNIT –V
NP – Hard and NP – Complete Problems, Reductions
1.a. How are P and NP problems related? [6M]
b. Differentiate Time Efficiency and Space Efficiency.[6M]
2.Compare NP-hard and NP-completeness?[7M]
3.Write the non-deterministic sorting algorithm and also analyze its complexity? [12M]
4. Explain the class of P and NP with example? [12M]
5. Differentiate between NP- complete and NP-hard problems? [12M]
6. State and explain cook’s theorem? [12M]
7. Explain the strategy to prove that a problem is NP-hard? [12M]
8. Explain the satisifiability problem and write the algorithm? [12M]
9. What is halting problem explain with an example? [12M]
10. Briefly explain the classes NP-hard and NP-complete? [12M]
11. .Discuss the general plan for analyzing Time efficiency of recursive algorithm.[8M]
12. Explain Reduction Source Problems.[7M]

Prepared by: DR. A. SWARUPA RANI, Assoc. Professor, Dept. of MCA

DESIGN AND ANALYSIS OF ALGORITHMS Page 4