All 65 questions of GATE 2014 CS (Set 2)

Question text and figures as in the official paper, with the answer from the official key. Worked solutions for every question are in your report after you take the paper as a 3-hour test.

Take this paper as a timed test Answer key and topic split

Q1 · General Aptitude · MCQ · 1 mark

What is the average of all multiples of 10 from 2 to 198?

(A)
90
(B)
100
(C)
110
(D)
120

Answer (official key): B

Worked solution: in your report after you take this paper.

Q2 · General Aptitude · MCQ · 1 mark

Choose the most appropriate phrase from the options given below to complete the following sentence.

India is a post-colonial country because

(A)
it was a former British colony
(B)
Indian Information Technology professionals have colonized the world
(C)
India does not follow any colonial practices
(D)
India has helped other countries gain freedom

Answer (official key): A

Worked solution: in your report after you take this paper.

Q3 · General Aptitude · MCQ · 1 mark

Match the columns.

Column 1	Column 2
1) eradicate	P) misrepresent
2) distort	Q) soak completely
3) saturate	R) use
4) utilize	S) destroy utterly

(A)
1:S, 2:P, 3:Q, 4:R
(B)
1:P, 2:Q, 3:R, 4:S
(C)
1:Q, 2:R, 3:S, 4:P
(D)
1:S, 2:P, 3:R, 4:Q

Answer (official key): A

Worked solution: in your report after you take this paper.

Q4 · General Aptitude · MCQ · 1 mark

The value of

\sqrt{12+\sqrt{12+\sqrt{12+\cdots}}}

(A)
3.464
(B)
3.932
(C)
4.000
(D)
4.444

Answer (official key): C

Worked solution: in your report after you take this paper.

Q5 · General Aptitude · MCQ · 1 mark

Who ___________ was coming to see us this evening?

(A)
you said
(B)
did you say
(C)
did you say that
(D)
had you said

Answer (official key): B

Worked solution: in your report after you take this paper.

Q6 · General Aptitude · MCQ · 2 marks

At what time between 6 a.m. and 7 a.m. will the minute hand and hour hand of a clock make an angle closest to $60^\circ$ ?

(A)
6:22 a.m.
(B)
6:27 a.m.
(C)
6:38 a.m.
(D)
6:45 a.m.

Answer (official key): A

Read the worked solution

Q7 · General Aptitude · MCQ · 2 marks

The old city of Koenigsberg, which had a German majority population before World War 2, is now called Kaliningrad. After the events of the war, Kaliningrad is now a Russian territory and has a predominantly Russian population. It is bordered by the Baltic Sea on the north and the countries of Poland to the south and west and Lithuania to the east respectively.

Which of the statements below can be inferred from this passage?

(A)
Kaliningrad was historically Russian in its ethnic make up
(B)
Kaliningrad is a part of Russia despite it not being contiguous with the rest of Russia
(C)
Koenigsberg was renamed Kaliningrad, as that was its original Russian name
(D)
Poland and Lithuania are on the route from Kaliningrad to the rest of Russia

Answer (official key): B

Read the worked solution

Q8 · General Aptitude · MCQ · 2 marks

The number of people diagnosed with dengue fever, contracted from the bite of a mosquito, in north India is twice the number diagnosed last year. Municipal authorities have concluded that measures to control the mosquito population have failed in this region.

Which one of the following statements, if true, does not contradict this conclusion?

(A)
A high proportion of the affected population has returned from neighbouring countries where dengue is prevalent
(B)
More cases of dengue are now reported because of an increase in the Municipal Office’s administrative efficiency
(C)
Many more cases of dengue are being diagnosed this year since the introduction of a new and effective diagnostic test
(D)
The number of people with malarial fever, also contracted from mosquito bites, has increased this year

Answer (official key): D

Worked solution: in your report after you take this paper.

Q9 · General Aptitude · MCQ · 2 marks

If $x$ is real and

|x^2-2x+3|=11,

then possible values of

|-x^3+x^2-x|

include

(A)
2, 4
(B)
2, 14
(C)
4, 52
(D)
14, 52

Answer (official key): D

Worked solution: in your report after you take this paper.

Q10 · General Aptitude · Numerical · 2 marks

The ratio of male to female students in a college for five years is plotted in the following line graph.

