Name:

Enrolment No:

RECOURSE EXAMINATION – AUGUST - 2021

COURSE: CSE 2719, DESIGN AND ANALYSIS OF ALGORITHMS

Programme: B.Tech (CS/CSE) Semester: IV (Even – 2020-21)

Duration: 2 hr. Max. Marks: 50

Instructions:
You can use a rough paper and pen during the exam. All questions are compulsory.
Section A: Objective Type
Only one option is correct. Choose the correct option, based on the problem statement.
Time: 1 hour 10 minutes.

Section B: Typed Answers

Type your answer within 350 words in the provided text box. No need to put any diagram etc.
Time: 50 minutes.

Section A [30 marks]

Question Question Mark CO &

No. BL
Q1 In Union-Find algorithm implementing disjoint subsets with linked-list and an
array to store the subset representatives – Which of the following statements is
correct?
CO1 &
a. Union operation will take O(n^2) time for n nodes. 1
b. Find is an O(1) time operation. L2
c. n unions and m finds will take O(m + m log n) time.
d. n unions and m finds will take O(n + n log m)

Q2 PQ1 is a priority queue implemented with an Unordered Array. PQ2 is another

priority queue implemented as a Min-Heap. Both are holding n number of
elements. Which of the following statements is correct?
CO2 &
a. Insertion takes O(n) in PQ2 and O(1) in PQ1. 1
b. Insertion takes O(n) in PQ1 and O(log n) in PQ2. L2
c. Deletion can be done in O(log n) time in PQ2 and O(n) time in PQ1.
d. Deletion can be done in O(1) time in both PQ1 and PQ2.

Q3 Choose the correct statement from the following:

a. We must count the basic operations performed by an algorithm when
analyzing its time complexity with asymptotic analysis.
b. In asymptotic analysis we generally consider the lowest degree of the
CO1 &
polynomial on input size and ignore the higher order terms. 1
c. Asymptotic analysis does always give hints of how complicated the actual L2
implementation of the algorithm would be.
d. It is always possible to find the asymptotic tight bound of time complexity
for every algorithm.
Q4 Given a weighted connected graph, Dijkstra’s algorithm finds (choose the
correct option)
a. All pairs shortest paths CO1 &
b. Multiple source single destination shortest paths 1
L2
c. Single source multiple destination shortest paths
d. Single source single destination shortest paths

Q5 Arrange the following functions according to their growth - from slowest

growing to fastest growing. [Note: log5n means log n base 5]
f1=O(n^2log2n) f2=O(nlog8n) f3=O(100n^5) f4=O(nlog4n)
CO2 &
a. f1 f2 f4 f3 1
L2
b. f2 f4 f1 f3
c. f2 f3 f1 f4
d. f3 f2 f1 f4

Q6 In a text file, the frequency (count) of some characters - a, b, c, d, e are given as

follows: - f(a)= 50, f(b)=35, f(c)=15, f(d)=6, f(e)=25. BitLength(x) denotes the
number of bits in the Binary encoding given by Huffman's algorithm to
character x. Which of the following is the most probable? CO2 &
a. BitLength(a) > BitLength(b) 1
L3
b. BitLength(a) > BitLength(d)
c. BitLength(e) < BitLength(d)
d. BitLength(b) > BitLength(e)

Q7 Suppose we implement Quicksort such that it always selects the last element of
the array as the pivot. What is the running time of this algorithm on an input
array that is already sorted?
CO1 &
a. O(n^2) 1
b. O(n) L2
c. O(n logn)
d. Not enough information given to answer the question

Q8 Which of the following is not a correct recurrence?

a. Binary Search (Best Case): T(n)=T(n/2) + c CO1 &

b. Quick Sort (Worst Case): T(n)=T(n−1) + cn^2 1
L2
c. Quick Sort (Best Case): T(n)=2T(n/2) + cn
d. Merge Sort (Every Case): T(n)=2T(n/2) + cn

Q9 Which of the following statements is correct?

a. Prim’s algorithm solves the single-source shortest path problem given
a weighted connected graph.
CO1 &
b. The MST produced by Kruskal’s algorithm is always unique. 1
c. Even if the graph has negative weight edges, Floyd-Warshall’s L2
algorithm will produce the all-pairs shortest path.
d. The MST produced by Prim’s algorithm is always unique.

