I.T.

Department - Semester – 5
Subject: Analysis and Design of Algorithms (2150703)

UNIT- 1
Basics of Algorithms and Mathematics
1. Explain following terms with example:
a. Set
b. Relation
c. Equivalence Relation
d. Function
e. Quantifiers
f. Linear inequality
g. Linear equations.
2. What is an algorithm? Explain characteristics of any algorithm. OR Define Algorithm.

UNIT- 2
Analysis of Algorithm
3. Explain why analysis of algorithms is important? Explain: Worst Case, Best Case & Average
Case Complexity. Arrange the following growth rate in increasing order: n3, 1, n2, nlog(n),
n2log(n), log(n), n0.5
4. Why do we use asymptotic notations in the study of algorithms? Briefly describe commonly
used asymptotic notations. OR Define: Big Oh, Big Omega and Big Theta Notation.
5. Explain Bubble sort algorithm. Derive the algorithmic complexity in Best case, worst case
and Average case analysis. Sort the letters of word “DESIGN” in alphabetical order using
bubble sort.
6. Write an algorithm for insertion sort. Analyze insertion sort algorithm for best case and worst
case. Sort the letters of word “EXAMPLE” in alphabetical order using insertion sort. OR
Sort the letters of word “EDUCATION” in alphabetical order using insertion sort.
7. Explain Selection Sort Algorithm and give its best case, worst case and average case
complexity.
8. Define Heap. Explain the heap sort in detail. Give its complexity. Give the properties of
Heap Tree. Sort the following data with Heap Sort Method:
• 20, 50, 30, 75, 90, 60, 25, 10, 40
• 65, 75, 5, 55, 25, 30, 90, 45, 80
UNIT- 3
Divide and Conquer
9. Design and analyze quick sort algorithm using divide and conquer technique. OR Explain
Quick Sort Method with example. OR Explain Quick sort using divide and conquer method
and compute its worst case running time. OR Write a program/algorithm of Quick Sort
Method and analyze it with example. OR Analyze quick sort algorithm for best case, average
 case and worst case with example. In which case it performs similar to selection sort? OR
Write the quick sort algorithm. Trace the same on data set -4, 3, 1, 9, 8, 2, 4, 7. Sort the
following list using quick sort algorithm: <50, 40, 20, 60, 80, 100, 45, 70, 105, 30, 90, 75>
Also discuss worst and best case of quick sort algorithm. OR Write an algorithm for quick
sort and derive best case, worst case using divide and conquer technique also trace given data
(3,1,4,5,9,2,6,5)
10. Explain how multiplication of large integers can be done efficiently by using divide and
conquer technique? OR Show how divide and conquer technique is used to compute
product of two n digit numbers with example.
11. What is Divide and Conquer Technique? Give the use of it for Binary Searching Method.
OR Explain Binary search using divide and conquer method and compute its worst case
running time. OR Give its complexity. Explain the use of Divide and Conquer Technique for
Binary Search Method. What is the complexity of Binary Search Method? Explain it with
example.
12. Explain Strasson’s algorithm for matrix multiplication. OR Discuss matrix multiplication
problem using divide and conquer technique.