Year	Ratio of male to female students
2008	2.5
2009	3.0
2010	2.0
2011	1.0
2012	1.5

If the number of female students doubled in 2009, by what percent did the number of male students increase in 2009?

(Answer in integer)

Answer (official key): 140

Worked solution: in your report after you take this paper.

Q11 · Computer Networks · Numerical · 1 mark

In the diagram shown below, L1 is an Ethernet LAN and L2 is a Token-Ring LAN. An IP packet originates from sender $S$ and traverses to receiver $R$ . The links within each ISP and across the two ISPs are point-to-point optical links. The initial value of the TTL field is 32.

The maximum possible value of the TTL field when $R$ receives the datagram is __________.

Answer (official key): 26

Worked solution: in your report after you take this paper.

Q12 · Databases · Numerical · 1 mark

Given an instance of the STUDENTS relation as shown below:

StudentID	StudentName	StudentEmail	StudentAge	CPI
2345	Shankar	shankar@math	X	9.4
1287	Swati	swati@ee	19	9.5
7853	Shankar	shankar@cse	19	9.4
9876	Swati	swati@mech	18	9.3
8765	Ganesh	ganesh@civil	19	8.7

For (StudentName, StudentAge) to be a key for this instance, the value X should NOT be equal to __________.

Answer (official key): 19

Worked solution: in your report after you take this paper.

Q13 · Algorithms · MCQ · 1 mark

Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing

(A)
the shortest path between every pair of vertices
(B)
the shortest path from $W$ to every vertex in the graph
(C)
the shortest paths from $W$ to only those nodes that are leaves of $T$
(D)
the longest path in the graph

Answer (official key): B

Worked solution: in your report after you take this paper.

Q14 · Programming and Data Structures · Numerical · 1 mark

Consider the function func shown below:

int func(int num) {
  int count = 0;
  while (num) {
    count++;
    num >>= 1;
  }
  return (count);
}

The value returned by func(435) is __________.

Answer (official key): 9

Worked solution: in your report after you take this paper.

Q15 · Programming and Data Structures · MCQ · 1 mark

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is:

10, 8, 5, 3, 2.

Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

(A)
10, 8, 7, 3, 2, 1, 5
(B)
10, 8, 7, 2, 3, 1, 5
(C)
10, 8, 7, 1, 2, 3, 5
(D)
10, 8, 7, 5, 3, 2, 1

Answer (official key): A

Worked solution: in your report after you take this paper.

Q16 · Discrete Mathematics · Numerical · 1 mark

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

Answer (official key): 36

Worked solution: in your report after you take this paper.

Q17 · Operating System · Numerical · 1 mark

A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is 4 bytes in size. Given a $100 \times 10^6$ bytes disk on which the file system is stored and data block size is $10^3$ bytes, the maximum size of a file that can be stored on this disk in units of $10^6$ bytes is __________.

Answer (official key): 99.55 to 99.65

Worked solution: in your report after you take this paper.

Q18 · Digital Logic · Numerical · 1 mark

Consider the equation

(123)_5 = (x8)_y

with $x$ and $y$ as unknowns. The number of possible solutions is __________.

Answer (official key): 3

Worked solution: in your report after you take this paper.

Q19 · Databases · Numerical · 1 mark

The maximum number of superkeys for the relation schema

R(E,F,G,H)

with $E$ as the key is __________.

Answer (official key): 8

Worked solution: in your report after you take this paper.

Q20 · Computer Organization and Architecture · Numerical · 1 mark

A 4-way set-associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB.

The number of bits for the TAG field is __________.

Answer (official key): 20

Worked solution: in your report after you take this paper.

Q21 · Linear Algebra · Numerical · 1 mark

If the matrix $A$ is such that it is the product of a column vector and a row vector, then the determinant of $A$ is equal to __________.

Answer (official key): 0

Worked solution: in your report after you take this paper.

Q22 · Probability and Statistics · Numerical · 1 mark

Each of the nine words in the sentence

The quick brown fox jumps over the lazy dog

is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn at random from the box.

The expected length of the word drawn is __________.

(Round off to one decimal place)

Answer (official key): 3.8 to 3.9

Worked solution: in your report after you take this paper.

