GITA Autonomous College, Bhubaneswar

(Affiliated to BPUT, Odisha)

At: Badaraghunathpur, P.O.: Madanpur, Bhubaneswar -
752054, Odisha

Subject Name: Design and Analysis of Algorithm Semester: 4th

Department: CSIT Sub Code: 21BTCSITTPC403

Name of Faculty: Dr Parimal Kumar Giri

Question Bank

Sl. Part-I
Module BL CO
No Short Answer Type Questions
1 Define growth of a function. 1 1 1
2 Is 2n+1 = O(2n)? 1 1 1
3 Differentiate posteriori and priori analysis. 1 1 1
4 Define little omega notation with example 1 1 1
5 Is 9n5+21n3+4n = ω (n5)? 1 2 1
6 1 1 1
Define time complexity and space complexity.
7 Find time complexity of addition of 2D array. 1 1 1
8 Is f(n) = 5n7 +2n3+8n = w(n6)? 1 1 1
9 If f(n) = 700 n7 + 8 , Represent it using all notation. 1 1 1
10 Briefly explain divide and conquer approach for problem solving. 1 2 1
11 Define recurrence with example. 1 2 1
12 What is time space trade-off? 1 1 1
13 State master’s method for solving recurrences. 1 2 1
14 Define big omega notation with example. 1 1 1
15 Define big oh notation with example. 1 1 1
16 List the advantages and disadvantages of divide and conquer 2 1 2
algorithm.
17 Write is the difference between quick sort and merge sort? 2 2 2
18 State the elements of dynamic programming. 2 1 2
19 Why dynamic programming is better than greedy? 2 2 2
20 Define matrix-chain multiplication problem. 2 1 2
21 Best case and Worst-case time complexity of LCS are _______ & 2 1 2
________.
22 Let A, B and C are three matrices of dimensions [5X7], [7 X 2] and 2 3 2
[2 X5]. Find the minimum cost of multiplying them.
23 In activity selection problem from a given set of activities always we 2 2 2
have to consider the first activity. [T/F]. Justify your answer.
24 What are the features/characteristics of an efficient algorithm? 5 2 2
25 State the elements of greedy algorithm. 3 1 2
26 State the formula for parenthesizing n matrices. 3 1 2
27 What do you mean by graph traversal and its types? 4 1 4
28 Define Minimum spanning tree problem. 4 1 4
29 Define the capacity constraint in the context of maximum workflow 3 1 3
problem.
30 List any two applications of shortest-path algorithms. 4 1 4
31 Explain the general method of branch and bound? What is FIFO and 4 2 4
LC branch and bound.
32 What are different graph representation techniques, explain? 4 1 4
33 What is the use of Relaxation () in shortest-path algorithms? 4 1 4
34 What do you mean by negative-weight cycle in a directed graph? 4 1 4
35 Define backtracking. 3 1 3
36 Define the transitive closure of a directed graph. 4 1 4
37 Define N-Queen problem. 3 1 3
38 State the time complexity of prim’s and krushkal’s algorithm. 3 2 3
39 State the algorithm for initialize_single_source(). 3 2 3
40 What do you mean by all-pair-shortest path? 4 1 5
41 Mention four differences between Dynamic and Greedy approach. 3 1,2 5
42 Define tree edge, forward edge, backward edge and cross edge. 4 1 4
43 Define spanning graph with an example. 4 1 4
44 State different types of shortest path problems 4 1 4
45 What is topological ordering of a graph? 4 1 4
46 What are tractable and intractable Problems? 5 1 5
47 Define Cook’s theorem. 5 1 5
48 State deterministic algorithm and non-deterministic algorithm. 5 1 5
49 Define decision problem and optimization problem. 5 1 5
50 What is node cover decision problem? 5 1 5
Sl. Part-II
Module BL CO
No Focused-Short answer type Questions
1 Let the frequency count of function f(n) = 7n5+2n+3n2+8, Represent 1 1 1
it using Big oh notation.
2 Let the frequency count of function f(n)= 5n2+7n+3, Represent it
using theta notation.
3 Solve the recurrence using master’s method. 1 3 1
T (n) =9T (n/3) + n2.5

4 Solve the recurrence: 1 2 1

T(n)= T (n-1) + 1 , if n>0 using iterative method.
5 Solve the recurrence using master’s method: - 1 2 1
T(n)= 2T(n/2) + n/log n
6 Define little oh notation. Is f(n) = 5n4 + 7n2 +6n+9 = o (n5)? 1 2 1
7 Define dynamic programming and the steps involved in dynamic 2 1,2 2
programming.
8 State and explain the average case time complexity of quick sort. 2 1,2 2
9 Write the algorithm for activity selection problem. 2 2 2
10 State the algorithm for quick sort. Explain it with the help of an 2 1,2 2
example.
11 Given item’s profits (in Rs.) and weights(in Kg) as follows: 2 3 2
[Pi , Wi] = {{60, 40} , {100, 50}, {120, 40},{150,140}} (1i4) and
a knapsack of capacity = 50Kg. Find the solution and maximum
profit of fractional knapsack.
12 State the algorithm for quick sort and explain it. 2 1,2 2
13 State and explain the algorithms that can be implemented in a max 2 1,2 2
priority queue.
14 Write the algorithm and time complexity for merge sort. 2 2,3 2