UNIT- 4
Dynamic Programming
13. What is Principle of Optimality? Explain its use in Dynamic Programming Method. OR
Define: Optimal Solution, Feasible solution, Principle of Optimality.
14. Explain common characteristics of dynamic programming. Explain difference between
divide and conquer method and dynamic programming
15. Explain Chained Matrix Multiplication for any given example.
OR Using algorithm find an optimal parenthesization of a matrix chain product whose
sequence of dimension is ﴾13, 5, 89, 3, 34﴿ (use dynamic programming).
OR Given the four matrix find out optimal sequence for multiplication
D=<15,5,10,20,25>
OR Given the four matrix find out optimal sequence for multiplication D=<5,4,6,2,7>
OR Generate equation for Matrix chain multiplication using Dynamic programming. Find
out minimum number of multiplications required for multiplying: A[1 × 5], B[5 × 4], C[4 ×
3], D[3 × 2], and E[2 × 1]. Also give the optimal parenthesization of matrices.
OR Design and analyze dynamic programming algorithm with and without memorization to
solve matrix chain multiplication problem
OR Using algorithm find an optimal parenthesization of a matrix chain product whose
sequence of dimension is ﴾5,10,3,12,5,50,6﴿ (use dynamic programming).
OR Consider the chain of matrices A1,A2,..,A6 with the dimensions given below. Give the
optimal parenthesization to get the product A2..A5
16. Discuss and derive an equation for solving the 0/1 Knapsack problem using dynamic
programming method. Design and analyze the algorithm for the same. OR Solve the
following 0/1 Knapsack Problem using Dynamic Programming Method. Write the equation
for solving the problem. Consider n = 5, W = 11
Object 1 2 3 4 5
W 1 2 5 6 7
V 1 6 18 22 28
OR Solve the following Knapsack Problem using Dynamic Method. Write the equation for
solving above problem. Consider n = 5, W = 100
Object 1 2 3 4 5
W 10 20 30 40 50
V 20 30 66 40 60

OR Solve following knapsack problem using dynamic programming algorithm with

given capacity W=5, Weight and Value are as follows : (2,12),(1,10),(3,20),(2,15).
17. Describe an assembly line scheduling problem and give dynamic programming algorithm to
solve it (with example).
18. Find Longest Common Subsequence using Dynamic Programming Technique with
illustration X={A,B,C,B,D,A,B} Y={B,D,C,A,B,A} OR Explain how to find out Longest
Common Subsequence of two strings using Dynamic Programming method. Find any one
Longest Common Subsequence of given two strings using Dynamic Programming.
X=abbacdcba, Y=bcdbbcaac
OR Given two sequences of characters, P=<XYZYTXY> Q=<YTZXYX> Obtain the
longest common subsequence.
OR Using algorithm determine an Longest Common Sequence of ﴾A,B,C,D,B,A,C,D,F﴿ and
﴾C,B,A,F﴿(use dynamic programming).
OR Describe LCS problem with example and obtain optimal substructure required to solve it
using dynamic programming. OR Given two sequences of characters, P=<MLNOM>
Q=<MNOM>. Obtain the longest common subsequence.
OR Given two sequences of characters, P=<ABCDABE>, Q=<CABE > Obtain the longest
common subsequence.
OR Discuss and derive the optimal substructure that can be used to solve the Longest
Common Subsequence problem using dynamic programming. Find the longest common
subsequence for the given two sequences of characters: P = (1,0,0,1,0,1,1,0,1,1,0,1); Q= (
0,1,1,0).
19. Give optimal substructure for make change problem. Consider an instance of such a problem
with coins 1, 4 and 6 units. Illustrate its solutions using dynamic programming approach
involving a payment of 8 units or less. OR Solve making change problem using DP.
(Denominations: d1=1, d2=4, d3=6). Give your answer for making change of Rs. 9. OR
Given coins of denominations 2, 4 and 5 with amount to be pay is 7. Find optimal number of
coins and sequence of coins used to pay given amount using dynamic method. OR Given
coins of denominations 1, 3 and 4 with amount to be pay is 7. Find optimal number of coins
and sequence of coins used to pay given amount using dynamic method.
20. Write the equation for finding out shortest path using Floyd’s algorithm. Use Floyd’s method
to find shortest path for below mentions all pairs

UNIT- 5
Greedy Algorithm
21. Write down the general characteristics of greedy algorithm. OR Explain Greedy method in
detail with example and differentiate it with dynamic method.
22. Write Huffman code algorithm and Generate Huffman code for following
Letters A B C D E
Frequency 24 12 10 8 8
23. Generate minimum spanning tree of fig, A using Prim’s algorithm and using Kruskal’s
algorithm.

OR Consider the following undirected weighted graph. Find minimum spanning tree for the
same using Kruskal’s algorithm.
 OR Write and analyze Prim’s algorithm to generate minimum spanning tree. Apply the same
and find MST for the graph given below.

OR Find Minimum Spanning Tree for the given graph using Prim’s Algorithm (initialization
from node A)