Q23 · Compiler Design · MCQ · 1 mark

Which one of the following is NOT performed during compilation?

(A)
Dynamic memory allocation
(B)
Type checking
(C)
Symbol table management
(D)
Inline expansion

Answer (official key): A

Worked solution: in your report after you take this paper.

Q24 · Computer Networks · MCQ · 1 mark

Which one of the following is TRUE about the interior gateway routing protocols — Routing Information Protocol (RIP) and Open Shortest Path First (OSPF)?

(A)
RIP uses distance vector routing and OSPF uses link state routing
(B)
OSPF uses distance vector routing and RIP uses link state routing
(C)
Both RIP and OSPF use link state routing
(D)
Both RIP and OSPF use distance vector routing

Answer (official key): A

Worked solution: in your report after you take this paper.

Q25 · Computer Networks · MCQ · 1 mark

Which one of the following socket API functions converts an unconnected active TCP socket into a passive socket?

(A)
connect
(B)
bind
(C)
listen
(D)
accept

Answer (official key): C

Worked solution: in your report after you take this paper.

Q26 · Theory of Computation · MCQ · 1 mark

L_1=\{a^n\mid n\ge0\}

and

L_2=\{b^n\mid n\ge0\},

consider the following statements:

(I) $L_1\cdot L_2$ is a regular language.

(II) $L_1\cdot L_2=\{a^n b^n\mid n\ge0\}$ .

Which one of the following is CORRECT?

(A)
Only (I)
(B)
Only (II)
(C)
Both (I) and (II)
(D)
Neither (I) nor (II)

Answer (official key): A

Worked solution: in your report after you take this paper.

Q27 · Programming and Data Structures · MCQ · 1 mark

Suppose n and p are unsigned int variables in a C program. We wish to set p to ${}^nC_3$ .

If n is large, which one of the following statements is most likely to set p correctly?

(A)
p = n * (n-1) * (n-2) / 6;
(B)
p = n * (n-1) / 2 * (n-2) / 3;
(C)
p = n * (n-1) / 3 * (n-2) / 2;
(D)
p = n * (n-1) * (n-2) / 6.0;

Answer (official key): B

Worked solution: in your report after you take this paper.

Q28 · Algorithms · MCQ · 1 mark

Which one of the following correctly determines the solution of the recurrence relation with $T(1)=1$ ?

T(n)=2T\left(\frac{n}{2}\right)+\log n

(A)
$\Theta(n)$
(B)
$\Theta(n\log n)$
(C)
$\Theta(n^2)$
(D)
$\Theta(\log n)$

Answer (official key): A

Worked solution: in your report after you take this paper.

Q29 · Compiler Design · MCQ · 1 mark

Consider the grammar defined by the following production rules, with two operators * and +:

S \to T * P

T \to U \mid T * U

P \to Q + P \mid Q

U \to id

Q \to id

Which one of the following is TRUE?

(A)
+ is left associative, while * is right associative
(B)
+ is right associative, while * is left associative
(C)
Both + and * are right associative
(D)
Both + and * are left associative

Answer (official key): B

Read the worked solution

Q30 · Theory of Computation · MCQ · 1 mark

Let $A \le_m B$ denote that language $A$ is mapping reducible, also known as many-to-one reducible, to language $B$ . Which one of the following is FALSE?

(A)
If $A \le_m B$ and $B$ is recursive, then $A$ is recursive.
(B)
If $A \le_m B$ and $A$ is undecidable, then $B$ is undecidable.
(C)
If $A \le_m B$ and $B$ is recursively enumerable, then $A$ is recursively enumerable.
(D)
If $A \le_m B$ and $B$ is not recursively enumerable, then $A$ is not recursively enumerable.

Answer (official key): D

Worked solution: in your report after you take this paper.

Q31 · Digital Logic · MCQ · 1 mark

The dual of a Boolean function

