B.
TECH/CSE/4TH SEM/CSEN 2201/2021
B.TECH/CSE/4TH SEM/CSEN 2201/2021
DESIGN & ANALYSIS OF ALGORITHMS
(CSEN 2201)
Time Allotted : 3 hrs Full Marks : 70
Figures out of the right margin indicate full marks.
Candidates are required to answer Group A and
any 5 (five) from Group B to E, taking at least one from each group.
Candidates are required to give answer in their own words as far as practicable.
Group – A
(Multiple Choice Type Questions)
1. Choose the correct alternative for the following: 10 × 1 = 10
(i) An algorithm takes T(n) = log n! steps. What is the tightest bound for T(n) in big-
Oh notation?
(a) O(nlog log n) (b) O(nlog n)
(c) O(n(log n) n) (d) O(n log n)
(ii) Worst case time complexity for inserting an element in a sorted array so that it
stays sorted is
(a) O(1) (b) O(n) (c) O(n2) (d) None of these.
(iii) In the KMP algorithm for pattern matching, the suffix function δ(x) is the est
of the pattern p that is also a of x
(a) large, suffix, prefix (b) large, prefix, suffix
(c) small, prefix, suffix (d) small, suffix, prefix.
(iv) How would you classify the time complexity of an algorithm for the 0/1
Knapsack problem with n objects and capacity C which runs in O(nC) time?
Assume that the inputs to the problem are the sizes and profits of the n objects
and the capacity C.
(a) polynomial (b) exponential
(c) pseudo-polynomial (d) quadratic.
(v) Consider the Floyd Warshall algorithm for all pairs shortest path that is run on a
graph G whose edge weights are given as a 2-d matrix. The final answer is
written in matrix D. Then the algorithm can be used to detect negative weight
cycles in G by
(a) Checking if any main diagonal entry of D assumes a negative value
(b) Checking if any entry above the main diagonal of D becomes negative
(c) Checking if any entry below the main diagonal of D becomes negative
(my reasoning is if there is a –ve edge in the beginning a non-diagonal
element will be –ve, right? But only when –ve cycle exist it will beat a 0 value
CSEN 2201 2
in the diagonal and usurp its space, so you may D[5,5] = - 20 if the vertex 5 is
on a –ve cycle after a full run.
(d) Checking if the determinant of D becomes negative.
CSEN 2201 2
B.TECH/CSE/4TH SEM/CSEN 2201/2021
(vi) Consider a k-bit binary counter initialized to all zeros. If the cost of an increment
operation is measured by the number of bits flipped, what is the amortized cost
per operation for n increments starting from all zeros?
(a) O(n) (b) O(nk)
(c) O(nlog n) (d) None of these.
(vii) Suppose we implement Quicksort in two ways:
A. Using Median element of the array as pivot after applying the O(n) median-of-
medians algorithm.
B. Using the middle element at location (low + high)/2 as pivot. Here low and
high are the lowest and highest indices of the part of the array on which
Quicksort is invoked.
Which of the above results in O(nlog n) worst case complexity for Quicksort?
(a) A only (b) B only
(c) Both A and B (d) Neither A nor B.
(just choosing the pivot element the worst-case of quick sort cannot be avoided)
(viii) Consider the following code snippet:
int fun(int n)
{
int count = 0;
for(int i = 0; i < n; i++)
for(int j = i; j > 0; j--)
count = count + 1;
return count;
}
What is the time complexity of fun() in the worst case?
(a) θ (n) (b) θ (n^2) (c) θ (n logn) (d) θ (n loglogn)
(ix) What is the residual capacity of the augmenting path for the flow network
shown below? Note that for each ‘a/b’ written beside it implies flow = ‘a’ and
capacity = ‘b’.
(a) 0.5 (b) 1 (c) 1.5 (d) 2
(x) A problem in NP is NP-complete if
(a) it can be reduced to the 3-SAT problem in polynomial time
(b) the 3-SAT problem can be reduced to it in polynomial time
(c) it can be reduced to any other problem in NP in polynomial time
(d) some problem in NP can be reduced to it in polynomial time.
(d) would be the answer if ‘some’ can be replaced by ‘all’
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
Group – B
2. (a) Let T(n) = 1 if n < 3 and T(n)=3T(n/3) + √n otherwise. What is T(n) in big-Oh
notation? Find it using the Master theorem or otherwise.
Using Master Theorem,
a=3, b=3, nlogba-0.5=n0.5=f(n). As case 1 satisfies, T(n)=Θ(nlogba)= Θ(n)=O(n)
(b) For the input, 10, 90, 80, 200, 250, 300, 400, how many times you need to call
max-heapify function to ensure that it is a max heap? Please also identify each
call to max heapify.
(c) Prove that the average case time complexity of a binary search is O(n logn).
Suppose when you first compare the key with the middle element, it matches,
then the number of comparisons required to find the key is only 1. Number of
positions for which only one comparison is required is therefore 1.
Now if you do not find the key in the 1st comparison but you find it in the 2nd
comparison, then number of such positions = 2 (middle elements of the half-
arrays).
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
The number of positions for which 3 comparisons are reqd. is 4.
• Hence average number of comparisons
•≤ (1/n) [(1.1 + 2.2 + 4.3 + 8. 4 + …+ 2 (lgn – 1) lgn) + lgn] = (S + lg n) / n (say)
(highlighted term is for not finding the key, for which lg n comparisons are
required)
• Hence S = ∑ k = 1 to lg n k.2 (k -1). This is a Arithmetico-geometric (AP_GP) series.
S = 1.1 + 2.2 + 4.3 + 8. 4 + … + 2 (lgn – 1) lgn)
2S = 2.1 + 4.2 + 8.3 + 16.4 +………………..+ 2lgn lgn
S – 2S = 1 + [2(2–1) + 4(3-2) + 8(4-3) + 16(5-4) + ………] - 2lgn lgn
-S = 1 + [2 + 4 + 8 + 16 + …. + 2 (lgn – 1) ] - 2lgn lgn
-S = 1 + [2(2 (lgn – 1) -1) / (2 -1)] – n lgn
= 1 + 2(n/2 – 1) – n lg n
= 1 + n - 2 – n lg n
S = n lg n – n + 1
Hence average case is (1/n) (n lg n – n + 1 + lg n) = O(lg n)
4 + 3 + 5 = 12
3. (a) You are provided with an input of an unsorted sequence S of n integers, where
n>1. You would like to find both the second order statistic and the nth order
statistic of S. Show that they can be found out in (3 n/2 + lgn - 1) number of
pair-wise comparisons.
The 1st order statistic (means minimum element) can be found out in (n – 1) comparisons. Now if you
do this as a tournament arranged as a binary tree where as many teams as possible play in the 1st level
and then in the 2nd level etc. then such a tree will have a height of lgn . In other words the champion
(the smallest element) had to play lgn games in order be the champion. If we can track which
numbers were the direct losers to the champion, then the smallest of them is the 2nd order statistic. To
find the minimum of lgn numbers it will take lgn -1 more comparisons.
Now you also have to find out the nth order statistic (maximum element). But if you take n -1
comparisons more, then you exceed the given bound. So a small trick is required. Look at the
comparisons that were done at the 1st level in the earlier tournament. How many such comparisons
were there? n/2 (to take care of odd n, otherwise n/2 could suffice). Note that the smaller number
from each of those comparisons is useless for finding out the nth order statistic. So I can now find out
the maximum element from the rest of the n - n/2 elements, which will take exactly n - n/2 - 1
comparisons (N. B. we do not care in which order they are compared). Hence total number of
comparisons = (n -1) + lgn -1 + n - n/2 - 1 = (2n -2 - n/2) + lgn -1 <= (3 n/2 + lgn - 1) .
(Actually the bound is tight for n = odd, for n = even, it is loose by 2)
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
(b) Let X[1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in
sorted order. Give the outline of an O(lg n)-time algorithm to find the median of
all 2n elements in arrays X and Y.
Hint: This is not difficult. Just think how to keep reducing the search space. It is
important that the algorithm remains O(lg n) and does not become O(n).
Ans. Consider that the elements are all distinct, if duplicates are allowed, the
solution needs to be modified slightly.
Note that for 2n elements the median is the nth or (n+1)th element or both.
Now start by considering the 2 middle elements - x_m of X and y_m of Y. As all
elements are distinct, either x_m < y_m or vice versa.
Without loss of generality (WLOG), take x_m < y_m. Then the left half of X and
the right half of Y can be removed from our search space.
In the next step, find the middle element of right half of X say x_m’ and the
middle element of left half of Y y_m’. WLOG say x_m’ > y_m’. Then in the next
step consider the left half of the previous interval (i.e right half) considered for
X, which is basically the 3rd quarter of full X array and the right half of the
previous interval (i.e left half) considered for Y, which is basically the 2nd quarter
of the full Y array. Then again consider the middle elements of the above two
intervals and continue the process till in each array the search space reduces to
1 in log n time. One of them is a median. This is the outline of the method.
I am personally not 100% satisfied with this answer, as if I taught it in the class I
would have considered some more variations (shown below) where both the
medians lie in the same array and how to tackle that but I think for exam
purpose if some student can clearly mention how he/she is reducing the search
space, it is good enough, because that is the strategy.
X= 1 2 3 4 8 Y = 5 6 7 9 10
Look both the medians 5 and 6 are in Y and by the above method you will
definitely zero in on 5 or 6 but you may not be able to tell both. I am not
investing any more time myself. May be it is a good exercise for all of us to think
and write a program first that gives the correct result and then come and write
the pseudo-code accordingly.
7 + 5 = 12
Group – C
4. (a) Show that the Kruskal’s algorithm correctly provides us a minimal spanning
tree.
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
(b)(i) What is the prefix property in coding and how does it help?
Prefix property in coding guarantees that no codeword is also a prefix of some
other codeword.
This property ensures simple and unambiguous decoding.
(ii) A networking company uses a compression technique to encode the
message before transmitting over the network. Suppose the message
contains the following characters with their frequency:
Character Frequency
a 5
b 9
c 12
d 13
e 16
f 45
Each character in input message takes 1 byte. If the compression technique used
is Huffman Coding, how many bits will be saved in the message?
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
c) Given two sequence X[1..7] and Y[1..6], where X = ABCBDAB and Y = BDCABA.Find
any one longest subsequence common to both and briefly show the steps.
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
Please note that I have drawn the picture just as a suggestion of what is expected
from a student. Obviously, there are multiple LCSs.
4 + (2 + 3) + 3 = 12
5. (a) Matrices A, B and C, of dimensions 10 × 24, 24 × 6 and 6 × 17 respectively, are
provided. You are told to ensure that when computing the matrix product A.B.C
the number of scalar multiplications will be a minimum. How would you
parenthesize the product, and what would be the minimum number of scalar
multiplications you would need to perform?
(AB)C
The number of scalar multiplication would be=(10*24*6) +
(10*6*17)=1440+1020=2460
(b) Write the pseudo codes for Initialize-Single–Source(G,s) and Relax(u,v,w)
functions used in Dijkstra’s algorithm to find out the shortest paths from a
source vertex(s) to all other vertices of a given graph G(V, E) . Assume that w is
the non-negative weight of the edge(u, v). In the given graph G, there is a non-
negative weight for each edge (u, v) E.
Let s u → v be a shortest path in the given graph G(V,E) for some
vertices u, v V, where the notations used have the usual meanings, like there is
a path from s to u, followed by a directed edge from u to v. Then after
INITIALIZE SINGLE-SRC(G, s) and a sequence of relaxation steps that include the
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
call RELAX(u, v, w), if d[u] = δ(s,u) (shortest path weight from s to u), at any
time prior to the call, then d[v] = δ(s,v) at all times after the call. Prove this
statement. Note that, d[x] maintains an upper bound of the shortest path weight
from source s to vertex x.
(c) Let G=(V, E) be a connected, undirected graph with a real-valued weight function
w defined on E. Let A be a subset of E that is included in some MST for G, let (S,
V-S) be any cut of G the respects A, and let (u, v) be a light edge crossing (S, V-S).
Then edge (u, v) is safe for A. Prove it.
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
2 + (3 + 4) + 3 = 12
Group – D
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
6. (a) Amortized analysis is different from average-case analysis as no probability
is involved in the former one but it is involved in the latter.
(b) Suppose that the procedure ‘Compute-Prefix-Function(P)’ is available to you.
Write the pseudo-code for KMP matcher (T, P) for text T and pattern P using the
above procedure.
• KMP Matcher
1. n length[T]
2. m length[P]
3. π Compute Prefix Function(P)
4. q 0
5. For i 1 to n
6. do while q > 0 and p[q+1] ≠ T[i]
7. do q π[q]
8. if p[q+1] = T[i]
9. then q q+1
10. if q=m
11. then print “Pattern valid shift ” i-m
12. q π[q]
Total Time complexity = O(m+n)
(c) Show how to implement a queue with two ordinary stacks so that the amortized
cost of each enqueue and dequeue operations remains O(1) and does not
become O(n). Explain your amortized analysis.
Sir enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
Here time complexity will be O(1)
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, pop each element from stack1 and push into stack2.
3) Pop one element from stack2 and return it.
Here worst-case time complexity will be O(n.
In the above approach, each enqueue operation will take O(1) amortized cost.
For the first dequeue operation, in the worst case, this approach will make O(n) enqueue
operations first, but after that for each dequeue it will take constant time only. So total
time for n dequeue operations will be O(n+n-1)=O(2n-1)=O(2n).
Also, in the case where, say, we enqueue t(<n) elements, then dequeue those t elements, then
again enqueue and dequeue rest of the elements, for n dequeue, we need, O(t+(t-1)+(n-t)+(n-t-
1))= O(2n-2)=O(2n) time. So, for total n dequeue operations, we need O(1) amortised cost.
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
Alternative explanation:
Note the entire life time of a number in the data structure. It first gets pushed in stack 1,
Then popped out of stack 1, then pushed into stack 2 and then popped out of stack 2. So total
number of operations is 4 per data item. The first push gets the job done for enqueue and the
next 3 operations get the job done for dequeue. Hence for n elements it takes n = O(n) for
enqueue and 3n = O(n) for dequeue. The amortized cost of each remains O(1).
1 + 5 + (3 + 3) = 12
7. (a) Construct the prefix function for the pattern ‘aadbaaba’ that can be used by the
Knuth-Morris-Pratt algorithm.
•Prefix Function-
π{1,2,..m} {0,1,..,m-1}
such that
π[q] = max{k : k<q and pk pq }
•So π[q] is the length of the longest prefix of P that is proper suffix of Pq .
(b) Suppose we perform a sequence of n operations on a data structure in which the
ith operation cost is i, if i is an exact power of 2, and 1 otherwise. Use aggregate
analysis to determine the integer k such that the amortized cost A per operation
satisfies the following k ≤ A < k + 1.
So, amortized cost A of per operation is < 3, k = 2
6 + 6 = 12
Group – E
8. (a) Run Ford-Fulkerson algorithm on the above Flow network and find out the
maximum flow value. Show every step in detail
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
(b) Consider the execution of the algorithm for finding connected components in an
undirected graph using the UNION-FIND data structure. If the graph has n
vertices, e edges and k components, how many times in terms of n, e and k are
the MAKE_SET, FIND_SET and UNION operations invoked?
MAKE_SET = n, FIND_SET = 2*e and UNION = n – k as each union call causes the
number of components to decrease by 1, so from n separated vertices if we
have to reach k components we need n – k call.
(c) State which problems are solvable in polynomial time and which are NP-hard -
(i) Hamiltonian Cycle(NP-hard)
(ii) Subset Sum Problem(NP-hard)
(iii) Set Cover Problem (optimization version is NP-hard) even writing Np-hard
is ok for the students but this is good as a model answer
(iv) Edge Cover Problem(solvable in polynomial time)
6 + 4 + 2 = 12
9. (a) Draw the tree after the call of FIND_SET(8) using path compression heuristic.
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
No explanation required, just the drawing of the tree.
(b) Show that the approximation algorithm ‘APPROX-VERTEX-COVER’ taught in
class is a polynomial-time 2-approximation algorithm. State its time complexity.
Time complexity of the above algorithm is O(V+E)
(c) Reduce the CNF, (x v y v z’) ^ (x v y’ v w’) ^ (x’ v z v w’) ^ (z’ v y’ v w’) to an
instance of a clique decision problem, where x, y, z and w are Boolean variables.
What is the size of the clique that you will be looking for? Please write all the
steps and the terms used in your steps in detail.
CSEN 2201 1
B.TECH/CSE/4TH SEM/CSEN 2201/2021
As there are 4 clauses in the given formula, we will be looking for 4-clique in the
following diagram:
2 + (4 + 1) + (2 + 1 + 2) = 12
CSEN 2201 1
