GIET Main Campus (Autonomous)

Gunupur-765 022

Regd. No.:
B.TECH. DEGREE EXAMINATION-Nov-Dec.2018
Question Bank
BCSPC3010 Design and Analysis of Algorithm
PART A - (10 X 2 = 20 Marks) Multiple Choice Questions
UNIT-1

1. (a) Which notation is used for upper bound analysis? [CO1] [PO1]
(A) Big-Oh (O)
(B) Big-Omega (Ω)
(C) Theta ()
(D) Small-Oh (o)
(b) Which method is not used to solve recurrence relation? [CO1] [PO1]
(A) Master method
(B) Recursion-tree
(C) Substitution
(D) Dynamic Programming
(c) Which method is also called Guess method? [CO1] [PO1]
(A) Master method
(B) Recursion-tree
(C) Substitution
(D) Dynamic Programming
(d) For the function f (n) = 2n2 + 6n+5, which is not correct bound? [CO1] [PO2]
(A) O (n2)
(B) O (n3)
(C) O (n)
(D) O (n4)
(e) For the function f (n) = 3n2 +8n+9, which is not correct bound? [CO1] [PO2]
(A) Ω (n2)
(B) Ω (n3)
(C) Ω (n)
(D) Ω (1)
(f) What is the time complexity for finding the sum of square of first n odd natural numbers? [CO1] [PO3]
(A) O(n)
(B) O(n2)
(C) O(log n)
(D) O(n log n)
(g) What is the time complexity for finding the K-th digit in ‘a’ raised to power ‘b’ [CO1] [PO2]
(A) O(n)
(B) O(n2)
(C) O(log n)
(D) O(1)
(h) Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1, then __________ [CO1] [PO3]
(A) T(n) = O(n2)
(B) T(n) = Θ(n log n)
(C) T(n) = Ω(n2)
(D) T(n) = O(n log n)
(i) Let f(n) = 18n4 +20nlog n and g(n) = 9758n3 log n + 9565n2. Which of the following is true? [CO1] [PO2]
(A) f(n) is not O(g(n)) and g(n) is not O(f(n))
(B) f(n) is O(g(n)), but g(n) is not O(f(n))
(C) g(n) is O(f(n)), but f(n) is not O(g(n))
(D) f(n) is O(g(n)) and g(n) is O(f(n))
GIET Main Campus (Autonomous)
Gunupur-765 022

(j) Consider the following functions: f(n) = 2n, g(n)=n!, h(n)=nlogn Which of the following
statements about the asymptotic behavior of f(n), g(n), and h(n) is true? [CO1] [PO2]
(A) f(n) = O(g(n)); g(n) = O(h(n))
(B) f(n) = Ω(g(n)); g(n) = O(h(n))
(C) g(n) = O(f(n)); h(n) = O(f(n))
(D) h(n) = O(f(n)); g(n) = Ω(f(n))
(k) Which notation is used for average case analysis? [CO1] [PO1]
(A) Big-oh
(B) Big-omega
(C) Theta
(D) Small-oh
(l) Let W(n) and A(n) denote the worst case and average case running time of an algorithm
executed on an input of size n. which of the following is true? [CO1] [PO2]
(A) A(n) = Ω(W(n))
(B) A(n) = θ(W(n))
(C) A(n) = O(W(n))
(D) A(n) = o(W(n))

UNIT-2

(a) The total running time of merge sort algorithm is ______. [CO2] [PO1]
(A) O(n)
(B) O(n2)
(C) O(log n)
(D) O(n log n)
(b) What is recurrence for worst case of Quick Sort and what is the time complexity in Worst
case? [CO2] [PO1]
(A) Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n2)
(B) Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n2)
(C) Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nlogn)
(D) Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nlogn)
(c) Given two sequences X and Y: X = < a, b, c, b, d, a, b > and Y = < b, d, c, a, b, a >. The
[CO2] [PO2]
longest common subsequence of X and Y is :
(A) < b, c, a>
(B) < c, a, b>
(C) < b, c, a, a>
(D) < b, c, b, a>
(d) The total running time of heap sort algorithm is ______. [CO2] [PO1]
(A) O(n)
(B) O(n2)
(C) O( n log n)
(D) O(log n)
(e) A pivot element to partition unsorted list is used in [CO2] [PO1]
(A) Merge Sort
(B) Quick Sort
(C) Selection Sort
(D) Heap Sort
(f) What is the time complexity of Huffman algorithm for encoding? [CO2] [PO1]
(A) O(n)
(B) O(n2)
(C) O( n log n)
(D) O(log n)
GIET Main Campus (Autonomous)
Gunupur-765 022

