Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences

Avatto > > UGC NET COMPUTER SCIENCE > > PRACTICE QUESTIONS > > Data Structures and Algorithms > > Performance Analysis of Algorithms and Recurrences

121. Match the pairs in the following:

List-I		List-II
A.	All pairs shortest paths	P.	Greedy
B.	Quick Sort	Q.	Depth-First search
C.	Minimum weight spanning tree	R.	Dynamic Programming
D.	Connected Components	S.	Divide and Conquer

Answer
Comment
Array

Option : B
Explanation :
A – 3
B – 4
C – 1
D – 2

You must be logged in to post a comment.

You must be logged in to post a comment.

122. Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

Answer
Comment
Array

Option : D
Explanation :
Union & intersection is slowest operation among all

You must be logged in to post a comment.

You must be logged in to post a comment.

123. A set X can be represented by an array x[n] as follows

Consider the following algorithm in which x, y,
and z are boolean arrays of size n: algorithm
zzz (x[ ], y[ ], z[ ])
{
int i;
for (i = 0; i < n; ++ i)
z[i] = (x [i] ∧ ~ y[i]) ∨ (~ x[i] ∧ y[i]);
}
The set Z computed by the algorithm is

Answer
Comment
Array

Option : D
Explanation :
The statement inside the for loop is similar to X– OR operation such that the set obtained is (X ∩ Y') ∪ (X' ∩ Y).
It is equivalent to (X – Y) ∪ (Y – X)

You must be logged in to post a comment.

You must be logged in to post a comment.

124. Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15.
Let y and z be such that T(9) = 1 + min (T(y), T(z)). Then the value of the product yz is_______.

Answer
Comment
Array

Option : A
Explanation :
By definition, T(9) = Dist. From 9 to 100 As given, T(9) = 1+min (T(y), T()(z) = 1 + min (Dist. from y to 100, Dist. From z to 100)
⇒ 1 = Dist. from 9 to y/Dist. From 9 to z
⇒ There are only two such values-one is the simple one step on number line i.e. 10, and the other is the shortcut associated with 9 i.e. 15.
⇒ Therefore, y and z are 10 and 15 (in any order)
⇒ Product yz = 150.

You must be logged in to post a comment.

You must be logged in to post a comment.

125. Match the following:

List-I		List-II
A.	Prim's algorithm for minimum spanning tree	1.	Backtracking
B.	Floyd-Warshall algorithm for all pairs shortest paths	2.	Greedy method
C.	Mergesort	3.	Dynamic programming
D.	Hamiltonian circuit	4.	Divide and Conquer

	A	B	C	D
(a)	3	2	4	1
(b)	1	2	4	3
(c)	2	3	4	1
(d)	2	1	3	4

Answer
Comment
Array

Option : C
Explanation :
Prims algorithm is greedy method because it choose minimum distance node.
Floyd warshal’s is dynamic because it changes the distance on each iteration.
Merge sort is divide and conquer because it divide the whole list is sublist and combine after sorting each sublist
Hamiltonian cycle is based on backtracking.

You must be logged in to post a comment.

You must be logged in to post a comment.

Related Quiz.
Performance Analysis of Algorithms and Recurrences

Forgot your password?

I agree with the Terms.