OR Generate minimum spanning tree from the following graph using Prim’s algorithm.
(Start at vertex a)

OR Define Minimal Spanning Tree (MST). Mention applications of minimum spanning tree.
OR Explain Kruskal’s Algorithm to find MST with example.
24. Explain Dijkstra’s shortest path algorithm with example. If we want to display intermediate
node than what change we should make in the algorithm. OR Design and explain Dijkstra’s
shortest path algorithm OR Explain Dijkstra’s algorithm to find minimum distance of all
nodes from a given node. (Greedy algorithm)
25. Following are the details of various jobs to be scheduled on multiple processors such that no
two processes execute at the same on the same processor.
 Show schedule of these jobs on minimum number of processors using greedy approach.
Derive an algorithm for the same. What is the time complexity of this algorithm?
26. Using greedy algorithm find an optimal schedule for following jobs with n=7 profits:
(P1,P2,P3,P4,P5,P6,P7) = (3,5,18,20,6,1,38) and deadline (d1,d2,d3,d4,d5,d6,d7) =
(1,3,3,4,1,2,1) OR Using greedy algorithm find an optimal schedule for following jobs with
n=6. Profits: (P1,P2,P3,P4,P5,P6) = (20, 15, 10, 7, 5, 3), Deadline: (d1,d2,d3,d4,d5,d6) =(3,
1, 1, 3, 1, 3)
27. Using greedy algorithm find an optimal solution for knapsack instance n=7, M = 15
(P1,P2,P3,P4,P5,P6,P7)=(10,5,15,7,6,18,3) and (w1,w2,w3,w4,w5,w6,w7) = (2,3,5,7,1,4,1)

UNIT- 6
Exploring Graphs
28. Explain with example how games can be formulated using graphs? Define: Acyclic Directed
Graph, Dense Graph, Sparse Graph, Articulation Point, Graph, Tree, Preconditioning and
Optimal Substructure property (with example wherever necessary). Differentiate BFS and
DFS.
29. Explain Breadth First Traversal Method for Graph with algorithm.
30. Write pseudo code for the basic depth first search algorithm. OR Explain Depth First
Traversal Method for Graph with algorithm.
31. Write down the algorithm to determine articulation points in a given undirected graph. Give
any application where it is applicable. OR Write an algorithm to find out the articulation
points of an undirected graph. Find out articulation points for the following graph. Consider
vertex A as the starting point. OR How you can identify articulation points explain with
example. Describe the use of articulation point.

UNIT- 7
String Matching
32. What is Finite Automata? How it can be used in string matching. Explain with example.
33. What is the basic idea behind Rabin – Karp algorithm? What is expected running time of this
algorithm? Explain with example. OR Explain spurious hits in Rabin-Karp string matching
algorithm with example. Working modulo q=13, how many spurious hits does the Rabin-
Karp matcher encounter in the text T = 2359023141526739921 when looking for the pattern
P = 31415?
 UNIT- 8
Backtracking and Branch and Bound
34. Explain Backtracking with Knapsack problem. OR Find an optimal solution to the knapsack
instance n=4, M=8, (P1,P2,P3,P4)=(3,5,6,10) and (W1,W2,W3,W4)=(2,3,4,5) using
backtracking. Also draw the corresponding state space tree. OR Construct an implicit tree for
0-1 Knapsack problem. Give backtracking algorithm to solve it.
35. Explain Backtracking Method. What is N-Queens Problem? Give solution of 4-Queens
Problem using Backtracking Method. OR Explain how backtracking is used to solve four
queen problem. Find all possible solution for the 4*4 chessboard, 4 queen’s problem using
backtracking. OR Show state space tree. OR Discuss how 8-queen problem can be solved
using backtracking.
36. Explain Min Max Principle.
37. Explain use of Branch & Bound Technique for solving Assignment Problem.
UNIT- 9
Introduction to NP-Completeness
38. Define/Explain in Brief: P, NP Problem, NP, NP complete and NP-Hard problems,
Travelling Salesman Problem, Polynomial reduction. OR Explain different class of
problems. Give examples of each. OR Write a brief note on NP-completeness and the
classes-P, NP and NPC.