(g) Which of the following is true about Huffman Coding? [CO2] [PO2]
(A) Huffman coding may become loss in some cases
(B) Huffman Codes may not be optimal lossless codes in some cases
(C) In Huffman coding, no code is prefix of any other code
(D) All of the above
(h) An almost complete binary tree T has 20 nodes. The number of nodes in T having two
children is: [CO2] [PO3]
(A) 7
(B) 9
(C) 12
(D) 8
(i) Running time of the quick sort depends on [CO2] [PO1]
(A) Type of inputs elements
(B) Arrangement of elements in an array
(C) Pivot element
(D) Size of array
Which of the following depict the correct complexity of the merge sort when the input array
(j) [CO2] [PO2]
is sorted?
(A) O(n)
(B) O(n3)
(C) O( n log n)
(D) O(n2)
(k) The dynamic programming approach can work in which of the following way? [CO1] [PO1]
(A) Bottom-up
(B) Top-down
(C) Both (A) & (B)
(D) None of these
(l) Coin changing problem can be solved by using which of the following technique? [CO2] [PO1]
(A) Backtracking
(B) Greedy
(C) Branch & Bound
(D) Dynamic Programming

UNIT-3

(a) Which of the following operation is not belongs to Disjoint set data structures? [CO3] [PO1]
(A) Make-Set(x)
(B) Union(x, y)
(C) Intersection(x, y)
(D) Find-Set(x)
(b) Which of the following algorithms can be used to most efficiently determine the presence of a
cycle in a given graph? [CO3] [PO1]
(A) Depth First Search
(B) Breadth First Search
(C) Prim’s Minimum Spanning Tree Algorithm
(D) Kruskal’s Minimum Spanning Tree Algorithm
(c) Dijkstra’s algorithm is based on [CO3] [PO1]
(A) Divide and conquer paradigm
(B) Dynamic programming
(C) Greedy Approach
(D) Backtracking paradigm
GIET Main Campus (Autonomous)
Gunupur-765 022

(d) Which of the following is the complexity of Kruskal’s MST algorithm? [CO3] [PO2]
(A) O(n)
(B) O(n3)
(C) O( n log n)
(D) None
(e) Which of the following is the complexity of Prim’s MST algorithm? [CO3] [PO2]
(A) O(E log V)
(B) O(V2)
(C) O(E2)
(D) O(V log E)
(f) What are the appropriate data structures for following algorithms?
1) Breadth First Search
2) Depth First Search
3) Prim's Minimum Spanning Tree
4) Kruskal's Minimum Spanning Tree [CO3] [PO2]
(A) 1) Stack 2) Queue 3) Union Find 4) Priority Queue
(B) 1) Queue 2) Stack 3) Priority Queue 4) Union Find
(C) 1) Stack 2) Queue 3) Union Find 4) Priority Queue
(D) 1) Queue 2) Stack 3) Priority Queue 4) Union Find
(g) Given an undirected graph with negative edge weights, which of the following algorithm is
used to find the Single source shortest path? [CO3] [PO1]
(A) Dijkstra’s algorithm
(B) Bellman-Ford algorithm
(C) Kruskal’s algorithm
(D) Prim’s algorithm
(h) If all edges have the same weight in an undirected graph, which algorithm will find the
shortest path between two nodes more efficiently? [CO3] [PO2]
(A) Dijkstra
(B) Bellman-Ford
(C) Depth-First Search
(D) Breadth-First Search
(i) Indicate the runtime of Dijkstra's algorithm when the implementation is based on a binary
heap. (E = edges; V = vertices) [CO3] [PO2]
(A) O(E log V)
(B) O(V2)
(C) O(E + V log V)
(D) O(E + V)
(j) A graph can be represented by which of the following? [CO3] [PO1]
(A) Matrices
(B) Linked list
(C) Both (A) & (B)
(D) None of the above
(k) Which of the following standard algorithms is not a Greedy algorithm? [CO3] [PO1]
(A) Prim's Minimum Spanning Tree
(B) Kruskal' Minimum Spanning Tree
(C) Bellman-Ford Single-source-shortest path algorithm
(D) Dijkstra’ Single-source-shortest path algorithm
(l) An All-pairs shortest-paths problem is efficiently solved by using: [CO3] [PO1]
(A) Dijkstra’ algorithm
(B) Floyd-Warshall algorithm
(C) Kruskal algorithm
(D) Bellman-Ford algorithm
GIET Main Campus (Autonomous)
Gunupur-765 022