F(x_1,x_2,\ldots,x_n,+,\cdot,')

written as $F^D$ , is the same expression as that of $F$ with $+$ and $\cdot$ swapped. $F$ is said to be self-dual if

F=F^D.

The number of self-dual functions with $n$ Boolean variables is

(A)
$2^n$
(B)
$2^{n-1}$
(C)
$2^{2^n}$
(D)
$2^{2^{n-1}}$

Answer (official key): D

Worked solution: in your report after you take this paper.

Q32 · Programming and Data Structures · MCQ · 1 mark

Which one of the following is TRUE?

(A)
The requirements document also describes how the requirements that are listed in the document are implemented efficiently.
(B)
Consistency and completeness of functional requirements are always achieved in practice.
(C)
Prototyping is a method of requirements validation.
(D)
Requirements review is carried out to find the errors in system design.

Answer (official key): C

Worked solution: in your report after you take this paper.

Q33 · Calculus · MCQ · 1 mark

A non-zero polynomial $f(x)$ of degree 3 has roots at $x=1$ , $x=2$ , and $x=3$ . Which one of the following must be TRUE?

(A)
$f(0)f(4)<0$
(B)
$f(0)f(4)>0$
(C)
$f(0)+f(4)>0$
(D)
$f(0)+f(4)<0$

Answer (official key): A

Worked solution: in your report after you take this paper.

Q34 · Digital Logic · MCQ · 1 mark

Let

k=2^n.

A circuit is built by giving the output of an $n$ -bit binary counter as input to an $n$ -to- $2^n$ bit decoder. This circuit is equivalent to a

(A)
$k$ -bit binary up counter
(B)
$k$ -bit binary down counter
(C)
$k$ -bit ring counter
(D)
$k$ -bit Johnson counter

Answer (official key): C

Worked solution: in your report after you take this paper.

Q35 · Probability and Statistics · Numerical · 1 mark

The security system at an IT office is composed of 10 computers of which exactly four are working. To check whether the system is functional, the officials inspect four of the computers picked at random without replacement. The system is deemed functional if at least three of the four computers inspected are working. Let the probability that the system is deemed functional be denoted by $p$ .

Then

100p =

__________.

Answer (official key): 11.85 to 11.95

Read the worked solution

Q36 · Computer Networks · MCQ · 2 marks

A graphical HTML browser resident at a network client machine Q accesses a static HTML webpage from an HTTP server S. The static HTML page has exactly one static embedded image which is also at S. Assuming no caching, which one of the following is correct about the HTML webpage loading, including the embedded image?

(A)
Q needs to send at least 2 HTTP requests to S, each necessarily in a separate TCP connection to server S
(B)
Q needs to send at least 2 HTTP requests to S, but a single TCP connection to server S is sufficient
(C)
A single HTTP request from Q to S is sufficient, and a single TCP connection between Q and S is necessary for this
(D)
A single HTTP request from Q to S is sufficient, and this is possible without any TCP connection between Q and S

Answer (official key): B

Worked solution: in your report after you take this paper.

Q37 · Databases · MCQ · 2 marks

Consider a join in relational algebra between relations $r(R)$ and $s(S)$ using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming

size(r(R)) < size(s(S)),

the join will have fewer number of disk block accesses if

(A)
relation $r(R)$ is in the outer loop
(B)
relation $s(S)$ is in the outer loop
(C)
join selection factor between $r(R)$ and $s(S)$ is more than 0.5
(D)
join selection factor between $r(R)$ and $s(S)$ is less than 0.5

Answer (official key): A

Worked solution: in your report after you take this paper.

Q38 · Discrete Mathematics · Numerical · 2 marks

The number of distinct positive integral factors of 2014 is __________.

Answer (official key): 8

Worked solution: in your report after you take this paper.

Q39 · Discrete Mathematics · MCQ · 2 marks

Which one of the following Boolean expressions is NOT a tautology?

(A)
$((a\to b)\land(b\to c))\to(a\to c)$
(B)
$(a\leftrightarrow c)\to(\neg b\to(a\land c))$
(C)
$(a\land b\land c)\to(c\lor a)$
(D)
$a\to(b\to a)$

Answer (official key): B

Worked solution: in your report after you take this paper.

Q40 · Theory of Computation · MCQ · 2 marks

Let

L_1=\{w\in\{0,1\}^* \mid w \text{ has at least as many occurrences of }110\text{ as }011\}.

Let

L_2=\{w\in\{0,1\}^* \mid w \text{ has at least as many occurrences of }000\text{ as }111\}.

Which one of the following is TRUE?

(A)
$L_1$ is regular but not $L_2$
(B)
$L_2$ is regular but not $L_1$
(C)
Both $L_1$ and $L_2$ are regular
(D)
Neither $L_1$ nor $L_2$ are regular

Answer (official key): A

Worked solution: in your report after you take this paper.

Q41 · Databases · MCQ · 2 marks

Consider the following schedule $S$ of transactions $T_1$ , $T_2$ , $T_3$ , $T_4$ :

Step	$T_1$	$T_2$	$T_3$	$T_4$
1		Reads(X)
2			Writes(X)
3			Commit
4	Writes(X)
5	Commit
6		Writes(Y)
7		Reads(Z)
8		Commit
9				Reads(X)
10				Reads(Y)
11				Commit

Which one of the following statements is CORRECT?

(A)
$S$ is conflict-serializable but not recoverable
(B)
$S$ is not conflict-serializable but is recoverable
(C)
$S$ is both conflict-serializable and recoverable
(D)
$S$ is neither conflict-serializable nor is it recoverable

Answer (official key): C

Worked solution: in your report after you take this paper.

Q42 · Computer Organization and Architecture · MCQ · 2 marks

The value of a float type variable is represented using the single-precision 32-bit floating point format of IEEE-754 standard that uses 1 bit for sign, 8 bits for biased exponent and 23 bits for mantissa. A float type variable X is assigned the decimal value of $-14.25$ .

The representation of X in hexadecimal notation is

(A)
C1640000H
(B)
416C0000H
(C)
41640000H
(D)
C16C0000H

Answer (official key): A

Worked solution: in your report after you take this paper.

Q43 · Computer Networks · MCQ · 2 marks

An IP machine Q has a path to another IP machine H via three IP routers R1, R2, and R3.

Q -- R1 -- R2 -- R3 -- H

H acts as an HTTP server, and Q connects to H via HTTP and downloads a file. Session layer encryption is used, with DES as the shared key encryption protocol. Consider the following four pieces of information:

[I1] The URL of the file downloaded by Q
[I2] The TCP port numbers at Q and H
[I3] The IP addresses of Q and H
[I4] The link layer addresses of Q and H

Which of I1, I2, I3, and I4 can an intruder learn through sniffing at R2 alone?

(A)
Only I1 and I2
(B)
Only I1
(C)
Only I2 and I3
(D)
Only I3 and I4

Answer (official key): C

Worked solution: in your report after you take this paper.

Q44 · Programming and Data Structures · MCQ · 2 marks

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions.

Which one of the following statements is TRUE with respect to this modified stack?

(A)
A queue cannot be implemented using this stack.
(B)
A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
(C)
A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
(D)
A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

Answer (official key): C

Worked solution: in your report after you take this paper.

Q45 · Discrete Mathematics · Numerical · 2 marks

Consider the following function:

double f(double x) {
  if (abs(x*x - 3) < 0.01)
    return x;
  else
    return f(x/2 + 1.5/x);
}

Give a value $q$ , to 2 decimals, such that f(q) will return $q$ .

Answer (official key): 1.72 to 1.74

Worked solution: in your report after you take this paper.

Q46 · Discrete Mathematics · Numerical · 2 marks

The number of distinct minimum spanning trees for the weighted graph below is __________.

Answer (official key): 6

Read the worked solution

Q47 · Programming and Data Structures · MCQ · 2 marks

Consider the C function given below.

int f(int j)
{
  static int i = 50;
  int k;

  if (i == j)
  {
    printf("something");
    k = f(i);
    return 0;
  }
  else
    return 0;
}

Which one of the following is TRUE?

(A)
The function returns 0 for all values of j.
(B)
The function prints the string something for all values of j.
(C)
The function returns 0 when j = 50.
(D)
The function will exhaust the runtime stack or run into an infinite loop when j = 50.

Answer (official key): D

Worked solution: in your report after you take this paper.

Q48 · Theory of Computation · MCQ · 2 marks

Let $\langle M\rangle$ be the encoding of a Turing machine as a string over $\Sigma=\{0,1\}$ . Let

L=\{\langle M\rangle \mid M \text{ is a Turing machine that accepts a string of length }2014\}.

Then $L$ is

(A)
decidable and recursively enumerable
(B)
undecidable but recursively enumerable
(C)
undecidable and not recursively enumerable
(D)
decidable but not recursively enumerable

Answer (official key): B

Worked solution: in your report after you take this paper.

Q49 · Operating System · MCQ · 2 marks

A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, ..., 100 in that order, and repeats the access sequence three times.

Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?

(A)
Least-recently-used
(B)
First-in-first-out
(C)
Last-in-first-out
(D)
Most-recently-used

Answer (official key): D

Worked solution: in your report after you take this paper.

Q50 · Calculus · Numerical · 2 marks

The probability that a given positive integer lying between 1 and 100, both inclusive, is NOT divisible by 2, 3 or 5 is __________.

Answer (official key): 0.259 to 0.261

Worked solution: in your report after you take this paper.

Q51 · Operating System · MCQ · 2 marks

Consider the procedure below for the Producer-Consumer problem which uses semaphores:

semaphore n = 0;
semaphore s = 1;

void producer()
{
  while(true)
  {
    produce();
    semWait(s);
    addToBuffer();
    semSignal(s);
    semSignal(n);
  }
}

void consumer()
{
  while(true)
  {
    semWait(s);
    semWait(n);
    removeFromBuffer();
    semSignal(s);
    consume();
  }
}

Which one of the following is TRUE?

(A)
The producer will be able to add an item to the buffer, but the consumer can never consume it.
(B)
The consumer will remove no more than one item from the buffer.
(C)
Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.
(D)
The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation.

Answer (official key): C

Worked solution: in your report after you take this paper.

Q52 · Computer Networks · MCQ · 2 marks

Consider the store and forward packet switched network shown below.

Assume that the bandwidth of each link is $10^6$ bytes/sec. A user on host A sends a file of size $10^3$ bytes to host B through routers R1 and R2 in three different ways.

In the first case, a single packet containing the complete file is transmitted from A to B.
In the second case, the file is split into 10 equal parts, and these packets are transmitted from A to B.
In the third case, the file is split into 20 equal parts, and these packets are sent from A to B.

Each packet contains 100 bytes of header information along with the user data. Consider only transmission time and ignore processing, queuing and propagation delays. Also assume that there are no errors during transmission.

Let $T_1$ , $T_2$ and $T_3$ be the times taken to transmit the file in the first, second and third case respectively. Which one of the following is CORRECT?

(A)
$T_1 < T_2 < T_3$
(B)
$T_1 > T_2 > T_3$
(C)
$T_2 = T_3,\ T_3 < T_1$
(D)
$T_1 = T_3,\ T_3 > T_2$

Answer (official key): D

Worked solution: in your report after you take this paper.

Q53 · Databases · MCQ · 2 marks

SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested query shown below?

select * from R where a in (select S.a from S)

(A)
select R.* from R, S where R.a=S.a
(B)
select distinct R.* from R, S where R.a=S.a
(C)
select R.* from R, (select distinct a from S) as S1 where R.a=S1.a
(D)
select R.* from R, S where R.a=S.a and is unique R

Answer (official key): C

Worked solution: in your report after you take this paper.

Q54 · Algorithms · Numerical · 2 marks

Consider two strings

A=\text{"qpqrr"}

and

B=\text{"pqprqrp"}.

Let $x$ be the length of the longest common subsequence, not necessarily contiguous, between $A$ and $B$ , and let $y$ be the number of such longest common subsequences between $A$ and $B$ .

Then

x+10y=

__________.

Answer (official key): 34

Worked solution: in your report after you take this paper.

Q55 · Computer Organization and Architecture · MCQ · 2 marks

In designing a computer's cache system, the cache block, or cache line, size is an important parameter. Which one of the following statements is correct in this context?

(A)
A smaller block size implies better spatial locality
(B)
A smaller block size implies a smaller cache tag and hence lower cache tag overhead
(C)
A smaller block size implies a larger cache tag and hence lower cache hit time
(D)
A smaller block size incurs a lower cache miss penalty

Answer (official key): D

Worked solution: in your report after you take this paper.

Q56 · Compiler Design · MCQ · 2 marks

For a C program accessing X[i][j][k], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits.

t0 = i * 1024
t1 = j * 32
t2 = k * 4
t3 = t1 + t0
t4 = t3 + t2
t5 = X[t4]

Which one of the following statements about the source code for the C program is CORRECT?

(A)
X is declared as int X[32][32][8]
(B)
X is declared as int X[4][1024][32]
(C)
X is declared as char X[4][32][8]
(D)
X is declared as char X[32][16][2]

Answer (official key): A

Worked solution: in your report after you take this paper.

Q57 · Operating System · Numerical · 2 marks

Three processes A, B and C each execute a loop of 100 iterations. In each iteration of the loop, a process performs a single computation that requires $t_c$ CPU milliseconds and then initiates a single I/O operation that lasts for $t_{io}$ milliseconds. It is assumed that the computer where the processes execute has sufficient number of I/O devices and the OS assigns different I/O devices to each process. Scheduling overhead is negligible.

Process	$t_c$	$t_{io}$
A	100 ms	500 ms
B	350 ms	500 ms
C	200 ms	500 ms

The processes A, B, and C are started at times 0, 5 and 10 milliseconds respectively, in a pure time sharing system using round robin scheduling with time slice 50 milliseconds.

The time in milliseconds at which process C would complete its first I/O operation is __________.

Answer (official key): 1000

Worked solution: in your report after you take this paper.

Q58 · Discrete Mathematics · MCQ · 2 marks

In the Newton-Raphson method, an initial guess of $x_0=2$ is made and the sequence $x_0,x_1,x_2,\ldots$ is obtained for the function

0.75x^3 - 2x^2 - 2x + 4 = 0.

Consider the statements:

(I) $x_3=0$ .
(II) The method converges to a solution in a finite number of iterations.

Which of the following is TRUE?

(A)
Only I
(B)
Only II
(C)
Both I and II
(D)
Neither I nor II

Answer (official key): A

Worked solution: in your report after you take this paper.

Q59 · Discrete Mathematics · MCQ · 2 marks

Consider the following relation on subsets of the set $S$ of integers between 1 and 2014. For two distinct subsets $U$ and $V$ of $S$ , we say $U<V$ if the minimum element in the symmetric difference of the two sets is in $U$ .

Consider the following two statements:

S1: There is a subset of $S$ that is larger than every other subset.
S2: There is a subset of $S$ that is smaller than every other subset.

Which one of the following is CORRECT?

(A)
Both S1 and S2 are true
(B)
S1 is true and S2 is false
(C)
S2 is true and S1 is false
(D)
Neither S1 nor S2 is true

Answer (official key): A

Worked solution: in your report after you take this paper.

Q60 · Algorithms · Numerical · 2 marks

Consider the expression tree shown below. Each leaf represents a numerical value, which can either be 0 or 1.

Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is __________.

Answer (official key): 6

Worked solution: in your report after you take this paper.

Q61 · Algorithms · Numerical · 2 marks

Suppose $P,Q,R,S,T$ are sorted sequences having lengths 20, 24, 30, 35, and 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time.

The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is __________.

Answer (official key): 358

Worked solution: in your report after you take this paper.

Q62 · Linear Algebra · Numerical · 2 marks

The product of the non-zero eigenvalues of the matrix

\begin{bmatrix} 1 & 0 & 0 & 0 & 1\\ 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 0 & 1 \end{bmatrix}

is __________.

Answer (official key): 6

Worked solution: in your report after you take this paper.

Q63 · Computer Organization and Architecture · Numerical · 2 marks

Consider a main memory system that consists of 8 memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for 100 nanoseconds by the data, address, and control signals. During the same 100 ns, and for 500 ns thereafter, the addressed memory module executes one cycle accepting and storing the data. The internal operation of different memory modules may overlap in time, but only one request can be on the bus at any time.

The maximum number of stores, of one word each, that can be initiated in 1 millisecond is __________.

Answer (official key): 10000

Worked solution: in your report after you take this paper.

Q64 · Computer Organization and Architecture · MCQ · 2 marks

If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?

(A)
Width of tag comparator
(B)
Width of set index decoder
(C)
Width of way selection multiplexor
(D)
Width of processor to main memory data bus

Answer (official key): D

Worked solution: in your report after you take this paper.

Q65 · Discrete Mathematics · Numerical · 2 marks

A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is __________.

Answer (official key): 5

Worked solution: in your report after you take this paper.