Q10 Select the incorrect statement from the following:

a. Floyd-Warshall’s algorithm can be computed with a space requirement CO1 &
of ϴ(n^2), n is the number of vertices in the graph. 1
L2
b. Floyd’s algorithm can be used to find the all-pairs source shortest path
in a weighted connected graph.
 c. Floyd-Warshall’s algorithm runs in ϴ(n^3) time, n is the number of
vertices in the graph.
d. Dijkstra’s algorithm can be used to find the transitive closure of a
directed graph.

Q11 Which of the following refers to the recurrence for time complexity of Strassen’s
matrix-multiplication algorithm?

a. c. T(n) = 7T(n/2)+9/2 c n^2 CO1 &

1
b. T(n) = 7T(n/2)+c n^2 L2
c. T(n) = 7T(n/4)+9/2 c n
d. T(n) = 7T(n/2)+9/4 c n^2

Q12 Which of the following terms is related with the Greedy methodology?
a. Tabulation method
CO1 &
b. Looking-glass heuristic 1
c. Non-overlapping subproblems L2
d. Locally optimal choice

Q13 Which of the following refers to the recurrence for time complexity of
Karatsuba’s large-integers-multiplication algorithm?
CO1 &
a. T(n) = 2T(n/2)+c n 1
b. T(n) = 3T(n/4)+c n L2
c. T(n) = 3T(n/2)+c n
d. T(n) = 3T(n/2)+c n^2

Q14 Which of the following statements is correct?

a. In tabulation approach, a Dynamic programming algorithm computes
solution in a top-down fashion.
b. To compute the longest common subsequence of two strings of length
m and n respectively, dynamic programming algorithm takes O(mn) CO1 &
1
time. L2
c. In dynamic programming we usually reduce space by increasing the
amount of time requirements.
d. Both dynamic programming and greedy algorithms are used to solve
decision problems.

Q15 Select the correct statement from the following:

a. Greedy algorithms can be solved using memoization approach.
b. Greedy algorithms are generally implemented using iterative CO1 &
functions. 1
c. Dynamic programming may not produce the optimal results. L2
d. Divide-and-conquer approach is not suitable for solving the Quick sort
algorithm.

Q16 Which of the following statements is correct?

a. Dijkstra’s and Floyd’s algorithms both solve all-pairs-shortest paths problem.
b. Floyd’s algorithm is based on dynamic programming approach while CO1 &
Dijkstra’s algorithm is based on greedy strategy. 1
L2
c. Time complexities of both Dijkstra’s and Floyd’s algorithms are the same.
d. Floyd’s algorithm works even if the graph has negative weight cycle.
Q17 Select the correct statements from the following:
a. Floyd’s algorithm has a space requirement of ϴ(n), n is the number of
vertices in the graph.
b. Floyd’s algorithm can be used to find the single source shortest path in CO1 &
a weighted connected graph. 1
L2
c. Warshall’s algorithm can be used to find the transitive closure of a
directed graph.
d. Warshall’s algorithm runs in ϴ(n^2) time, n is the number of vertices in
the graph.

Q18 Which of the following is not a valid case in the Master’s method?
a. if f(n) = O(nlogba +) for some  > 0, then: T(n) = (nlogba)
b. if f(n) = O(nlogba -) for some  > 0, then: T(n) = (nlogba)
CO1 &
c. if f(n) = (nlogba), then: T(n) = (nlogba lgn) 1
d. if f(n) = (nlogba +) for some  > 0, and if af(n/b) ≤ cf(n) for some c < 1 L2
and all sufficiently large n, then T(n) = (f(n))

Q19 Select the incorrect statement from the following:

a. ‘Looking-Glass’ heuristic ensures that the pattern is compared from the last
(right-to-left) with the given text.
b. In Boyer-Moore algorithm, the time complexity of the Last-occurrence CO1 &
function depends on the size of the character set. 1
c. KMP algorithm computes the last occurrence heuristic by processing the L2
given pattern.
d. Character-jump heuristic is used by the Boyer-Moore algorithm to realign the
pattern with the given text in the case of a mismatch.