UNIT-4

(a) Time complexity analysis of n queen problem [CO4] [PO2]

(A) O(n!)
(B) O(n2 log n)
(C) O(2n)
(D) O(n3)
(b) Time complexity analysis of sum of subset problem [CO4] [PO2]
(A) O(n!)
(B) O(n2 log n)
(C) O(2n)
(D) O(n3)
(c) What is the type of the algorithm used in solving the 8 Queens problem? [CO4] [PO1]
(A) Greedy
(B) Dynamic
(C) Branch and Bound
(D) Backtracking
(d) Time complexity of Knuth-Morris-Pratt algorithm [CO4] [PO1]
(A) O(n!)
(B) O(n)
(C) O(2n)
(D) O(n + k)
(e) What is the worst case time complexity of Rabin-Karp string matching algorithm [CO4] [PO2]
(A) O(n)
(B) O(m2)
(C) O(n + m)
(D) O(m(n-m))
(f) Which is more efficient string matching algorithm? [CO4] [PO1]
(A) KMP
(B) Rabin-Karp
(C) Naïve
(D) All of the above are equally efficient
(g) Which of the following string matching is used? [CO4] [PO1]
(A) DNA matching
(B) Text editor
(C) Finding musical patterns
(D) All of the above
(h) Which of the following is not used in string matching? [CO4] [PO1]
(A) LCS
(B) Naïve
(C) Master Theorem
(D) KMP
(i) In which of the following approximation algorithm is not needed? [CO4] [PO1]
(A) Searching
(B) TSP
(C) Vertex Cover
(D) CLIQUE
A problem that can’t be solved by polynomial time algorithm but is verifiable in polynomial
(j) [CO4] [PO2]
time is
(A) P
(B) NP
(C) NP-Complete
(D) NP-Hard
GIET Main Campus (Autonomous)
Gunupur-765 022

(k) A Problem that can be solved by a non deterministic algorithm in polynomial time is [CO4] [PO2]
(A) P
(B) NP
(C) NP-Complete
(D) NP-Hard
(l) A Problem that can be solved by a deterministic machine polynomial time is [CO4] [PO2]
(A) P
(B) NP
(C) NP-Complete
(D) NP-Hard

PART B - (10 X 2 = 20 Marks) Short Answer Question

UNIT-1

(a) What are the characteristics of an algorithm? [CO1] [PO1]

(b) Differentiate between Priori and Posteriori analysis of an algorithm. [CO1] [PO1]
(c) Define Worst case, Average case and Best case efficiency of an algorithm. [CO1] [PO1]
(d) Arrange the following functions from the lowest asymptotic order to the highest. 2n, 10n,
n log n, 4n3, log n, 5n2. [CO1] [PO2]
(e) What are the best case and worst case time complexity of Linear Search? [CO1] [PO2]
(f) Differentiate between Big-Oh and Big-Omega notation [CO1] [PO1]
(g) Prove that 2n+1 = O (2n) [CO1] [PO2]
(h) Is 22n = O (2n)? Justify. [CO1] [PO2]
n
(i) Prove that n! = ω(2 ) [CO1] [PO2]
(j) Prove that n! = o(nn) [CO1] [PO2]
(k) Define Time and Space complexity of an algorithm. [CO1] [PO1]
(l) What are the different notations are used to measure the time complexity of an algorithm? [CO1] [PO1]
(m) What are the parameters required to measure the performance of an algorithm? [CO1] [PO1]
(n) Solve the recurrence relation T(n) = 16T(n/4) + n2 [CO1] [PO3]
Solve the following recurrence relation using master theorem. If not justify your answer.
(o) T(n) = 0.5T(n/2) + n
[CO1] [PO3]

