Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t₁ and t₂ be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds?

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2
for i = 1 to n do
   for j = i to n do
      for k = j + 1 to n do
           D = D * 3

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

Which one of the following is FALSE?

A canonical set of items is given below

$$\eqalign{ & S \to L. > R \cr & Q \to R. \cr} $$

On input symbol < the set has

Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is ________.

Consider the following three statements about link state and distance vector routing protocols, for a large network with 500 network nodes and 4000 links

[S1] The computational overhead in link state protocols is higher than in distance vector protocols.
[S2] A distance vector protocol (with split horizon) avoids persistent routing loops, but not a link state protocol.
[S3] After a topology change, a link state protocol will converge faster than a distance vector protocol.

Which one of the following is correct about S1, S2, and S3?

Let the size of congestion window of a TCP connection be 32 KB when a timeout occurs. The round trip time of the connection is 100 msec and the maximum segment size used is 2 KB. The time taken (in msec) by the TCP connection to get back to 32 KB congestion window is __________.

Which one of the following are used to generate a message digest by the network security protocols?
(P) RSA
(Q) SHA-1
(R) DES
(S) MD5

An access sequence of cache block addresses is of length $$N$$ and contains $$n$$ unique block address. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by $$k.$$ What is the miss ratio if the access sequence is passed through a cache of associativity $$A\, \ge \,k$$ exercising least-recently-used replacement policy?

Consider a $$6$$-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this $$6$$-stage pipeline, the speedup achieved with respect to non-pipelined execution if $$25$$% of the instructions incur $$2$$ pipeline stall cycles is________________.

A machine has a $$32$$-bit architecture, with $$1$$-word long instructions. It has $$64$$ registers, each of which is $$32$$ bits long. It needs to support $$45$$ instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is ____________.

Consider two processors ܲ$${P_1}$$ and $${P_2}$$ executing the same instruction set. Assume that under identical conditions, for the same input, a program running on $${P_2}$$ takes $$25$$% less time but incurs $$20$$% more $$CPI$$ (clock cycles per instruction) as compared to the program running on ܲ$${P_1}$$ If the clock frequency of ܲ$${P_1}$$ is $$1GHz,$$ then the clock frequency of $${P_2}$$ (in $$GHz$$) is _____________.

Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

Consider the following C functions in which size is the number of elements in the array E:

int MyX(int *E, unsigned int size){
 int Y = 0;
 int Z;
 int i,j,k;
 for(i = 0; i < size; i++)
       Y = Y + E[i];
 for(i = 0; i < size; i++)
   for(j = i; j < size; j++){
     Z = 0;
     for(k = i; k <= j; k++)
        Z = Z + E[k];
     if(Z > Y)
        Y = X;
   }
   return Y;
}

The value returned by the function MyX is the

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes O(n^a Log^bn ). Then the value of a + 10b is _________

Given the following statements:

S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL.

S2: Given the table R(a,b,c) where a and b together form the primary key, the following is a valid table definition.

CREATE TABLE S (
 a INTEGER,
 d INTEGER,
 e INTEGER,
 PRIMARY KEY (d),
 FOREIGN KEY (a) references R)

Which one of the following statements is CORRECT?

Given the following schema:

employees(emp-id, first-name, last-name, hire-date, dept-id, salary)

departments(dept-id, dept-name, manager-id, location-id)

You want to display the last names and hire dates of all latest hires in their respective departments in the location ID 1700. You issue the following query:

SQL> SELECT last-name, hire-date 
FROM employees WHERE (dept-id, hire-date) IN 
(SELECT dept-id, MAX(hire-date) 
FROM employees JOIN departments USING(dept-id) 
WHERE location-id = 1700
GROUP BY dept-id);

What is the outcome?

Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?

Consider the relation schema $$R = \left( {E,\,F,\,G,\,H,\,I,\,J,\,K,L,\,M,\,N} \right)$$ and the set of functional dependencies $$\left\{ {\left\{ {E,F} \right\} \to \left\{ G \right\},\left\{ F \right\}} \right.$$
$$ \to \left\{ {I,J} \right\},\left\{ {E,H} \right\} \to \left\{ {K,L} \right\},\left\{ K \right\}$$
$$ \to \left\{ M \right\},\left\{ L \right\}$$
$$ \to \left. {\left\{ N \right\}} \right\}$$ on $$R.$$ What is the key for $$R?$$

Given the following two statements:
$$S1:$$ Every table with two single-valued attributes is in $$1NF, 2NF, 3NF$$ and $$BCNF.$$
$$S2:$$ $$AB \to C,\,\,D \to E,\,\,E \to C$$ is a minimal cover for the set of functional dependencies $$AB \to C,$$ $$D \to E,\,\,AB \to E,\,\,E \to C.$$

Which one of the following is CORRECT?

Consider the $$4$$-to-$$1$$ multiplexer with two select lines $${S_1}$$ and $${S_0}$$ given below

The minimal sum-of-products form of the Boolean expression for the output $$F$$ of the multiplexer is

The base (or radix) of the number system such that the following equation holds is __________
$${{312} \over {20}} = 13.1$$

Consider the following Boolean expression for $$F:$$
$$F\left( {P,\,Q,\,R,\,S} \right) = PQ + \overline P QR + \overline P Q\overline R S.$$
The minimal sum-of-products form of $$F$$ is

The maximum number of edges in a bipartite graph on $$12$$ vertices is _________.

Suppose you break a stick of unit length at a point chosen uniformaly at random. Then the expected length of the shorter stick is __________________.

Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is X/1296. The value of X is__________

