CS1251 Design & Analysis of Algorithm Question Bank : kings.ac.in

Name of the College : Kings College Of Engineering
Department : Computer Science & Engineering
Subject : Design & Analysis of Algorithm
Website : https://www.kingsengg.edu.in/
Document Type : Question Bank

Download Model/Sample Question Paper : https://www.pdfquestion.in/uploads/ki…in/303-daa.pdf

Kings Design & Analysis of Algorithm Question Paper

Design & Analysis of Algorithm Question Bank

Related : Kings College Of Engineering EC1451 Mobile & Wireless Communication Question Bank : www.pdfquestion.in/1305.html

Unit I – Algorithm Analysis

Part-A (2 Marks)
1. Define algorithm.
2. What is big ‘Oh’ notation?
3. Define Loop.
4. What are the two different types of recurrence
5. State the best case and worst case analysis for linear search.
6. Solve the recurrence equation. T (n) =2T (n-1) +n2^n+n2.
7. Give the recurrence equation for the worst case behavior of merge sort.
8. What is the average case complexity of linear search algorithm?

Part-B :
1. (a). Define the asymptotic notations used for best case average case and worst case analysis of algorithm. (8)
(b)Write an algorithm for finding maximum element of an array; perform best and average case complexity with appropriate order notations. (8)

2. Write an algorithm to find mean and variance of an array perform best, worst and average case complexity, defining the notations used for each type of analysis.(16)
3. Derive the recurrence relation for Fibonacci series,perform complexity analysis for the same. (16)
4. Explain the various asymptotic notations with the properties. (16)
5. Explain linear search with example (16)

Unit II – Divide And Conquer

Part-A (2 Marks) :
1 Define Substitution method.
2 Analysis the various cases of complexity for Binary search.
3 Define Control Abstraction.
4 Define Knapsack problem.
5 What is the computing time of DAndC.

6 Write the complexity of divide and Conquer algorithms.
7 Sort the numbers using merge sort.
8 List out the disadvantage of merge sort.
9 What are the four feasible solutions for n=3,m=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=18,15,10).
10 Give the time efficiency and drawback of merge sort algorithm.

11 Write a pseudo code for a divide and conquer algorithm for finding the position of the largest element in an array of N numbers.
12 What is recursive call?
13 What are objectives of sorting Algorithms?
14 List out any two drawbacks of binary search algorithm.
15 Write the procedure for selection sort.

Part-B :
1. Explain Knapsack Problem (16).
2. Explain the algorithm for maximum and minimum numbers in an array. (16)
3. (a) Give a detailed note on Divide and Conquer techniques.(6)
(b). Sort the following set of elements using merge sort (10) 12,24,8,71,4,23,6,89,56
4. Write An algorithm for searching an element using Binary search method. Give an example. (16)

5. (a) write a pseudo code for a divide and conquer algorithm for merging two sorted arrays into a single sorted one. Explain with an example. (12)
(b) Setup an solve a recurrence relation for the number of key comparisons made by the above pseudo code. (4)

6.(a) Write an algorithm to sort a set of N numbers using insertion sort.(8)
(b) Trace the algorithm for the following set of numbers. 20,35,18,8,14,41,3,39.
7. Explain in detail merge sort. Illustrate the algorithm with a numeric example. Provide complete analysis of the same (16)

Unit III – Dynamic Programming

Part-A (2 Marks) :
1. Write any four examples for Brute Force Approach.
2. Define Dynamic programming.
3. Define multistage graph problem.
4. What is the difference between forward & backward approach?
5. Define all-pair shortest path problem.

6. Define Optimal Binary Search trees.
7. What is 0/1 Knapsack.
8. What is the procedure to solve traveling Salesman problem.
9. Differentiate non preemptive & preemptive scheduling.
10. List out the advantages of Dynamic programming.

Unit IV – Backtracking

Part-A(2 Marks) :
1. What is m-colorability optimization?
2. Define sum of subsets problem.
3. What is chromatic numbers?
4. Define Backtracking.
5. What are the applications of backtracking?

6. What are the algorithm design techniques?
7. Define n-queens problem.
8. Define Hamiltonian Circuit problem in an undirected Graph.
9. What is state space tree?
10. State the principle of Backtracking.
11. State if Backtracking always produces optimal solution.

Part-B :
1. What is Backtracking? Explain in detail. (16)
2. Explain Subset-sum Problem & Discuss the possible solution strategies using backtracking. (16)
3. Discuss the use of greedy method in solving knapsack problem and subset sum problem. (16)

4. Write short notes on
(a) Graph coloring (8)
(b) 8-Queens problem (8)
5.Apply Backtracking technique to solve the following instance of the subset sum problems.s=(1,3,4,5) & d=11 (16)
6. Explain subset-sum problem and discuss the possible solution strategies using backtracking. (16)

7. Explain 8-Queens problem with an algorithm. Explain why backtracking is defined as a default procedure of last resort for solving problems. (10+6)
8. Using Backtracking enumerate how can you solve the following problems
(a) 8-queens problem (8)
(b) Hamiltonian circuit problem (8)