DAA Question Bank
Note:
Don’t bother about the no. of questions (count) given here for each unit. All are
gathered from previous years question papers. Observe the questions how the
concepts are asking in different ways.
First understand the concepts and then practice example for each one (if
possible, practice Algorithms also).
In Exam, for each question first write about the concept and then explain with
an example.
Write neatly with side headings and points wise (Except definitions, don’t write
any paragraphs).
Attempt all questions and for out of questions or indirect questions, try to write
relevant information but don’t leave (There are more chances to get pass or
good marks).
Preparation order: UNIT-1,UNIT-2,UNIT-3,UNIT-5,UNIT-4 (Don’t leave any full
unit as your choice, prepare known concepts at least)
********All the Best********
UNIT-1 Questions
1. What is an algorithm? Explain its characteristics in detail?
2. Write different pseudo code conventions used to represent an algorithm.
3. What is space complexity? Illustrate with an example for fixed and variable part
in space complexity.
4. What is an asymptotic notation? Explain different types of asymptotic
notations with examples.
5. What do you mean by performance analysis? Give the algorithm for matrix
multiplication and find the time complexity of the algorithm using step–count
method.
6. Using step count method, analyze the time complexity of procedure to add two
m x n matrices.
7. What do you mean by performance analysis? Derive the run time complexity of
a non-recursive Fibonacci series algorithm using tabular method.
8. What do you mean by Amortized Complexity? Give an example.
9. What is time complexity? Explain the different methods of finding the time
complexity with examples.
10. Give the algorithm for transpose of a matrix of size mxn and determine
the time complexity of the algorithm by frequency – count method.
11. What is Randomized Algorithm and write different types of randomized
algorithms?
12. What is a Set & Disjoint set? Write about union and find operations.
13. What is graph traversal and Explain Breadth First Search Traversal (BFS)
with an example?
14. What is graph traversal and Explain Depth First Search Traversal (DFS)
with an example?
15. What is connected component and spanning trees?
16. What is an articulation point and how to find articulation points in the
graph?
17. What is Biconnected graph and how to find Biconnected components in a
graph?
UNIT-2 Questions
1. Write any two differences between divide-and-conquer and greedy method.
2. Discuss the working strategy of merge sort and illustrate the process of
merge sort algorithm for the given data: 43, 32, 22, 78, 63, 57, 91 and 13.
3. Describe binary search in detail and provide time complexity analysis with an
example.
4. Describe the time complexity of Divide and Conquer in the recurrence form.
5. Illustrate the tracing of quick sort algorithm for the following set of numbers:
25, 10, 72, 18, 40, 11, 64, 58, 32, 9.
6. With a suitable algorithm, explain the problem of finding the maximum and
minimum items in a set of n elements.
7. Give the general idea of Divide & Conquer algorithms.
8. Apply Merge Sort to sort the list a[1:10]=(31,28,17,65,35,42.,86,25,45,52).
Draw the tree of recursive calls of merge sort, merge functions.
9. What are different approaches of writing randomized algorithm? Write
randomized sort algorithms.
10. Write a recursive algorithm for binary search and also bring out its
efficiency.
11. Explain divide-and-conquer technique; write a recursive algorithm for
finding the maximum and minimum element from the list.
12. Explain the Recursive Binary search algorithm with suitable examples.
13. Derive the time complexity of the Quick sort algorithm for the worst case.
14. Illustrate the tracing of quick sort algorithm for the following set of
numbers: 25, 10, 72, 18, 40, 11, 64, 58, 32, 9.
15. State the KNAPSACK problem. What is the difference between
KNAPSACK and 0/1 KNAPSACK problem?
16. Write a greedy algorithm for sequencing unit time jobs with deadlines
and profits.
17. What is optimal merge pattern? Find optimal merge pattern for ten files
whose record lengths are 28, 32, 12, 5, 84, 53, 91, 35, 3, and 11.
18. Define Minimum Cost Spanning Tree and list its applications..
19. Write and explain Prism’s algorithm for finding minimum cost spanning
tree of a graph with an example.
20. State Container Loading problem and explain with suitable example?
21. State the general principle of greedy algorithm.
UNIT-3 Questions
1. State the KNAPSACK problem. What is the difference between KNAPSACK and
0/1 KNAPSACK problem?
2. Write and explain an algorithm to compute the all pairs shortest path using
dynamic programming and prove that it is optimal.
3. Solve the following instance of 0/1 KNAPSACK problem using Dynamic
programming n = 3, (W1, W2, W3) = (2, 3, 4), (P1, P2, P3) = (1, 2, 5), and m = 6.
4. What is meant by bottom-up dynamic programming?
5. Differentiate between divide-and-conquer and dynamic programming
6. Explain the methodology of Dynamic programming. Mention the applications of
Dynamic programming.
7. Write Bellman and Ford algorithm to compute shortest paths.
8. Present the dynamic programming solution for single sources shortest path
problem. Analyze its time complexity.
9. Find the all pairs shortest path solution for the graph represented by below
adjacency matrix:
10. Define merging and purging rules in 0/1 knapsack problem and explain with an
example.
11. Design a three stage system with device types D1, D2, D3. The costs are $30, $15,
$20 respectively. The cost of the system is to be not more than $105 and the
reliability of each device type is 00.9, 0.8 and 0.5 respectively.
12. Construct an optimal travelling sales person tour using Dynamic Programming
for
the given data:
0 10 9 3
5 0 6 2
9 6 0 7
7 3 5 0
13. Discuss the time and space complexity of Dynamic Programming traveling sales
person algorithm.
UNIT-4 Questions
1. What is a backtracking? Give the explicit and implicit constraints in 8
queen’s problem.
2. Explain the Graph – coloring problem. And draw the state space tree for m=
3 colors n=4 vertices graph. Discuss the time and space complexity.
3. Write an algorithm for N – queen’s problem. Give time and space
complexity for 8 – queen’s problem.
4. What is a Hamiltonian Cycle? Explain how to find Hamiltonian path and
cycle using backtracking algorithm.
5. Discuss the 4 – queen’s problem. Draw the portion of the state space tree
for n= 4 queens using backtracking algorithm.
6. Draw the portion of state space tree generated by FIFO BB for the job
sequencing with deadlines instance n=5, (p1,p2,..,p5) =(6,3,4,8,5), (t1,t2,..t5)
= (2,1,2,1,1) and (d1,d2,..,d5)=(3,1,4,2,4).What is the penalty corresponding
to an optimal solution.[8M]
7. Draw the portion of state space tree generated by LCBB for the 0/1
Knapsack instance: n = 5, (p1,p2,…,p4) = (10,15,6,8,4), (w1,w2,..,w5) =
(4,6,3,4,2) and m=12. Find an optimal solution using fixed – tuple sized
approach.
8. Explain the LCBB 0/1 Knapsack problem procedure with the knapsack
instance for n=4.m=15,(p1,p2,p3,p4)=(10,10,12,18) (w1,w2,w3,w4) =(2, 4, 6,
9). Draw the portion of the state space tree and find optimal solution. What
is LC – Search? Discuss LC – Search algorithm.
9. Explain Travelling sales person problem LCBB procedure with the following
instance and draw the portion of the state space tree and find an optimal
[ ]
∞ 20 30 10 11
15 ∞ 16 4 2
tour. 3 5 ∞ 2 4
19 6 18 ∞ 3
16 4 7 16 ∞
10. Draw the portion of state space tree generated by FIFO BB for the 0/1
Knapsack instance: n = 5, (p1,p2,…,p4) = (10,15,6,8,4), (w1,w2,..,w5) =
(4,6,3,4,2) and m=12. Find an optimal solution using fixed – tuple sized
approach.
UNIT-5 Questions
1. What is NP, NP Hard and NP Completeness? Write their differences?
2. Explain cook’s theorem?
3. Explain about NaÏve String Matching Algorithm with example and write its
drawbacks?
4. Explain about Knuth-Morris-Pratt Algorithm with example?
5. What is string matching? Explain Rabin-Karp Algorithm with example?
6. Write about Tries and Suffix Tree.