LORDS INSTITUTE OF ENGINEERING AND TECHNOLOGY
Approved by AICTE/Affiliated to Osmania University/ Estd.2002.
Department of Information Technology
DAA Question Bank
Unit-1:
Short Answer Questions:
1. What is an algorithm? State & Explain basic properties of an algorithm
2. Describe the characteristics of an algorithm with an example
3. What is Asymptotic Notation?
4. Define O, Omega and Theta.
5. What is Algorithm specification?
6. Define Space complexity and Time complexity.
7. Solve the recurrence relation T(n)=9T(n/3)+n.
8. What do you mean by performance analysis of an algorithm? Explain.
9. Solve the recurrence relation
T(n) = T(1) n=1
aT(n/b)+f(n) n>1
for a=2, b=2, T(1)=2 and f(n)=n
10. Solve: T(n)=3T(n/3)+√n
Long Answer Questions:
1. What is asymptotic complexity of an algorithm
2. What is performance analysis? Compute the performance for iterative sum and recursive sum through step
count method.
3. Write the recursive and iterative algorithms for finding the reverse of a given string and analyze time and
space complexities.
4. For T(n)=7T(n/2)+18n2 Solve the recurrence relation and find the time complexity
5. Explain asymptotic notations, Big Oh, Omega and Theta
Unit-2
Short Answer Questions:
1. Write a control abstraction for Divide and Conquer approach.
2. Compare Quick sort vs Merge sort.
3. Differentiate Divide and Conquer and Transfer and Conquer
4. What is a Balanced Search Tree
5. Define Heap.
Long Answer Questions:
1. Write Binary search algorithm and analyze its time complexity.
2. L={2,12,18,3,34, 27, 56, 4, 8, 3, 10} write and explain the merge sort algorithm that outputs the sorted list
of elements.
3. Explain heap sort with the help of example.
4. Demonstrate sorting the following list using Quick sort with 1st element as a pivot { 5,2,3,10,11,6,1,12,4}
5. Write an algorithm for merge sort and write time complexities
6. Write an algorithm to sort N numbers in descending order using Quick sort and analyze time complexity in
best, average and worst cases.
7. Write an algorithm to form a heap using “Heapify” and discuss about its time complexity.
Explain step by step heap sort with example and write an algorithm for heap sort.
Unit-3
Short Answer Questions:
1. Define feasible solution.
2. What is dynamic programming?
3. What is 0/I knapsack problem?
4. Explain optimal binary search tree
5. State traveling salesperson’s problem.
6. What is multistage graph?
7. Explain dominance rules in 0/1 Knapsack problem.
8. Define minimum cost spanning tree.
9. What is greedy method? List out application?
10. Explain how cost of Optimal Binary Search Tree is measured.
Long Answer Questions:
1. Briefly argue how principle of optimality holds for 0/I knapsack problem. Generate the sets Si, 0 ≤ i ≤ 4
where (w1,w2,w3,w4) = (10,15,6,9) & (p1,p2,p3,p4) = (2, 5, 8, 9) state the purging rules if knapsack
capacity is m = 25. What is optimal solution.
2. Write about single source shortest path, All pairs shortest path, Optimal Binary Search Trees
3. Find an optimal solution to the knapsack instance n=3, M=20, (P1,P2,P3)=(24,25,15) and
(W1,W2,W3)=(18,15,10).
4. Write Prims Algorithm and explain the example to find minimum spanning tree
5. Find the minimum cost spanning tree for the graph given below.
6. What is the optimal solution generated using greedy approach for job scheduling with deadlines when n =7,
(P1, P2, …, P7) = (3, 5, 20, 18, 1, 6, 30) and (d1, d2, ….,d7) = (1, 3, 4, 3, 2, 1, 2), where n is number of
jobs, Pi is profit of ith job, di is deadline of ith job.( i = 1 to 7)
7. Explain multistage graph with the help of example.
8. Use an algorithm for greedy strategies for the knapsack to find an optimal solution to the knapsack instance
n=7,m=15,(p1,p2….,p7)=(10,5,15,7,6,18,3),and (w1,w2,…w7)=(2,3,5,7,1,4,1)
9. Apply greedy algorithm to generate single-source shortest path with an example graph. Mention its time
complexity
Derive the time complexity of job sequencing with deadlines. Obtain the optimal solution when n=5,
(p1,p2…)=( 3,3,1,1) q(0:4)=(20,15,10,5,1) and(d1,d2,..)=(2,2,1,3,3)
10. What is minimum Spanning Tree? Explain Kruskal’s Algorithm and trace it step by step using the graph
given below
Unit-4
Short Answer Questions:
1. What is meant by pattern matching.
2. What is a chromatic number?
3. State Cook’s theorem.
4. Define P, NP and NP hard.
5. Define satisfiability problem
6. Define NP hard and NP Complete
Long Answer Questions:
1. Write and explain Brute Force Matching algorithm with the help of example.
2. Explain KMP algorithm for string matching
3. Explain decision problem.
4. State and prove Cook’s Theorem.
5. Compare and construct between NP hard and NP Complete.
Unit-5
Short Answer Questions:
1. Denote live node and dead node with example.
2. Compare LC and FIFO brand- and-bound
3. Define Implicit constraints and Explicit constraints with example.
4. What is branch and bound algorithm? How it is different from backtracking?
Long Answer Questions:
1. Describe an algorithm to solve 8-queen problem and Show the state space tree.
2. Write an algorithm for finding all m-coloring of a graph with example.
3. Generate FIFO branch and bound solution for the given knapsack problem. m = 15, n = 3. (P1 P2 P3) =
( 10, 6, 8 ) (w1 w2 w3) = ( 10, 12, 3 )
4. Find all possible subsets of w that sum to m. Let w={5,7,10,12,15,18,20}and m=35 and draw the portion of
the state space tree that is generated.
5. Describe about Control Abstractions for LC-search.
6. Draw the portion of the state space tree generated by LCBB for the knapsack instance:
(a) n=5,(p1,p2,p3,p4,p5)=(w1,w2,w3,w4,w5)=(4,4,5,8,9), and m=15.
(b) n=5,(p1,p2,p3,p4,p5)=(10,15,6,8,4),(w1,w2,w3,w4,w5)=(4,6,3,4,2), and m=12.
7. Explain different types of tries with an example
(a) Standard Tries
(b) Suffix Tries
(c) Compressed Tries