Which one of the following propositional logic formulas is TRUE when exactly two of $$p, q,$$ and $$r$$ are TRUE?

Let S denote the set of all functions $$f:\,{\{ 0,\,1\} ^4}\, \to \,\{ 0,\,1\} $$. Denote by N the number of functions from S to the set {0, 1}. The value of $${\log _2}$$ $${\log _2}$$ N is___________________

The value of the dot product of the eigenvectors corresponding to any pair of different eigen values of a 4-by-4 symmetric positive definite matrix is ____________.

Consider the following system of equations:
3x + 2y = 1
4x + 7z = 1
x + y + z =3
x - 2y + 7z = 0
The number of solutions for this system is ______________________

Let the function
$$f\left( \theta \right) = \left| {\matrix{ {\sin \,\theta } & {\cos \,\theta } & {\tan \,\theta } \cr {\sin \left( {{\pi \over 6}} \right)} & {\cos \left( {{\pi \over 6}} \right)} & {\tan \left( {{\pi \over 6}} \right)} \cr {\sin \left( {{\pi \over 3}} \right)} & {\cos \left( {{\pi \over 3}} \right)} & {\tan \left( {{\pi \over 3}} \right)} \cr } } \right|$$

Where $$\theta \in \left[ {{\pi \over 6},{\pi \over 3}} \right]$$ and $$f\left( \theta \right)$$ denote the derivative of $$f$$ with repect to $$\theta $$. Which of the following statements is/are TRUE?

$${\rm I})$$ There exists $$\theta \in \left[ {{\pi \over 6},{\pi \over 3}} \right]$$ such that $$f\left( \theta \right)$$ $$= 0$$.
$${\rm I}{\rm I})$$ There exists $$\theta \in \left[ {{\pi \over 6},{\pi \over 3}} \right]$$ such that $$f\left( \theta \right)$$ $$ \ne 0$$.

The function $$f(x) =$$ $$x$$ $$sinx$$ satisfies the following equation:
$$f$$"$$\left( x \right) + f\left( x \right) + t\,\cos \,x\,\, = \,\,0$$. The value of $$t$$ is ______ .

A function $$f(x)$$ is continuous in the interval $$\left[ {0,2} \right]$$. It is known that $$f(0)$$ $$=$$ $$f(2)$$ $$= -1$$ and $$f(1)$$ $$ = 1$$. Which one of the following statements must be true?

There are 5 bags labeled 1 to 5. All the coins in given bag have the same weight. Some bags have coins of weight 10 gm, other have coins of weight 11 gm. $${\rm I}$$ pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coin is _______ .

A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1,1)} and the set of all 3-pennants is {(2,1),(1,1,1), (1,2)}. Note that the pennant (1,2) is not the same as the pennant (2,1). The number of 10-pennants is _________.

Let $$G = \left( {V,E} \right)$$ be a directed graph where $$V$$ is the set of vertices and $$E$$ the set of edges. Then which one of the following graphs has the same strongly connected components as $$G$$?

Consider the statement
"Not all that glitters is gold"
Predicate glitters$$(x)$$ is true if $$x$$ glitters and
predicate gold$$(x)$$ is true if $$x$$ is gold.

Which one of the following logical formulae represents the above statement?

An ordered $$n$$-tuple $$\left( {{d_1},\,\,{d_2},\,....,{d_n}} \right)$$ with $${{d_1} \ge ,\,\,{d_2} \ge .... \ge {d_n}}$$ is called graphic if there exists a simple undirected graph with $$n$$ vertices having degrees $${d_1},{d_2},.....,{d_n}$$ respectively. Which of the following $$6$$- tuples is NOT graphic?

Consider an undirectional graph $$G$$ where self-loops are not allowed. The vertex set of $$G$$ is $$\left\{ {\left( {i,j} \right):\,1 \le i \le 12,\,1 \le j \le 12} \right\}.$$ There is an edge between $$(a,b)$$ and $$(c,d)$$ if $$\left| {a - c} \right| \le 1$$ and $$\left| {b - d} \right| \le 1$$. The number of edges in this graph is _____.

Assume that there are $$3$$ page frames which are initially empty. If the page reference string is $$1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6,$$ the number of page faults using the optimal replacement policy is______________.

Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.

An operating system uses the Banker’s algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution. There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:

REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z
REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z

Which one of the following is TRUE?

Which one of the following is FALSE?

Consider the following set of processes that need to be scheduled on a single $$CPU.$$ All the times are given in milliseconds.

Process Name	Arrival Time	Execution Time
A	0	6
B	3	2
C	5	4
D	7	6
E	10	3

Using the $$shortest$$ $$remaining$$ $$time$$ $$first$$ scheduling algorithm, the average process turnaround time (in $$msec$$) is _______.

Consider the following program in C language:

#include < stdio.h >
main()
{
int i;
int *pi = &i;
scanf("%d", pi);
printf("%d\n", i + 5);
}

Which one of the following statements is TRUE?

Match the following:
$$1)$$ Waterfall model
$$2)$$ Evolutionary model
$$3)$$ Component-based software engineering
$$4)$$ Spiral development

$$a)$$ Specifications can be developed incrementally
$$b)$$ Requirements compromises are inevitable
$$c)$$ Explicit recognition of risk
$$d)$$ Inflexible partitioning of the project into

Let $$L$$ be a language and $$\overline L $$ be its complement. Which one of the following is NOT a viable possibility?

Which one of the following is TRUE?

Consider the finite automation in the following figure.

What is the set of reachable states for the input string $$0011?$$

Which of the regular expression given below represent the following $$DFA?$$