MCQ1 mark
Consider the equality and the following choices for
I.
II.
III.
IV.
The equality above remains correct if is replaced by
Single correct
MCQ2 marks
Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?
Single correct
MCQ2 marks
Language is polynomial time reducible to language . Language is polynomial time reducible to , which in turn is polynomial time reducible to language . Which of the following is/are true?
I. if , then
II. if or , then
III. , if and only if
IV. if , then and
Single correct
NAT2 marks
Let be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of is 500. When the weight of each edge of is increased by five, the weight of a minimum spanning tree becomes _____.
Numerical answer
NAT2 marks
Suppose is an array of length , where all the entries are from the set . For any positive integers and , consider the following pseudocode.
DOSOMETHING (c, a, n)
z ← 1
for i ← 0 to k − 1
do z ← z² mod n
if c[i] = 1
then z ← (z × a) mod n
return zNumerical answer
MCQ2 marks
Let and , where is a positive integer. Which of the following statements is/are correct?
I.
II.
Single correct
NAT1 mark
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _____.
Numerical answer
MCQ1 mark
You have an array of elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
Single correct
NAT2 marks
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 with . Given a shortcut if you are at position on the number line, you may directly move to . Suppose denotes the smallest number of steps needed to move from 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 and be such that . Then the value of the product is _____.
Numerical answer
MCQ2 marks
Consider the decision problem 2CNFSAT defined as follows:
For example, is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is
Single correct
MCQ2 marks
Consider the C function given below. Assume that the array
listA contains n (> 0) elements, sorted in ascending order.
int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0;
j = n-1;
do {
k = (i+j)/2;
if (x <= listA[k])
j = k-1;
if (listA[k] <= x)
i = k+1;
}while (i <= j);
if (listA[k] == x)
return(k);
else
return -1;
}ProcessArray is CORRECT?Single correct
Use ← → to move