Sipna College of Engineering and Technology, Amravati
Department of Computer Science & Engineering
Session 2022-23
Year/Sem/Section: 3rd / 6th /A,B,C
Subject: Design and analysis of algorithms
Question Bank (Unit 1,2,3,4,5,6)
Unit-I
Q1) List and explain in detail different general means for improving the efficiency of
algorithms.
Q2) List and explain different algorithm design strategies.
Q3) Explain Big-Oh, Omega & Theta notations.
Q4) Explain Used of loop in detail.
Q5) Find the Big-O notation for the following
i) Log n+ � ii) n+nlog n iii) 6n+2�4 + 2�5
Q6) Explain with example conversion of iterative function to recursive function.
Q7) Explain with example conversion of recursive function to iterative function.
Unit-II
Q1) Explain Strassen's Matrix Multiplication method with example.
Q2) What do you mean by triangulation? Explain different applications of
triangulation and different types of test performed on triangulation.
Q3) What is divide and conquer ? Explain with suitable example.
Q4) What is convex hull ? list and explain various algorithms of convex hull.
Q5) Write an algorithm for merge sort. Explain how divide and conquer strategy is
applicable to it. Also analyse the algorithm.
Q6) Explain the concept of Closet pair with example.
Q7) Explain binary search algorithm using recursive function.
Unit-III
Q1) Explain what greedy algorithms are and write its abstract algorithm.
Q2) Explain knapsack algorithm to find an optimal solution to the following instance
of knapsack problem if n=3 M=20 (P1,P2,P3)=(25,24,15) and (W1,W2,W3)=(18,15,10).
Q3) Apply knapsack algorithm to find an optimal solution to the following instance if
n=5, M=100 , (P1, P2,P3,….P5) = (20,30,66,40,60) and (W1,W2,W3….W5) =
(10,20,30,40,50)
Q4) Find solution to the scheduling problem when n=4, Pi=(50,10,15,30) and
Di=(2,1,2,1)
Q5) Find solution to the scheduling problem when n=6, Pi=(20,15,10,7,5,3) and
Di=(3,1,1,3,1,3)
Q6) Write and simulate Prim’s and Kriskal’s algorithm for the following graphs
Q7) Write and simulate Prim’s and Kriskal’s algorithm for the following graphs
Q8) Write and simulate Prim’s and Kriskal’s algorithm for the following graphs
Q9) Write and apply Dijkstra algorithm to find the shortest path from single source to
other nodes of a graph.
Q10) Write and apply Dijkstra algorithm to find the shortest path from single source
to other nodes of a graph.
Q11) Write and apply Dijkstra algorithm to find the shortest path from single source
to other nodes of a graph.
UNIT-IV
Q1) Distinguish between greedy methods and dynamic programming. Give its
advantages and disadvantages.
Q2) Find the shortest path for following multistage graph using dynamic
programming:
Q3) Find the shortest path for following multistage graph using dynamic
programming:
Q4)Find the shortest path for following multistage graph using dynamic programming:
Q5) Use dynamic programming strategy to calculate product of four matrices ABCD ,
where A is 13*5,B is 5*89,C is 89*3 D is 3*34.
Q6) Explain the chained matrix multiplication algorithm for dynamic programming.
State how the algorithm works to calculate the product of four matrices M1 is 10 * 20,
M2 is 20*50, M3 is 50 *1 and M4 is 1*100.
Q7) Find the Longest common Sub-sequence for following string:
a) Xi = A, B, C, B, D, A, B and Yj = B, D, C, A, B, A
b) Xi = A,B,C,B,A and Yj= B,D,C,A,B
Q8) Solve using traveling salesman problem for the distance matrix
Q9) Solve using traveling salesman problem for the distance matrix
Q10) Explain Floyd-Warshall algorithm to find the shortest path with an example
Q11) Explain Floyd-Warshall algorithm to find the shortest path with an example.
Q12) Explain Floyd-Warshall algorithm to find the shortest path with an example.
Q.13) Explain Floyd-Warshall algorithm to find the shortest path with an example.
Q.14) Explain Floyd-Warshall algorithm to find the shortest path with an example.
Unit-V
Q1) Explain BFS algorithm with example.
Q2) Explain DFS algorithm with example.
Q3) Write, explain and apply Depth first search (DFS )for the given un-directed graph
starting at node 1
Q4) Explain Backtracking strategy for 8 Queens Problem.
Q5) Explain Backtracking strategy for 4 Queens Problem.
Q6) Explain Backtracking strategy for 5 Queens Problem.
Q7) Explain M Colouring problem with an example.
Q8) Consider a graph G = <V,E> shown in following graph. Determine hamilton
Circuit using backtracking strategy
Q9) Write, explain and apply Depth first search (DFS )for the given un-directed graph
starting at node 1
UNIT VI
Q1) Explain complexity of set operations and mapping
Q2) Explain time analysis of algorithm using any search algorithm.
Q3) Explain time complexity calculation for any sorting algorithm.
Q4) Explain Non Polynomial time (NP) algorithms.
Q5) Explain efficiency of recursion with example.
Q6) Explain complexity using step counting principle.
