Data Structures and Algorithms MCQ - 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

A – 3
B – 4
C – 1
D – 2

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?

Union & intersection is slowest operation among all

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

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)

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_______.

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.

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

Codes:

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

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.