GITA AUTONOMOUS COLLEGE, BHUBANESWAR

QUESTION BANK
Subject: Design of Algorithm and Analysis
Subject Code: MCAT303 Department: MCA Semester:3rd

PART – I BL CL PO&
Short Answer Type Questions O PS PSO
1 Describe the characteristics of algorithm with an example. 1 2 1,2,3
2 Derive the time worst case complexity of merge sort. 1 3 1,2
3 Write the differences between divide and conquer and greedy method. 2 2 1,2,4
4 Define Backtracking? List the applications of Backtracking. 3 3 1,2,6
5 What is Travelling Sales Man Problem? Explain 3 2 1,3,4
6 Using step count find the time complexity of sum of ‘n’ natural numbers 2 5 1,3,5
7 Give the problem formulation of Knapsack problem using greedy method. 1 4 1,4,2
8 Prove that dynamic programming constructs solution in bottom up approach. 3 2 1,3,4
9 Write about the constraints and criterion function used in backtracking. 2 3 1,2
Using step count method, analyze the time complexity when 2 m x n matrix 2 4 1,2,7
10
added.
11 Sort the following set of elements using merge sort 12,24,8,71,4,23,6,89,56. 1 4 1,2,4
12 What is meant by all pairs shortest path problem? 3 3 1,2,3
13 Write the difference between greedy method and dynamic programming. 1 2 1,2,3
What are the factors that influence the efficiency of the backtracking 1 3
14 1,2
algorithm?
15 Define 8 queens problem. 2 2 1,2,4
16 Write about big oh notation. 3 3 1,2,6
17 What is pseudo-code? Explain with an example. 3 2 1,3,4
18 Give the general procedure of divide and conquer method. 2 5 1,3,5
19 Describe the two phases of performance evaluation. 1 4 1,4,2
20 Write the working principles of divide and conquer with finding factorial of ‘n’. 3 2 1,3,4
21 Write the pseudo code for finding the factorial of given number. 2 3 1,2
22 Write the recurrence relation for divide and conquer and explain. 2 4 1,2,7
23 Write about principle of optimality in shortest path problem. 1 4 1,2,4
24 Devise an algorithm that sorts a collection of n≥1 elements of arbitrary type. 3 3 1,2,3
State the best, average and worst case complexities of binary search for 1 2
25 1,2,3
successful and unsuccessful search.
26 Write the functional difference of divide and conquer greedy method. 1 3 1,2
Solve the recurrence relation using substitution method 2 2
27 T(n)= { T(1) n=1 1,2,4
aT(n/b)+f(n) n>1 ,where a=5,b=4,and f(n)=cn2 .
28 What are the four distinct areas of study of algorithm? 1 3 1,2,6
29 Is quick sort a stable sorting method? Justify. 1 2 1,3,4
Can we say that the time for Merge Sort is Ɵ(n log n).What is its worst and best 1 5
30 time of procedure for Merge Sort.
1,3,5
31 List out the criteria’s of an algorithm. 1 4 1,4,2
32 Mention the advantages and disadvantages of binary search. 1 2 1,3,4
33 List the features of dynamic programming. 1 3 1,2
34 Define Little Oh notation with example. 2 4 1,2,7
35 Describe the time complexity of Divide And Conquer in the recurrence form. 1 4 1,2,4
36 What is knapsack problem? State knapsack problem formally. 1 3 1,2,3
37 Distinguish Greedy method and Dynamic Programming. 1 2 1,2,3
38 Denote live node and dead node with example. 2 3 1,2
39 Explain the basic principle of Divide and Conquer method. 3 2 1,2,4
40 Define Minimum Cost Spanning tree and list its applications. 2 3 1,2,6
41 Explain recursive functions algorithm analysis with an example. 1 2 1,3,4
42 State the Subset Sum problem. 2 5 1,3,5
43 Differentiate between Backtracking and Branch & Bound techniques. 3 4 1,4,2
44 Define Omega notation. 1 2 1,3,4
45 Derive the worst case complexity of the Quick sort algorithm. 2 3 1,2
46 State the general principle of greedy method. 1 4 1,2,7
In how many passes does the Merge sort technique sorts the following 1 4 1,2,4
47 sequence 3,27,4,11,45,39,2,16,56?
48 What is the importance of knapsack algorithm in our daily life? 1 3 1,2,3
49 What are the Asymptotic notations and its properties? 1 3 1,4
In how many passes does the Quick sort technique sorts the following 2 2 2,3
50 sequence 3,27,4,11,45,39,2,16,56?
PART-II(Focused type Question )
Differentiate performance measurement and performance estimation of 2 2 13,5
1
algorithms.
Write the recursive and iterative algorithms for finding the reverse of a given 1 2 2,8
2
string and analyze time and space complexities.
3 T(n)=aT(n/b)+f(n). Simplify this recurrence relation in terms h(n) and u(n) 1 3 6,8,10
functions to find out the time complexities.
Write the algorithm for finding pivot element in quick sort algorithm and 2 5 5,8
4
analyze its time complexity.
How to insert more number of jobs in feasible solution set J={} to maximize 2 1 3,4,7
5
the profit using greedy method? Explain algorithm.
6 What is the role of ‘min’ cost edge in the graph to find minimum cost 2 3 2,7
spanning tree using Krushkal algorithm? Give the implementation.
Write the algorithm for general iterative backtracking method and explain 2 3 1,6,7
7
various factors that define the efficiency of backtracking.
Explain the role of instance characteristics in finding the time and space 1 2 13,5
8 complexities with an example.
9 For T(n)=7T(n/2)+18n2 Solve the recurrence relation and find the time 2 2 2,8
complexity.
Given 2 sorted lists of numbers. Write the algorithm to merge them and 2 3 6,8,10
10
analyze its time complexity.
Write an algorithm for linear search and analyze the algorithm for its time 1 5 5,8
11
complexity.
Explain in detail merge sort. Illustrate the algorithm with a numeric example. 2 1 3,4,7
12
Provide complete analysis of the same.
13 Write about single source shortest path problem. 2 3 2,7
What is Minimum cost spanning tree? Explain an algorithm for generating 2 3 1,6,7
14
minimum cost spanning tree and list some applications of it.
15 Write about 0/1 knapsack problem. 1 2 13,5
Explain the methodology of Dynamic programming. List the applications of 1 2 2,8
16
Dynamic programming.
f(n)=O(g(n)), f(n)=Ω(g(n)) and f(n)=Θ(g(n)), illustrate these relations in 2 3 6,8,10
17
estimating the time complexities with suitable examples.
Formulate the Knapsack problem with greedy method and find the optimal 1 5 5,8
18
solution for n=7, m=15, (p1-p7)=(10,5,15,7,6,18,3), (w1-w2)=(2,3,5,7,1,4,1).
19 Write the prim’s minimum cost spanning tree algorithm and show that the run 2 1 3,4,7
time is O((n+|E|)log n).
Estimate the time complexity using f(n) and g(n) functions in asymptotic 2 3 2,7
20
notations.
Perform binary search on list of elements to find the key element using divide and 2 2 13,5
21
conquer, and also estimate the time complexity.
Generate the actions of shortest paths for the given graph from vertex 1 to all 2 2 2,8
22 remaining vertices. 12=20, 21=2, 13=15, 25=10, 26=30, 36=10,
34=4, 54=15, 64=4, 65=10.
Find optimal solution to the knapsack problem instance n=6, m=15, 2 3 6,8,10
23 (p1…p6) = (10,5,15,7,6,18), (w1…w6) = (2,3,5,7,1,4)
Explain how backtracking is used for solving n- queens problem. Show the state 3 5 5,8
24
space tree.
25 Consider the travelling salesperson instance defined by the cost matrix. 2 1 3,4,7
Write recursive binary search algorithm with an example and analyze time
26
complexity. List the applications of binary search.
Apply greedy algorithm to generate single-source shortest path with an example
27
graph. Mention its time complexity.
Sort the list of the elements 10,5,7,6,1,4,8,3,2,9 using merge sort algorithm and
28
show its computing time is O(n log n).
Describe the Travelling sales person problem and discuss how to solve it using
29
dynamic programming.
Write a backtracking algorithm to solve sum of subsets problem with m=35,
30
w= {20, 18, 15, 12, 10, 7, 5} to the variable tuple size formulation.

PART – III(Long answer type Questions)

Let the dimensions of A,B,C,D respectively be 10X5, 5X15, 15X8, 8X20 2 1 1,2,6,7
1 generate matrix product chains that produces minimum number of matrix
multiplications using dynamic programming.
Relate Hamiltonian cycle with travelling sales person problem and also give 3 2 1,2,6,7
2 the backtracking solution vector that finds all Hamiltonian cycles for any
directed or undirected graph.
Draw the portion of state space tree generated by recursive backtracking 3 2 1,2,6,7
3
algorithm for sum of subsets problem with an example.
Apply divide and conquer to search an element ‘k’ in an array a[1:n] using 2 2 1,12
binary search and explain the algorithm.
4
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.
Apply dynamic programming to find the optimal order of multiplying 3 1 4 1,3,8
5
matrices A 5X25, B25X10, C10X15.
Write and explain the iterative back tracking algorithm. Draw the state space 2 4 1,3,7,8
6
tree for 4-queens problem and give the solution tuples.
Device backtracking algorithm to find all solutions to the n-queens problem and 2 3 1,2,6,7
7
represent the solution space in state space tree.
Apply quick sort algorithm to sort the list. E, X, A, M, P, L, E in alphabetical 3 5 1,2,6,7
8
order.
Analyze the best, average and worst case complexity of quick sort.
Describe about reliability design with an example. 2 1 1,2,6,7
9 Obtain the solution to knapsack problem by Dynamic Programming method n=6,
(p1, p2,…p6)=(w1,w2,…w6)=(100,50,20,10,7,3) and m=165.
Define spanning tree. Compute a minimum cost spanning tree for the graph of 3 2 1,2,6,7
figure using prim’s algorithm.

10

Describe All-pairs shortest path algorithm with example. Give the time 3 2 1,2,6,7
11
complexity of the algorithm.
Consider A1=5X4, A2=4X6, A3=6X2, A4=2X7.P1=5, P2=4, P3=6, P4=2, P5=7 and 2 2 1,12
12 Apply matrix chain multiplication to obtain optimal sequence.
13 Describe an algorithm to solve 8-queen problem and Show the state space tree. 1 4 1,3,8
What is the time complexity of following function fun ()? Explain 2 4 1,3,7,8
int fun(int n)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < n; j += i)
14 {
Sum = Sum +i*j;
}
}
return(Sum);
}
15 What is Minimum cost spanning tree? Explain an algorithm for generating 2 3 1,2,6,7
minimum cost spanning tree and list some applications of it.
16 Write the algorithm to compute 0/1 Knapsack problem using dynamic 3 5 1,2,6,7
programming and explain it.
Derive the Best, Worst and Average time complexities of Quick sorting 2 1 1,2,6,7
17 technique.
Describe the Matrix multiplication chains problem. Apply the recursive 3 2 1,2,6,7
18 solution of dynamic programming to determine optimal sequence of pair wise
matrix multiplications.
Explain the basic principle of Backtracking and list the applications of 3 2 1,2,6,7
backtracking.
19 Using backtracking technique solve the following instance for the subset problem
s=(1,3,4,5) and d=11.
How the reliability of a system is determined using dynamic 2 2 1,12
20 programming? Explain.
Explain the Knapsack problem with an example?