15. Prove that the worst-case time complexity of Quick sort is O(n2). 2 3 2

16 State the algorithm of merge sort. Analyze the best , worst and 2 1,1 2
average case time complexity of merge sort.

17 2 3,1 2
Given the s table:

Find the optimal parenthesis for above matrix and write the
algorithm.

18 Find all the possible solution for 4-Queen problems in a 4Χ4 3 3 4

chessboard using Backtracking method.
19 Find the transitive closure for the given graph:- 4 3 4

20 Explain Depth First Search algorithm and find the traversal list. 4 2,3 4

21 Write Breadth First Search (BFS) algorithm for graph traversals. 4 2,3 4
Perform BFS traversal for the following graph by considering start
node as 0.
22 Find the minimum spanning tree and its cost for the given graph by 4 3 4
using krushkal’s algorithm.

23 Find the shortest path from vertex A to all other vertices by using 4 3 4
Dijkstra’s algorithm.

24 2 3 2

Find the shortest way for Travelling Salesman by assuming that the
salesman starts his journey from city 1 by using dynamic
programming.
25 Use branch and bound technique to solve the following 0/1 3 3 3
knapsack problem . Find the maximum profit.
Consider :-n = 4, w = 10, (w1, w2, w3, w4) = (4, 7, 5, 3)
(v1, v2, v3, v4) = (40, 42, 25, 12)

26 Define circuit satisfiability. Prove that 3 CNF is np complete. 5 3 5

27 Find the optimal solution using 0/1 knapsack problem for 4 items 3 3 3
with weight= {2.3.4,5} , profit= {3,5,6,10}, maximum capacity= 8
by using Back Tracking.
Sl. Part-III
Module BL CO
No Long answer type Questions
1 Let the frequency count of an algorithm be 10n2+4n+2. Represent 1 2 1
using Big oh notation and find the values of c1, c2 and n0.
2 Solve the recurrence using recursion tree method 1 3 1
T (n) =2T(n/2) + n
3 State the algorithm for binary search. Also analyze its time 1 3 1
complexity.
4 State the algorithm and time complexity for Matrix-chain 2 1,2 2
multiplication problem.
5 Sort the given array elements in Quick sort for the given array of 2 3 2
elements
A[] = {12,52,41,42,15,14,52,47,48,49,65,35}
6 Given the 10 activities along with their start and finish time as 2 3 2
Si = <1, 2, 4, 3 ,5, 7, 8, 9,10, 12>
Fi=<3, 5, 5, 7, 7, 9, 14, 18, 11, 12>, Use an efficient method that
completes a schedule with maximum no. activities on that stage.
7 Given Profit: <10, 10, 12 ,18> , Weight: <2, 4 , 6 , 9 > , 3 3 3
maximum capacity m =15, and no. of items= 4. Find the maximum
profit of 0/1 knapsack within capacity using branch and bound.
8 Solve the following TSP which is represented as a directed graph 3 3 3
and whose edge length are given below by cost adjacency matrix.
0 10 15 20
5 0 9 12
6 13 0 12
8 8 9 0
9 Find the optimal parameterization of a matrix chain product for 2 3 2
minimizing the total number of scalar multiplication whose sequence
of order is <2, 6 , 5 , 4 , 3> , n =4
10 Find an optimal solution of the knapsack problem using dynamic 2 3 2
programming. The no of item n=8, Knapsack capacity m=17,
Profit= {10,15,8,7,3,15,8,27}
Weight= {5,4,3,7,2,3,2,6}
11 Suppose a file to be transformed through network contains the 2 3 2
following characters with the no. of occurrences given below
< a:45, b:13, c:12, d:16, e:9, f:5> , Determine the efficient strategy
that can minimize the total cost of transferring a file having 100
characters using Huff-man coding and tree.

12 Determine LCS of <1, 0, 0, 0, 1, 1, 0, 1> and < 0, 0, 1, 1, 1, 1, 0, 1> 2 3 2

13 Explain the Divide-and Conquer technique. Design a recursive 2 1,2 2
algorithm for binary search.
14 Compress the given string using Huffman Coding. 2 3 2
S= aassgshhhasjshhhsaaaassaasshh

15 Given four matrices with dimensions 4 x 10, 10 x 3, 3 x 12, 12 x 20. 2 3 2

Compute M [i,j] and S[i,j] tables.
16 Write Prim’s Minimum Spanning Tree (MST) algorithm. Find a 4 1,3 4
MST and its cost of the following graph using v5as a root vertex.

17. Consider the following flow network with source S and sink T, 4 3 4
where the edges are labeled with their capacities:

Find a maximum S-T flow for this network. What is the value of this
flow?

18. Define NP completeness. State chromatic number decision 5 2 5

Problem and clique decision problem.
19. Define class P, NP , NP-complete and NP- hard. Show the 5 2 5
relationship between them.
20 Consider the following directed weighted graph G = {V, E}. Find
the shortest paths between all the vertices of the graphs using the
Floyd-Warshall algorithm