UNIT-2

(a) What are the best case and worst case time complexity of Binary Search? [CO2] [PO2]
(b) Write the recurrence relation for binary search. [CO2] [PO2]
(c) What is the recurrence relation of Merge Sort? [CO2] [PO2]
(d) What are the best case and worst case time complexity of Quick Sort? [CO2] [PO2]
(e) Running time of the quick sort depends on which factors? [CO2] [PO1]
(f) Among Quick Sort and Merge Sort which one is the best? Justify your answer. [CO2] [PO2]
(g) What is heap? How max heap is different from min heap? [CO2] [PO1]
(h) What are the maximum and minimum numbers of elements in a heap of height h? [CO2] [PO1]
(i) How greedy is different from dynamic programming? [CO2] [PO1]
(j) How fractional knapsack is different from 0/1 knapsack? [CO2] [PO1]
(k) How divide and conquer is different from dynamic programming? [CO2] [PO1]
(l) Define Greedy choice property. [CO2] [PO1]
(m) Explain characteristics of Greedy Algorithm [CO2] [PO1]
(n) What is Principle of Optimality? Explain its use in Dynamic Programming Method. [CO2] [PO1]
(o) What is the time complexity of Matrix Chain ordering? [CO2] [PO2]
GIET Main Campus (Autonomous)
Gunupur-765 022

UNIT-3

(a) What are the basic operations supports for disjoint data structure? [CO3] [PO1]
(b) What are the applications of BFS & DFS? Mention any two applications for each. [CO3] [PO1]
(c) What is a Mother Vertex? [CO3] [PO1]
(d) How BFS is different from DFS? [CO3] [PO1]
(e) Define minimum spanning tree. [CO3] [PO1]
(f) What is negative weigh cycle? [CO3] [PO1]
(g) What do you mean by initialization of single source shortest path? [CO3] [PO1]
(h) How a Bellman Fords algorithm is different from Dijkstra algorithms? [CO3] [PO1]
(i) What is time complexity of Kruskal and Prims algorithms for MST? [CO3] [PO2]
(j) How many edges are there in a complete graph of n vertices? [CO3] [PO1]
(k) How many spanning trees can be constructed from complete graph of n vertices? [CO3] [PO1]
(l) Define Minimum Spanning Tree. Write any two applications of MST. [CO3] [PO1]
(m) What is the running time of the Floyd-Warshall all-pair-shortest-path algorithm? [CO3] [PO2]
(n) Define transitive closure of a directed graph. [CO3] [PO1]
(o) Given a weighted graph where weights of all edges are unique (no two edge have same
weights), Is there is always a unique shortest path from a source to destination in such a
graph? Justify your answer. [CO3] [PO2]

UNIT-4