Q20 Which of the following is not an example of an intractable problem?

a. N-queens problem. CO1 &
b. Solving the Boolean Satisfiability problem. 1
c. Vertex cover problem. L2
d. Finding minimal spanning tree from a weighted connected graph.

Q21 In a state-space tree during Backtracking, which of the following statements is

correct?
a. A leaf node denotes either one of the possible solutions to the
problem or a dead end. CO1 &
1
b. A leaf node always denotes that the node is promising. L2
c. A leaf node always denotes one of the possible solutions to the
problem.
d. A leaf node always denotes that the node is not promising.

Q22 Choose the correct option from the following:

a. Subset sum problem is an example of exponential time solvable
problem. CO1 &
b. 4-Queens problem can be solved by using brute force method in 1
polynomial time. L2
c. There are 12 unique solutions to the 8-Queens problem.
d. The asymptotic lower bounds of intractable problems are linear of the
input size.
Q23 Which of the following statements is true about the Greedy algorithm design
paradigm?
a. Greedy strategy is used to solve a decision problem.
b. Greedy strategy does not always produce an optimal solution, CO1 &
1
sometimes it does. L2
c. Greedy strategy makes a globally optimal choice in the hope that this choice
will lead to a locally optimal solution.
d. Once a choice is made, it can be undone and at later step can be redone.

Q24 Which of the following statements is correct about the Backtracking approach
for solving an algorithmic problem?
a. In general, the entire search-space is searched for finding a single
solution to the given problem.
b. “Backtracking-step” refers to going back to the root node of the state- CO1 &
1
space tree. L2
c. Backtracking traces the state-space tree in a depth-first manner
for solving a problem.
d. Backtracking is method generally used to solve tractable problems.

Q25 Choose the correct option from the following statements.

a. P is the class of polynomial time solvable decision problems.
b. NP problems can be solved in polynomial time in a deterministic
machine. CO1 &
1
c. NP is the class of decision problems verifiable in constant time. L2
d. The ‘Yes’ answer of a co-NP problem can be checked in non-polynomial
time.

Q26 What is the implication of P=NP? Choose the incorrect option.

a. Boolean Satisfiability is a NP problem.
b. All NP problems can be solved in constant time in a
deterministic machine. CO1 &
c. Every NP-complete problem can be solved in polynomial time in a 1
L2
deterministic machine.
d. We will be able to solve the Vertex-Cover problem using the
algorithm of 3-SAT in polynomial time.

Q27 Which of the following statements is incorrect?

a. Subset sum is an undecidable problem.
CO1 &
b. TSP problem is exponential-time solvable. 1
c. Theory of NP-completeness applies to decision problems. L2
d. N-queens problem is an intractable problem.

Q28
In the context of NP-completeness, what does the notion of problem reduction
imply?
a. Reduce a problem P1 to another problem Q1 in exponential-time and
solve P1 using the algorithm for Q1 in polynomial time.
CO1 &
b. Reduce a problem P1 to another problem Q1 in constant-time and sole 1
P1 using the algorithm for Q1 in polynomial time. L2
c. Reduce a problem P1 to another problem Q1 in polynomial-time
and solve P1 using the algorithm for Q1.
d. None of the options is correct.
Q29 Choose the incorrect statement from the following:
a. Halting problem of Turing machine is undecidable.
b. A non-deterministic Turing machine can solve the Max-Clique problem
in polynomial time. CO1 &
1
c. A deterministic Turing machine can solve a NP-complete problem L2
in polynomial time.
d. A non-deterministic search can be performed in constant amount of
time.

Q30 Choose the correct statement from the following:

a. All modern digital computers run on non-deterministic algorithms.
b. Every deterministic algorithm has two steps – guessing and
checking/verification. CO1 &
1
c. Guessing step in a non-deterministic algorithm is a non- L2
deterministic step.
d. In NP problems, the verification of a certificate can be done in
exponential time.

Section B [20 marks]

Q31 “The notion of non-deterministic computation can be realized by allowing CO3 &
unbounded parallelism in a deterministic computer” – Justify the statement. 10
L4

Q32 Prove that the Halting problem of Turing machine is not decidable. CO3 &
10
L4