QUESTION BANK
Subject: Analysis and Design of Algorithms
Class: IV Semester
Module-1
1. With a neat diagram, explain the different steps in designing and analyzing an
algorithm
2. Define an algorithm. Explain the asymptotic notations Big Oh, Big Omega,
and Big Theta notations
If t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)), then show that t1(n) + t2(n) ∈
3. Prove the following theorem
O(max{g1(n), g2(n)}).
4. Explain the general plan for analyzing the efficiency of a recursive algorithm.
Suggest a recursive algorithm to find the factorial of a number. Derive its
efficiency
5. Explain the general plan for analyzing the time efficiency of Recursive
algorithms and also analyze the time efficiency of the Tower of Hanoi
Recursive Algorithm.
6. Explain the general plan for analyzing the efficiency of a non-recursive
algorithm. Suggest a non-recursive algorithm to find the maximum element in
the list of n numbers. Derive its efficiency
7. Compare the orders of growth of
a. ½ n(n-1) and n2
b. n! and 2n
c. log2 n and √n
8. Write an algorithm for Selection sort, Bubble sort, and apply both algorithms to
sort
the given list 89, 45, 68, 90, 29, 34, 17
9. Outline an algorithm for Sequential Search and derive its time efficiency.
10. Explain the Brute Force String Matching Algorithm with its efficiency
Module-2
1. Explain the Travelling Salesman Problem using the Exhaustive Search
Method.
2. Design the Insertion Sort algorithm. Analyze its time efficiency. Sort the given
list using Insertion Sort: 89, 45, 68, 90, 29, 34, 17
3. Explain the Source Removal Method in Topological sorting and sort the
following graph by the same method.
4. Write an algorithm for Quick Sort and apply the algorithm to sort the given list
5,3,1,9,8,2,4,7.
5. Design an algorithm for Merge sort, apply the algorithm to sort the given list
8, 3, 2, 9, 7, 1, 5, 4 and derive its time complexity.
6. Discuss in detail about Binary tree traversal techniques with examples.
Traverse the following binary tree a. preorder. b. inorder. c. postorder.
7. Explain the Divide and Conquer Method. Apply the Divide-and-Conquer
method to multiply the following two integers. a=26 b=45.
8. Explain Strassen’s matrix multiplication and derive its time complexity.
Multiply the following two matrices with the help of Strassen’s Matrix
Multiplication.
1 2 2 2
3 4 3 1
9. Apply the DFS-based algorithm to solve the topological sorting problem for
the following digraph
10. Explain 3 major variations of Decrease and Conquer with examples.
Module-3
1. Define Heap. Explain the bottom-up heap construction algorithm.
2. Define AVL tree with an Example.
3. Sort the given list using Heap Sort 2, 9, 7, 6, 5, 8. Obtain its time complexity
4. Explain the properties of Heap along with its representation.
[Link] that the set of possible list values are {11,12,13}, sort the following
list in ascending order by the distribution-counting algorithm: 13, 11, 12,
13,12,12
6,Design Horspool’s algorithm for string matching. Apply Horspool’s algorithm to
find the pattern BARBER in the text: JIM_SAW_ME_IN_A_BARBERSHOP
[Link] the problem by using Sorting by Comparison Counting
A={62,31,84,96,19,47}
Module-4
1. Solve the instance 5, 1, 2, 10, 6, 2 for the coin-row problem by dynamic
programming algorithm
2. Apply the dynamic programming algorithm to find all the solutions to the
change-making problem for the denominations 1, 3, 4 and the amount n =6
3. Apply Dynamic Programming Technique to the following instance of
Knapsack Problem with capacity M=5
4. Write Dijkstra’s algorithm and apply the same to find single source shortest
Path problem for the following graph taking vertex ‘1’ as source.
5. Find the minimum spanning tree for the following graph by Kruskal’s method.
Explain neatly
6. a. Write the algorithm for Prim’s method to find minimum Spanning tree.
b. Define Minimum spanning tree. Construct minimum cost spanning tree
using Prims algorithm for the following graph.
7. Apply Warshall’s algorithm to find the transitive closure of the digraph
defined by the following adjacency matrix:
a b c d
a 0 1 0 0
b 0 0 1 0
c 0 0 0 1
d 0 0 0 0
8. Solve the all-pair shortest path problem for the given digraph:
9. a. Construct a Huffman code for the following data:
Symbol A B C D _
Frequency 0.4 0.1 0.2 0.15 0.15
b. Encode ABACABAD using the code of question
c. Decode 100010111001010 using the code of question
10. a. Construct a Huffman code for the following data:
b. Encode DAD-CBE using Huffman coding
c. Decode 10011011011101 using Huffman coding
Module-5
1. Explain the following with examples
i) P problem ii) NP Problem iii) NP- Complete problem iv) NP – Hard
Problems
2. What is backtracking? Apply backtracking to solve the below instance of sum
of subset problem S={5,10,12,13,15,18} d=30
3. Illustrate N queen’s problem using backtracking to solve 4-Queens problem.
Write state space tree.
4. Write pseudo-code for solving the 4-Queens problem using backtracking.
5. Solve the following instance of the knapsack problem by the branch-and
bound algorithm:
6. Solve the following instance of the knapsack problem by the branch-and
bound algorithm: Construct state space tree.
7. Explain Greedy approximation algorithm to solve discrete knapsack problem.
8. Differentiate between Branch and Bound technique and Backtracking. Apply
backtracking to solve the following instance of subset-sum problem S={ 3, 5,
6, 7 } and d=[Link] a state space tree.
9. What is NP-completeness and why is it important in algorithm analysis?