What are the differences between 'Backtracking' and 'Branch & Bound' algorithm
(a) [CO4] [PO1]
techniques?
(b) Which technique is used to solve N Queen problem? How many unique solutions can be
[CO4] [PO1]
obtained from a 4 Queen problem?
(c) Define State space tree. [CO4] [PO1]
(d) Differentiate between Live node and Dead node. [CO4] [PO1]
(e) Define subset sum problem. [CO4] [PO1]
(f) Differentiate between Implicit and Explicit constraints. [CO4] [PO1]
(g) Write the applications of Branch and Bound problem [CO4] [PO1]
(h) List the name of at least 4 NP-Complete problems. [CO4] [PO1]
(i) Why is the traveling salesman problem NP complete? [CO4] [PO2]
(j) What would be the complexity of ‘Naïve string matching’ algorithm, if the text T is of length
[CO4] [PO2]
‘n’ and the pattern P is of length ‘m’?
(k) What is the complexity of Knuth–Morris–Pratt string matching algorithm? [CO2] [PO2]
(l) What are the applications of String matching algorithms? [CO4] [PO1]
(m) Draw the Venn diagram to represent the relationship between the class P, NP, NP-Complete
[CO4] [PO1]
and NP-Hard problems.
(n) What is Hamiltonian cycle? [CO4] [PO1]
(o) What is approximation algorithms and why it needs? [CO4] [PO1]
GIET Main Campus (Autonomous)
Gunupur-765 022

PART – C: (Long Answer Questions)

UNIT-1

