SCHOOL OF ENGINEERING AND TECHNOLOGY
QUESTION BANK
Programme: B.Tech AIDS/CSE Course Code :21CSE07
Semester: V CourseTitle: Design and Analysis of Algorithm
UNIT: 1 ANALYSIS & DIVIDE-AND-CONQUER
2 Marks
1. How do you measure the efficiency of an Algorithm
2. Define recursion.
3. Prove that f(n)= O(g(n)) and g(n)=O(f(g(n)) then f(n)=(g(n))
4. What is an Algorithm?
5. How to measure algorithm’s running time?
6. Define recurrence relation
7. Write down the properties of asymptotic notations.
8. Define Big Theta Notations
9. Define Big Omega Notations
10. What is Big ‘Oh’ notation?
11. What are six steps processes in algorithmic problem solving?
12. What are the basic asymptotic efficiency classes?
13. List the factors which affects the running time of thealgorithm
14. What is the order of growth?
15. State the Convex Hull Problem.
16. What is the time and space complexity of Merge Sort?
17. State Master’s Theorem
18. What is Divide and Conquer Algorithm
19. What meant by substitution method and its types
15 MARKS
20. Elaborate Asymptotic analysis of an algorithm with an example.
21. Discuss Fundamentals of the analysis of algorithm efficiency elaborately
22. Explain about Strassen’s matrix multiplication method with example
23. Explain about recurrence relations with example
24. Explain about master and substitution method with example
UNIT-2 GREEDY & DYNAMIC PROGRAMMING
25. State the Principle of Optimality
26. How Dynamic Programming is used to solve Knapsack Problem?
27. Define the Minimum Spanning tree problem
28. What does Floyd’s Algorithm do?
29. Define the Single Source Shortest Path Problem
30. List out the memory function under dynamic programming
31. List the advantage of Huffman’s encoding?
32. What do you mean by Huffman code?
33. What is greedy method?
34. Compare Greedy method and Dynamic Programming
35. Show the general procedure of dynamic programming
36. Define Kruskal Algorithm
37. What is Huffman trees?
38. Define multistage graph. Give Example
39. Define transitive closure of directive graph
40. What is the Constraint for binary search tree for insertion?
41. Compare Greedy method and Dynamic programming
42. What are the drawbacks of dynamic programming?
43. Show the general procedure of dynamic programming
44. Write some applications of traveling salesperson problem
15 MARKS
45. Explain Kruskal's Algorithm
46. Discuss Prim's Algorithm in detail.
47. Write short note on Single source shortest path problem
48. What does All pairs shortest path problem with example
49. Explain how to Floyd’s Algorithm works.
Discuss Dijkstra’s algorithm for solving the Single Source Shortest Path problem. Provide a
50.
step-by-step example
Solve the Traveling Salesperson Problem (TSP) using dynamic programming and
51. explain the step-by-step approach.
52. Explain Greedy approach.
53. Explain Longest common subsequence method.
UNIT-3 BACKTRACKING & BRANCH-AND-BOUND
54. Compare backtracking and branch bound techniques
What are the searching techniques that are commonly used in Branch-and-
55.
Bound method.
56. Illustrate 8 – Queens problem
57. Show the purpose of lower bound
58. Show the application for Knapsack problem
59. Define Branch-and-Bound method
60. List the factors that influence the efficiency of the backtracking algorithm?
61. Define Hamiltonian cycle
62. Define knapsack problem
63. Define travelling sales man problem
64. Define sum of subsets problem
65. What are the principle followed for branch and bound?
66. What u meant by row minimization and column minimization?
67. What is the use of TSP?
68. List the application of backtracking technique?
69. Define backtracking?
70. What is heuristic
What are the additional items are required for branch and bound compare to
71.
backtracking technique?
What are the searching techniques that are commonly used in Branch-and-
72.
Bound method.
73. Show the purpose of lower bound.
15 Marks
Elaborate how backtracking technique can be used to solve the n-queens
74.
problem. Explain with an example.
75. Explain Backtracking technique.
Explain how branch and bound method can be used to solve travelling sales man
76.
problem
77. Explain about graph coloring problem in detail
78. Explain about knapsack problem in detail
79. UNIT: 4 STRING MATCHING & PARALLEL ALGORITHMS
80. Define Naive Algorithm
81. Define Knuth-Morris-Pratt (KMP) Algorithm
82. Define Boyer-Moore Algorithm
83. Define the String matching Problem
84. What are all the types of parallel algorithms?
85. What is the partial match in the KMP algorithm? Explain with an example.
86. Define PRAM.
What is the time complexity of Odd-Even Merge Sort in a parallel computing
87.
model?
88. What is Bitonic sorting?
89. Describe the bad character heuristic in the Boyer-Moore algorithm.
90. What is a parallel algorithm? How does it differ from a sequential algorithm?
91. What is List Ranking in parallel algorithms? How is it useful?
92. What are the key advantages of parallel algorithms?
What is the KMP algorithm? How does it improve over the naive string matching
93.
algorithm?
94. How does the Odd-Even Merge Sort algorithm utilize parallelism in sorting?
95. What is the time complexity of Bitonic Sort in a parallel model?
96. What is the significance of parallelism in algorithms?
What is the role of the partial match table (also known as the "prefix function")
97.
in the KMP algorithm?
98. Write the step-by-step explanation of Boyer-Moore algorithm.
99. How does the KMP algorithm handle mismatches?
100. What are the applications of Bitonic sorting?
101. What are the pros and cons of the Odd-Even Merge Sort algorithm?
102. Compare and contrast Odd-Even Merge Sort and Bitonic Sort.
15 Marks
Explain the KMP string matching algorithm in detail. Illustrate its working with an
103.
example and discuss its time complexity.
Describe the Boyer-Moore string matching algorithm. How does it use both the
104.
bad character rule and the good suffix rule? Provide an example.
Discuss the PRAM model in parallel computing. Explain its types and how it helps
105.
in designing parallel algorithms.
Explain the Odd-Even Merge Sort algorithm in parallel computing. Provide a
106.
detailed example and analyze its parallel time complexity.
Describe the Bitonic Sort algorithm. How does it work in parallel environments?
107.
Compare its time complexity with other parallel sorting algorithms.
Unit-5 NP PROBLEMS & APPROXIMATION ALGORITHMS
108. Define NP Completeness and NP Hard
109. State Hamiltonian Circuit Problem
110. Define P and NP Problems
111. Define sum of subset Problem
112. When is a problem said to be NP Hard?
113. Define Absolute approximation
114. Compare NP- hard and Np-complete problems
115. What is meant by approximation algorithm
116. Features of Approximation algorithms
117. What is Absolute approximation?
118. What is Relative approximation?
119. Write short notes on FIFO search
120. Write short notes on LIFO Search
121. What is Hamiltonian cycle in an undirected graph?
122. What is Feasible solution?
123. What is optimal solution?
124. What are tractable and non tractable problems ?
Show the time complexity and space complexity of traveling salesperson
125.
problem
126. Define NP Complete problems
127. Define NP Completeness problems
15marks
128. Explain P, NP and NP complete problems.
Outline the steps to find approximate solution to NP-Hard optimization problems
129.
using approximation algorithms with an example
130. Discuss the approximation algorithm for NP hard problems.
131. Explain in detail about LIFO Search
132. Write short notes on FIFO search
PO-CO Mapping Table for Design and Analysis of Algorithms
PO/PSO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3
CO
21CSE07 3 - - - - - - - - - - 1 3 2 2
21CSE07 2 3 2 2 - - - - - - - 1 3 3 1
21CSE07 2 3 2 2 - - - - - - - 1 3 3 1
21CSE07 2 3 2 2 - - - - - - - 1 3 3 1
21CSE07 1 2 2 2 - - - - - - - 1 3 3 1
Average 2.0 2.8 2.0 2.0 - - - - - - - 1.0 3.0 2.8 1.2
Correlation levels 1, 2 or 3 are as defined below:
1: Slight (Low) 2: Moderate (Medium) 3: Substantial
(High) No correlation: “-”