1 (a) (i) Show that for any real constants a and b, where b>0
(n + a)b = (nb) [5] [CO1] [PO1]
(ii) Solve the following recurrence relation
T (n) = 4T (n/2) + n2, where n>1 and is a power of 2. [5] [CO1] [PO2]
(iii) Show that f1(n) + f2(n) = O(max(g1(n), g2(n)) where f1(n) = O(g1(n)) and f2(n) =
O(g2(n)). [5] [CO1] [PO1]
OR
(b) (i) Solve the recurrences and find the complexity of the following term:
T(n) = 3T(n1/3) + log3n. [5] [CO1] [PO2]
(ii) Solve the recurrences using Master Theorem T(n) = 3T(n/4) + n log n. [5] [CO1] [PO2]
(iii) Solve the recurrences using Recurrence Tree Method T(n) = T(n/4) + T(n/2) + cn2 [5] [CO1] [PO2]

2 (a) (i) What is asymptotic notation? Why asymptotic notation is used? Explain different
asymptotic notations briefly. [8] [CO1] [PO1]
(ii) Write down limit theorems to define the different asymptotic notations for given
two function f(n) & g(n). [7] [CO1] [PO1]
OR
(b) (i) Define recurrence relation. How many different methods are used to solve
recurrence relation? Explain briefly. [8] [CO1] [PO1]
(ii) Prove that o(g(n)) ∩ ω(g(n)) is the empty set. Justify with suitable example. [7] [CO1] [PO2]

3 (a) (i) Solve the following recurrence relation using iteration method. T(n) = 8T(n/2)
+ n2. Here T(1) = 1. [7] [CO1] [PO2]
(ii) Why amortized analysis is required? Explain any two method of amortized
analysis with suitable example. [8] [CO1] [PO1]
OR
(b) (i) Solve the following recurrence relation using substitution method. T(n) = 2T(n/2)
+ n. Here T(1) = 1. [7] [CO1] [PO2]
(ii) Explain why analysis of algorithm is important? Explain: Worst Case, Best Case
& Average Case Complexity with suitable algorithm. [8] [CO1] [PO1]
GIET Main Campus (Autonomous)
Gunupur-765 022

UNIT-2

1 (a) (i) Write the Quick sort algorithm and analyze the best case and worst case time
complexity. [7] [CO2] [PO2]
(ii) Sort the following list using Merge Sort Algorithm : (25, 15, 23, 16, 5, 1, 34, 11,
22, 12) [8] [CO2] [PO2]
OR
Sort the given elements with Heap Sort Method: (20, 50, 30, 75, 90, 60, 25, 10,
(b) (i) [7] [CO2] [PO2]
40)
(ii) Show that the running time of Quick Sort is (n ) when the array A contains
2

distinct elements and is sorted in increasing order. [8] [CO2] [PO2]

2 (a) (i) Write an algorithm for QUICK SORT and PARTITION procedure. Derive the
best case and worst case time complexity using divide and conquer technique also
trace given data (3, 1, 8, 4, 5, 9, 2, 6, 5) [7] [CO2] [PO1]
(ii) Write Huffman code algorithm and Generate Huffman code for the string “DAA”

Letters A B C D E
Frequency 24 12 10 8 8 [8] [CO2] [PO2]
OR
(b) (i) Explain in brief characteristics of greedy algorithms. Compare Greedy Method
with Dynamic Programming Method. [7] [CO2] [PO1]
(ii) What is the running time of Quick Sort when all elements of an array A have the
same value [8] [CO2] [PO2]

3 (a) (i) Write recursive function for Chained matrix multiplication using Dynamic
programming. Find out optimal sequence for multiplication: A1 [5 × 4],
A2 [4 × 6], A3 [6 × 2], and A4 [2 × 7]. Also give the optimal parenthesis of
matrices [10] [CO2] [PO3]
(ii) Consider the following instance of the Fractional Kanpsack problem, n=3
capacity of Knapsack W=50, w=(10,20,40) and v=(60,80,100) find the optimal
profit using greedy approach. [5] [CO2] [PO3]
OR
(b) (i) Explain how to find out Longest Common Subsequence of two strings using
dynamic programming method. Find the Longest Common Subsequence of given
two strings S1 = “ABCBDAB” and S2 = “BDCABA”. [10] [CO2] [PO3]
(ii) Given 10 activities along with their Start (Si) and Finish (Fi) time as follows:

Ai A1 A2 A3 A4 A5 A6 A6 A8 A9 A10

Si 1 2 3 4 7 7 9 9 11 12

Fi 3 5 4 7 10 9 11 13 12 14

Compute a schedule where the maximum number of activities takes place.

[5] [CO2] [PO3]
GIET Main Campus (Autonomous)
Gunupur-765 022

UNIT-3

1 (a) (i) Write the BFS algorithm and explain it with a suitable example of directed graph. [5] [CO3] [PO1]
(ii) Compute the Minimum-cost Spanning Tree for the Graph given below using
Kruskal’s Algorithm.
a 3 b

10 2 4 7

12 6
c d e

15 4 5 2
f g
3
[10] [CO3] [PO3]
OR
(b) (i) Write the DFS algorithm and explain it with a suitable example of directed graph. [5] [CO3] [PO1]
(ii) Compute the Minimum-cost Spanning Tree for the Graph given below using
Prim’s Algorithm.
6
11 B G
A 10 21
15 8
11
13 12 D F
17
2 14 7
C
E D
5
[10] [CO3] [PO3]

2 (a) (i) Use Dijkstra’s single-source-shortest-path algorithm to find the shortest distance
from the source a, of the following graph.

[7] [CO3] [PO3]

(ii) Write and explain the Floyd-Warshall algorithm for finding all pair shortest path
for a weighted directed graph. [8] [CO3] [PO1]

OR
GIET Main Campus (Autonomous)
Gunupur-765 022

(b) (i) Compute the shortest distance from s to t for the Graph given below by using
Bellman–Ford Algorithm.

[7] [CO4] [PO3]

(ii) Define disjoint sets. Briefly explain about the different disjoint set operations. [8] [CO4] [PO1]

UNIT-4

1 (a) (i) Given a set S = {5, 10, 12, 13, 15, 18} and Sum=30, find the subset sum using
backtracking approach. [7] [CO4] [PO3]
(ii) For KMP-Matcher compute the prefix function π for the pattern P=
“ababbabbabbababbabb” when the alphabet is Ʃ = {a,b} [8] [CO4] [PO3]
OR
(b) (i) Solve the 4-Queen problem with one of the solution using backtracking approach. [7] [CO4] [PO3]
(ii) Working modulo q = 11. How many spurious hits does the Rabin-Karp matcher
encounter in the text T = 3141592653589793 when looking for the pattern P =26? [8] [CO4] [PO3]

2 (a) (i) Define P, NP, NP complete and NP-Hard problems. Give examples of each. [7] [CO4] [PO1]
(ii) Write an approximation algorithm for solving the TSP Problem. [8] [CO4] [PO2]
OR
(b) (i) Justify that Naïve string matching algorithm uses Brute force approach. [7] [CO4] [PO2]
(ii) Explain use of branch and bound technique for solving assignment problem. [8] [CO4] [PO1]