GATE 2008
Question 2 
If P, Q, R are subsets of the universal set U, then (P∩Q∩R) ∪ (P^{c}∩Q∩R) ∪ Q^{c }∪ R^{c} is
Q^{c} ∪ R^{c}
 
P ∪ Q^{c} ∪ R^{c}  
P^{c} ∪ Q^{c} ∪ R^{c}  
U 
(P∩Q∩R)∪(P^{c}∩Q∩R)∪Q^{c}∪R^{c}
It can be written as the p.q.r + p'.q.r +q' + r'
=> (p+p').q.r + q' + r'
=> q.r + (q'+r')
=> q.r + q' + r' = 1 i.e., U
Question 3 
The following system of equations

x_{1} + x_{2} + 2x_{3} = 1
x_{1} + 2x_{2} + 3x_{3} = 2
x_{1} + 4x_{2} + ax_{3} = 4
has a unique solution. The only possible value(s) for a is/are
0  
either 0 or 1  
one of 0, 1 or 1  
any real number 
When a5 = 0, then rank(A) = rank[AB]<3,
So infinite number of solutions.
But, it is given that the given system has unique solution i.e., rank(A) = rank[AB] = 3 will be retain only if a5 ≠ 0.
Question 4 
In the IEEE floating point representation, the hexadecimal value 0×00000000 corresponds to
the normalized value 2^{  127}  
the normalized value 2^{  126}  
the normalized value + 0  
the special value + 0 
Question 5 
In the Karnaugh map shown below, X denotes a don’t care term. What is the minimal form of the function represented by the Karnaugh map?
Question 6 
Let r denote number system radix. The only value(s) of r that satisfy the equation is/are
decimal 10  
decimal 11  
decimal 10 and 11  
any value > 2 
(r^{2} + 2r + 1)^{1/2} = r + 1
(r + 1)^{2} * 1/2 = r + 1
r + 1 = r + 1 Any value of r will satisfy the above equation. But the radix should be greater than 2 because the 121 has 2. So r > 2 is correct.
Question 7 
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
θ(n)  
θ(m)  
θ(m+n)  
θ(mn) 
Suppose if we are using Adjacency matrix means it takes θ(n^{2}).
Question 8 
Given f_{1}, f_{3} and f in canonical sum of products form (in decimal) for the circuit
 f_{1} = Σm(4,5,6,7,8)
f_{3} = Σm(1,6,15)
f = Σm(1,6,8,15)
then f_{2} is
Σm(4,6)  
Σm(4,8)  
Σm(6,8)  
Σm(4,6,8) 
f_{1}*f_{2} is intersection of minterms of f_{1} and f_{2}
f = (f_{1}*f_{2}) + f_{3} is union of minterms of (f_{1}*f_{2}) and f_{3}
Σm(1,6,8,15) = Σm(4,5,6,7,8) * f_{2} + Σm(1,6,15)
Options A, B and D have minterm m_{4} which result in Σm(1,4,6,15), Σm(1,4,6,8, 15) and Σm(1,4,6,8, 15)respectively and they are not equal to f.
Option C : If f_{2} = Σm(6,8)
RHS: Σm(4,5,6,7,8) * Σm(6,8) + Σm(1,6,15)
= Σm(6,8) + Σm(1,6,15)
= Σm(1,6,8,15)
= f = LHS
Question 9 
Which of the following is true for the language {a^{p}p is a prime} ?
It is not accepted by a Turing Machine  
It is regular but not contextfree
 
It is contextfree but not regular  
It is neither regular nor contextfree, but accepted by a Turing machine 
Question 10 
Which of the following are decidable?

I. Whether the intersection of two regular languages is infinite
II. Whether a given contextfree language is regular
III. Whether two pushdown automata accept the same language
IV. Whether a given grammar is contextfree
I and II  
I and IV  
II and III  
II and IV 
Statement IV is also decidable, we need to check that whether the given grammar satisfies the CFG rule (TYPE 2 grammar productions).
But statements II and III are undecidable, as there doesn’t exist any algorithm to check whether a given contextfree language is regular and whether two pushdown automata accept the same language.
Question 11 
Which of the following describes a handle (as applicable to LRparsing) appropriately?
It is the position in a sentential form where the next shift or reduce operation will occur.
 
It is nonterminal whose production will be used for reduction in the next step.  
It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur.
 
It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found.

Question 12 
Some code optimizations are carried out on the intermediate code because
They enhance the portability of the compiler to other target processors  
Program analysis is more accurate on intermediate code than on machine code
 
The information from dataflow analysis cannot otherwise be used for optimization  
The information from the front end cannot otherwise be used for optimization 
Question 13 
If L and are recursively enumerable, then L is
regular  
contextfree  
contextsensitive  
recursive 
If are recursively enumerable, then it implies that there exist a Turing Machine (lets say M2) which always HALT for the strings which is NOT in L(as L is complement of Since we can combine both Turing machines (M1 and M2) and obtain a new Turing Machine (say M3) which always HALT for the strings if it is in L and also if it is not in L. This implies that L must be recursive.
Question 14 
What is the maximum size of data that the application layer can pass on to the TCP layer below?
Any size  
2^{16} bytessize of TCP header  
2^{16} bytes  
1500 bytes 
Transport Layer  65515 byte
Network layer  65535 byte
Data link layer  1500 byte
Question 15 
Which of the following tuple relational calculus expression(s) is/are equivalent to ∀t ∈ r(P(t))?
 I. ¬∃t ∈ r(P(t))
II. ∃t ∉ r(P(t))
III. ¬∃t ∈ r(¬P(t))
IV. ∃t ∉ r(¬P(t))
I only  
II only  
III only  
III and IV only 
∀xP(x) ≡ ∼∃x(∼P(x))
∼∀x(∼P(x)) ≡ ∃x(P(x))
Given: ∀t ∈ r(P(t)) (1)
As per Demorgan law
(1) ⇒ ∼∃t ∈ r(∼P(t))
which is option (III).
Question 16 
A clustering index is defined on the fields which are of type
nonkey and ordering  
nonkey and nonordering  
key and ordering
 
key and nonordering

Question 17 
Which of the following system calls results in the sending of SYN packets?
socket  
bind  
listen  
connect 
1) The client requests a connection by sending a SYN (synchronize) message to the server.
2) The server acknowledges this request by sending SYNACK back to the client.
3) The client responds with an ACK, and the connection is established.
Question 18 
Which combination of the integer variables x, y and z makes the variable a get the value 4 in the following expression?
a = (x > y) ? ((x > z) ? x : z) : ((y > z) ? y : z)
x = 3, y = 4, z = 2  
x = 6, y = 5, z = 3  
x = 6, y = 3, z = 5  
x = 5, y = 4, z = 5 
→ We can directly eliminate the options B & C, because none of the variable can assign a value 4.
→ Given explanation is
a = (x>y)?((x>z)?x:z):((y>z)?y:z)
Option A:
x=3; y=4; z=2
a=(3>4)? ⇒ No
Then evaluate second expression ⇒ (4>2)?Yes
⇒a=y
a=4 (True)
Option D:
x=5; y=4; z=5
a=(5>4) ⇒ Yes
Then evaluate first expression ⇒ (5>5)? No
⇒ a=z ⇒ a=5 (Not true)
⇒ Answer is Option A.
Question 19 
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is
MNOPQR  
NQMPOR  
QMNPRO  
QMNPOR 
Option C: QMNPRO
→ Queue starts with Q then neighbours of Q is MNP and it is matching with the given string .
→ Now , Next node to be considered is M . Neighbours of M are N, Q and R , but N and Q are already in Queue. So, R is matching with one given string
→ Now, next node to be considered is N. Neighbours of N are M, Q and O, but M and Q are already in Queue. So, O is matching with a given string.
Hence , Option C is Correct.
Similarly, check for option (D).
Question 20 
The data blocks of a very large file in the Unix file system are allocated using
contiguous allocation  
linked allocation  
indexed allocation  
an extension of indexed allocation 
Question 21 
The minimum number of equal length subintervals needed to approximate to an accuracy of atleast using the trapezoidal rule is
1000e  
1000  
100e  
100 
Question 22 
The NewtonRaphson iteration can be used to compute the
square of R
 
reciprocal of R  
square root of R  
logarithm of R 
Question 23 
Which of the following statements is true for every planar graph on n vertices?
The graph is connected  
The graph is Eulerian
 
The graph has a vertexcover of size at most 3n/4  
The graph has an independent set of size at least n/3

(A) Consider the following disconnected graph which is planar.
So false.
(B) A graph is Eulerian if all vertices have even degree but a planar graph can have vertices with odd degree.
So false.
(D) Consider K_{4} graph. It has independent set size 1 which is less than 4/3.
So false.
Hence, option (C) is correct.
Question 24 
Let and , where k is a positive integer. Then
P = Q  k  
P = Q + k  
P = Q  
P = Q + 2 k 
P = 1+3+5+7+...+(2k1)
= (21)+(41)+(61)+(81)+...+(2k1)
= (2+4+6+8+...+2k)+(1+1+1+k times)
= Q(1+1+...+k times)
= Qk
Question 25 
A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve 3x^{4}  16x^{3} + 24x^{2} + 37 is
0  
1  
2  
3 
f’(x) = 12x^{3} + 48x^{2} + 48x = 0
12x(x^{2}  4x + 4) = 0
x=0; (x2)^{2} = 0
x=2
f’’(x) = 36x^{2}  96x + 48
f ”(0) = 48
f ”(2) = 36(4)  96(2) + 48
= 144  192 + 48
= 0
At x=2, we can’t apply the second derivative test.
f’(1) = 12; f’(3) = 36, on either side of 2 there is no sign change then this is neither minimum or maximum.
Finally, we have only one Extremum i.e., x=0.
Question 26 
If P, Q, R are Boolean variables, then
Simplifies to
Question 27 
Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that she studies mathematics the next day is 0.6. If she studies mathematics on a day, then the probability that she studies computer science the next day is 0.4. Given that Aishwarya studies computer science on Monday, what is the probability that she studies computer science on Wednesday?
0.24  
0.36  
0.4  
0.6 
(i) She study Mathematics on Tuesday and computer science on wednesday.
⇒ 0.6×0.4
⇒ 0.24
(ii) She study computer science on Tuesday and computer science on wednesday.
⇒ 0.4×0.4
⇒ 0.16
→ The probability that she study computer science on wednesday is
0.24+0.16 = 0.40
Question 28 
How many of the following matrices have an eigenvalue 1?
one  
two  
three  
four 
Answer: We have only one matrix with eigen value 1.
Question 29 
Let X be a random variable following normal distribution with mean +1 and variance 4. Let Y be another normal variable with mean 1 and variance unknown. If P(X ≤ 1) = P(Y ≥ 2), the standard deviation of Y is
3  
2  
√2  
1 
We can compare their values using standard normal distributions.
The above equation satisfies when σ_{y} will be equal to 3.
Question 30 
Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent. Which of the following first order logic statements represents the following:
Each finite state automaton has an equivalent pushdown automaton
(∀x fsa(x)) ⇒ (∃y pda(y) ∧ equivalent(x,y))  
∼∀y(∃x fsa(x) ⇒ pda(y) ∧ equivalent(x,y))  
∀x ∃y(fsa(x) ∧ pda(y) ∧ equivalent(x,y))  
∀x ∃y(fsa(y)∧ pda(x) ∧ equivalent(x,y)) 
Option A:
If everything is a FSA. Then there exists an equivalent PDA for everything.
Option B:
Not for the case Y, if there exists a FSA then it can have equivalent PDA.
Option C:
Everything is a PDA and consists equivalent PDA.
Option D:
Everything is a PDA and has exist an equivalent FSA. In option A we are getting the equivalent of a and b.
So answer is option A.
Question 31 
P and Q are two propositions. Which of the following logical expressions are equivalent?
 I. P∨∼Q
II. ∼(∼P∧Q)
III. (P∧Q)∨(P∧∼Q)∨(∼P∧∼Q)
IV. (P∧Q)∨(P∧∼Q)∨(∼P∧Q)
Only I and II  
Only I, II and III  
Only I, II and IV  
All of I, II, III and IV 
II. ∼(∼P∧Q)⇒(P∨∼Q)≡I (✔️)
III. (P×Q)∨(P×∼Q)∨(∼P×∼Q)
P∧(Q∨∼Q)∨(∼P∧∼Q)
P∨(∼P×∼Q)
(P∨∼P)×(P∨∼Q)
(P∨∼Q)≡I=II (✔️)
IV. (P×Q)∨(P∧∼Q)∨(∼P×Q)
P×(Q∨∼Q)∨(∼P∧Q)
P∨(∼P×Q)
(P∨∼P)×(P∨Q)
(P∨Q)≠I (❌)
So I≡II≡III (✔️)
Question 32 
For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to
nonuniform distribution of requests  
arm starting and stopping inertia  
higher capacity of tracks on the periphery of the platter  
use of unfair arm scheduling policies 
Because the definition of inertia is a property of matter by which it continues in its existing state of rest or uniform motion in a straight line, unless that state is changed by an external force.
Question 33 
Which of the following is/are true of the autoincrement addressing mode?
 I. It is useful in creating selfrelocating code
II. If it is included in an Instruction Set Architecture, then an additional ALU is required for effective address calculation
III. The amount of increment depends on the size of the data item accessed
I only  
II only  
III Only  
II and III only 
II. An additional ALU is not necessary for autoincrement. So this statement is wrong.
III. In autoincrement addressing mode the address where next data block to be stored is generated automatically depending upon the size of single data item required to store. This is based on pointer arithmetic. So this statement is true.
Hence option C is the answer.
Question 34 
Which of the following must be true for the RFE (Return From Exception) instruction on a general purpose processor?
 I. It must be a trap instruction
II. It must be a privileged instruction
III. An exception cannot be allowed to occur during execution of an RFE instruction
I only  
II only  
I and II only  
I, II and III only 
Question 35 
For inclusion to hold between two cache levels L1 and L2 in a multilevel cache hierarchy, which of the following are necessary?
 I. L1 must be a writethrough cache
II. L2 must be a writethrough cache
III. The associativity of L2 must be greater than that of L1
IV. The L2 cache must be at least as large as the L1 cache
IV only  
I and IV only
 
I, III and IV only  
I, II, III and IV 
1st is not always correct as data need not to be exactly same at the same point of time and so write back policy can be used in this instead of write through policy.
2nd is not needed when talking only about L1 and L2, as whether L2 is write through will have impact on any memory higher than L2, not on L1.
For 3rd, associativity can be equal also, so it need not be true.
For 4th statement, L2 cache has to be as large as L1 cache. In most cases L2 cache will be generally larger than L1 cache, but we will never have an L2 cache smaller than L1 cache. So only 4th statement is necessarily true. Hence option A is the answer.
Question 36 
Which of the following are NOT true in a pipelined processor?
 I. Bypassing can handle all RAW hazards
II. Register renaming can eliminate all register carried WAR hazards
III. Control hazard penalties can be eliminated by dynamic branch prediction
I and II only  
I and III only  
II and III only  
I, II and III 
II. True. Register renaming can eliminate all WAR Hazard as well as WAW hazard.
III. If this statement would have said that
"Control hazard penalties can be completely eliminated by dynamic branch prediction", then it is false. But it is only given that "Control hazard penalties can be eliminated by dynamic branch prediction". So, it is true.
Hence, none of the given Option is Correct.
Question 37 
The use of multiple register windows with overlap causes a reduction in the number of memory accesses for
 I. Function locals and parameters
II. Register saves and restores
III. Instruction fetches
I only  
II only  
III only  
I, II and III 
II is false as register saves and restores would still be required for each and every variable.
III is also false as instruction fetch is not affected by memory access using multiple register windows.
Question 38 
In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is
Before effective address calculation has started  
During effective address calculation  
After effective address calculation has completed  
After data cache lookup has completed 
Question 39 
Consider the following functions:

f (n) = 2^{n}
g(n) = n!
h (n) = n^{logn}
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
f(n) = O(g(n)); g(n) = O(h(n))
 
f(n) = Ω(g(n)); g(n) = O(h(n))  
g(n) = O(f(n)); h(n) = O(f(n))  
h(n) = O(f(n)); g(n) = Ω(f(n))

1. Check whether the function if polynomial time or exponential time.
2. Group them into polynomial functions and exponential function. The exponential functions are always bigger than polynomial functions.
As per the above 3 functions, the g(n) is greater than others. f(n) greater than h(n). So, the order of growth h(n) < f(n) < g(n).
Note: For computing, take always big number.
Question 40 
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
θ(n)  
θ(logn)  
θ(log*n)  
θ(1) 
1. The First occurrence of an element can be found out in O(log(n)) time using divide and conquer technique, lets say it is i.
2. The Last occurrence of an element can be found out in O(log(n)) time using divide and conquer technique,lets say it is j.
3. Now number of occurrence of that element(count) is (ji+1).
Overall time complexity = log n +log n +1 = O(logn)
Program:
/* If x is present in arr[low...high] then returns the index of first occurrence of x, otherwise returns 1 */
int binarySearch(int arr[], int low, int high, int x){
if (high >= low) {
int mid = (low + high)/2; /*low + (high  low)/2;*/
/* Check if arr[mid] is the first occurrence of x.
arr[mid] is first occurrence if x is one of the following is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid1] < x and arr[mid] == x */
if ( (mid == 0  x > arr[mid1]) && (arr[mid] == x) )
return mid;
else if (x > arr[mid]
) return_binarySearch(arr, (mid + 1), high, x);
else
return_binarySearch(arr, low, (mid  1), x);
}
return 1;
}
Note: The code finds out the first occurrence of the element in the array and checks if the element at (n/2+1)^{th} position is same(as the array is sorted). Takes O(logn) time.
Question 41 
A Btree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?
3  
4  
5  
6 
{1,2,3,...,10} which can cause maximum possi ble splits.
1, 2, 3 →
4 →
5 →
6 →
7 →
8 →
9 →
10 →
Question 42 
G is a graph on n vertices and 2n–2 edges. The edges of G can be partitioned into two edgedisjoint spanning trees. Which of the following is NOT true for G?
For every subset of k vertices, the induced subgraph has at most 2k–2 edges  
The minimum cut in G has at least two edges  
There are two edgedisjoint paths between every pair to vertices  
There are two vertexdisjoint paths between every pair of vertices 
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
> Option C: True: A spanning tree covers all the vertices. So, 2 edgedisjoint spanning trees in G means, between every pair of vertices in G we have two edgedisjoint paths (length of paths may vary).
Question 43 
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sublists each of which contains at least onefifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
T(n) ≤ 2T(n/5) + n
 
T(n) ≤ T(n/5) + T(4n/5) + n  
T(n) ≤ 2T(4n/5) + n  
T(n) ≤ 2T(n/2) + n

So, T(n/5) comparisons are needed for the first subset and T(4n/5) comparisons needed for second subset.
Now, suppose that one subset contains more than n/5 elements then another subset will contain less than 4n/5 elements. Due to which time complexity will be less than
T(n/5) + T(4n/5) + n
Because recursion tree will be more balanced.
Question 44 
The subsetsum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to
An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?
Q solves the subsetsum problem in polynomial time when the input is encoded in unary
 
Q solves the subsetsum problem in polynomial time when the input is encoded in binary
 
The subset sum problem belongs to the class NP  
The subset sum problem is NPhard 
Question 45 
Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to
only vertex a  
only vertices a, e, f, g, h  
only vertices a, b, c, d  
all the vertices 
A  B ⇒ 1
A  C ⇒ 1 + 2 = 3
A  E ⇒ 1  3 = 2
A  F ⇒ 1 3 + 2 = 0
A  G ⇒ 1  3 + 2 + 3 = 3
A  C ⇒ 1 + 2 = 3
A  H ⇒ 1 + 2  5 = 2
Question 46 
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
θ(log n)  
θ(n)  
θ(nlog n)  
None of the above, as the tree cannot be uniquely determined 
T(n) = T(k) + T(nk1) + logn
In worst case T(n) = O(nlogn), when k=0
But searching for an element in the inorder traversal of given BST can be done in O(1) because we have n elements from 1...n so there is no need to search an element if last element in post order is say 5 we take it as root and since 4 elements are split the post order array into two (first 4 elements), (6th element onward) and solve recursively. Time complexity for this would be
T(n) = T(k) + T(nk1)+O(1)
Which gives T(n) = O(n)
since we know that all elements must be traversed at least once T(n) = θ(n)
Question 47 
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
θ(log n)  
θ(n)  
θ(nlog n)  
θ(n^{2}) 
Note: We can also insert all the elements once, there will be no difference on time complexity.
Question 48 
Which of the following statements is false?
Every NFA can be converted to an equivalent DFA  
Every nondeterministic Turing machine can be converted to an equivalent deterministic Turing machine
 
Every regular language is also a contextfree language
 
Every subset of a recursively enumerable set is recursive 
Question 49 
Given below are two finite state automata (→ indicates the start state and F indicates a final state)
Which of the following represents the product automaton Z×Y?
Lets rename table Z (for sake of clarity)
And Table Y (same as given in question)
The product automata will have states { One1, One2, Two1, Two2} Where One1 is P , Two2 is R and One2 is Q and Two1 is S.
The transition table for Z × Y is given below:
NOTE: LAST TWO ROWS DOESN’T MATCH WITH OPTION A. BUT IF THE ASSUMPTION IN QUESTION SUCH AS STATE “11” IS P AND STATE “22” IS R, HOLDS, THEN THE ONLY OPTION MATCHES WITH PRODUCT AUTOMATA IS OPTION A, AS (FIRST ROW) , P (ON “a”) > S AND P (ON “b”) > R, IS THE ONLY OPTION MATCHING WITH OPTION A.
Question 50 
Which of the following statements are true?
 I. Every leftrecursive grammar can be converted to a
rightrecursive grammar and viceversa
II. All \epsilon productions can be removed from any contextfree grammar by suitable transformations
III. The language generated by a contextfree grammar all of whose productions are of the form X → w or X → wY (where, w is a string of terminals and Y is a nonterminal), is always regular
IV. The derivation trees of strings generated by a contextfree grammar in Chomsky Normal Form are always binary trees
I, II, III and IV  
II, III and IV only  
I, III and IV only  
I, II and IV only 
Statement III is also true, as this is the standard definition of regular grammar (TYPE 3 grammar).
Statement IV is also true, as in CNF the only productions allowed are of type:
A> BC
A> a // where “a” is any terminal and B, C are any variables.
When we draw the parse tree for the grammar in CNF, it will always have at most two childs in every step, so it always results binary tree.
But statement II is false, as if the language contains empty string then we cannot remove every epsilon production from the CFG, since at least one production (mainly S → ϵ) must be there in order to derive empty string in language.
Question 51 
Match the following:
E  P, F  R, G  Q, H  S  
E  R, F  P, G  S, H  Q  
E  R, F  P, G  Q, H  S  
E  P, F  R, G  S, H  Q 
F matches with P, Number of formal parameters in the declaration…. matches with {L = { a^{n} b^{m} c ^{n} d^{m}  m,n >=1}
Since, a^{n} b^{m} corresponds to formal parameter (if n=2 and m=1, and “a” is int type and “b”is float type, then it means (int,int,float)) and c^{n} d^{m} corresponds to actual parameter used in function.
Similarly other two can also be argued by their reasons, but with F matches with P and H matches with S implies that option C is the only correct option.
Question 52 
Match the following NFAs with the regular expressions they correspond to
 1. ϵ + 0(01*1 + 00) * 01*
2. ϵ + 0(10 *1 + 00) * 0
3. ϵ + 0(10 *1 + 10) *1
4. ϵ + 0(10 *1 + 10) *10 *
P2, Q1, R3, S4
 
P1, Q3, R2, S4  
P1, Q2, R3, S4  
P3, Q2, R1, S4 
Similarly, The NFA represented by Q, has the form of > ϵ + 0X*0, where X is regular expression (10*1 + 00) {resolving the loop at middle state}. It matches with statement 2.
The NFA represented by R, has the form of > ϵ + 0X*1, where X is regular expression (10*1 + 01) {resolving the loop at middle state}. It matches with statement 3.
The NFA represented by S, accepts string “01” and then at final state (other than initial state) we have self loop of “0”, so we conclude that it must accept the string of the form of > ϵ + 0X* 10*, where X is regular expression (10*1 + 10) {resolving the loop at middle state}. It matches with statement 4.
Question 53 
Which of the following are regular sets?
 I. {a^{n}b^{2m}  n≥0, m≥0}
II. {a^{n}b^{m}  n=2m}
III. {a^{n}b^{m}  n≠2m}
IV. {xcy  x,y∈{a,b}*}
I and IV only  
I and III only  
I only  
IV only 
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.
Question 54 
Which of the following are true?

I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation
II. Multilevel access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions
III. Recursion in programming languages cannot be implemented with dynamic storage allocation
IV. Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stackbased allocation scheme for activation records
V.Programming languages which permit a function to return a function as its result cannot be implemented with a stackbased storage allocation scheme for activation records
II and V only  
I, III and IV only  
I, II and V only  
II, III and V only 
V. PL’s which permits a function to return a function as its result cannot be implemented with a stackbased storage allocation scheme for activation records.
II & V are True.
Question 55 
An LALR(1) parser for a grammar G can have shiftreduce (SR) conflicts if and only if
the SLR(1) parser for G has SR conflicts  
the LR(1) parser for G has SR conflicts
 
the LR(0) parser for G has SR conflicts  
the LALR(1) parser for G has reducereduce conflicts

Consider a state in LR(1) parser:
S> x.yA, a
A> x. , y
This has both shift and reduce conflict on symbol “y”.
Since LR(1) already has SR conflict , so resulting LALR(1) (after merging) will also have SR conflict.
Now if LR(1) doesn’t have SR conflict then it is guaranteed that the LALR(1) will never have SR conflict. The reason behind this is, as we merge those state only which has same set of canonical items except look ahead and the LR(1) canonical items has DFA (means from one state to other state the transition is from unique symbol) , so after merging also we will never see any shift conflict, only reducereduce may occur.
Hence An LALR(1) parser for a grammar G can have shiftreduce (SR) conflicts if and only if the LR(1) parser for G has SR conflicts.
Question 56 
In the slow start phase of the TCP congestion control algorithm, the size of the congestion window
does not increase  
increases linearly  
increases quadratically  
increases exponentially

Question 57 
If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of hosts per subnet?
1022  
1023  
2046  
2047 
Number of bits assigned for host id is the number of zeros in subnet mask. Here 11 bits are used.
for host id so maximum possible hosts are= 2^{11}  2 = 2046
Question 58 
A computer on a 10Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2Mbps. It is initially filled to capacity with 16Megabits. What is the maximum duration for which the computer can transmit at the full 10Mbps?
1.6 seconds  
2 seconds  
5 seconds  
8 seconds 
Question 59 
A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a socket (), a bind () and a listen () system call in that order, following which it is preempted. Subsequently, the client process P executes a socket () system call followed by connect () system call to connect to the server process S. The server process has not executed any accept() system call. Which one of the following events could take place?
connect ( ) system call returns successfully
 
connect ( ) system call blocks  
connect ( ) system call returns an error  
connect ( ) system call results in a core dump 
Question 60 
What is printed by the following C program?
int f(int x, int *py, int **ppz) void main() { { int y, z; int c, *b, **a; **ppz += 1; z = **ppz; c = 4; b = &c; a = &b; *py += 2; y = *py; printf("%d",f(c,b,a)); x += 3; } return x + y + z; }
18  
19  
21  
22 
f(c,&c,&(&c)) = f(4,4,4)
c is 4, b is a pointer pointing address of a, a is a pointer to pointer of c. Hence both b and c are pointing to same memory address i.e., a.
Hence whatever increment operation happens in f, it happens/ reflects on same value i.e., a.
**ppz+=1;
z=**ppz; //z=5
These steps update it to 5 and stored in z.
*py+=2; //changes c to 7, x is unchanged.
y=*py; //y=7
It updates to 7 and stored in y.
x+=3 //x is incremented by 3.
returns x+y+z = 7+7+5 = 19
Question 61 
Choose the correct option to fill ?1 and ?2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character.
void reverse(void) { int c; if(?1)reverse(); ?2 } int main(){ printf("Enter Text"); printf("n"); reverse();printf("n") ; }
?1 is (getchar( ) != ’\n’) ?2 is getchar(c);  
?1 is (c = getchar( ) ) != ’\n’) ?2 is getchar(c);  
?1 is (c != ’\n’) ?2 is putchar(c);  
?1 is ((c = getchar()) != ’\n’) ?2 is putchar(c); 
{
int c;
if(?1) reverse( );
?2
}
main( )
{
printf(“Enter Text”);
printf(“\n”);
reverse( );
printf(“\n”);
}
We can simply eliminate A & B for ?2.
& Hence
?1 is ((c=getchar( )) != ‘\n’)
?2 is putchar(c);
Question 62 
The following C function takes a singlelinked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?
struct node { int value; struct node *next; }; void rearrange(struct node *list) { struct node *p, * q; int temp; if ((!list)  !list>next)return; p = list; q = list>next; while(q) { temp = p>value;p>value = q>value; q>value = temp;p = q>next; q = p?p>next:0; } }
1,2,3,4,5,6,7  
2,1,4,3,6,5,7  
1,3,2,5,4,7,6  
2,3,4,5,6,7,1 
After 1^{st} Iteration: 2,1,3,4,5,6,7
2^{nd} Iteration: 2,1,4,3,5,6,7
3^{rd} Iteration: 2,1,4,3,6,5,7
After each exchange is done, it starts from unchanged elements due to p=q⟶next;
‘p’ pointing to Null & q pointing to 7.
Hence 2,1,4,3,6,5,7.
Question 63 
The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows:
P(s): s = s  1; if (s < 0) then wait; V(s): s = s + 1; if (s <= 0) then wakeup a process waiting on s;
Assume that P_{b} and V_{b} the wait and signal operations on binary semaphores are provided. Two binary semaphores X_{b} and Y_{b} are used to implement the semaphore operations P(s) and V(s) as follows:
P(s): P_{b}(X_{b}); s = s  1; if (s < 0) { V_{b}(X_{b}) ; P_{b}(Y_{b}) ; } else V_{b}(X_{b}); V(s): P_{b}(X_{b}) ; s = s + 1; if (s <= 0) V_{b}(Y_{b}) ; V_{b}(X_{b}) ;
The initial values of X_{b} and Y_{b} are respectively
0 and 0  
0 and 1  
1 and 0  
1 and 1 
Y_{b} must be '0' initially, because if Y_{b} is '1' initially then two process can be in critical section at the same time.
So answer is Option (C).
Question 64 
Which of the following statements about synchronous and asynchronous I/O is NOT true?
An ISR is invoked on completion of I/O in synchronous I/O but not in asynchronous I/O
 
In both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is invoked after completion of the I/O  
A process making a synchronous I/O call waits until I/O is complete, but a process making an asynchronous I/O call does not wait for completion of the I/O
 
In the case of synchronous I/O, the process waiting for the completion of I/O is woken up by the ISR that is invoked after the completion of I/O

Synchronous I/O  some execution vehicle (like a process or thread) that initiates the I/O also waits for the I/O to complete (and perhaps completes it). When the I/O completes, that same execution vehicle goes on to do something else, perhaps using the results of the I/O.
Asynchronous I/O  no execution vehicle waits for the I/O to complete. When the I/O completes, whatever execution vehicle happens to complete the I/O may arrange for later things to happen.
Option B is not true, because both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is not invoked after completion of the I/O.
Question 65 
Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?
In deadlock prevention, the request for resources is always granted if the resulting state is safe  
In deadlock avoidance, the request for resources is always granted if the result state is safe  
Deadlock avoidance is less restrictive than deadlock prevention  
Deadlock avoidance requires knowledge of resource requirements a priori 
Question 66 
A process executes the following code
for(i=0; i<n; i++) for();
The total number of child processes created is
n  
(2^{n})  1  
2^{n}  
(2^{n+1})  1 
It is a operation where process creates a copy of itself.
1,3,7,15,31,... ⇒ 2^{n}1
Question 67 
A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows
 • Bits 3031 are used to index into the first level page table
• Bits 2129 are used to index into the second level page table
• Bits 1220 are used to index into the third level page table, and
• Bits 011 are used as offset within the page
The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page tables are respectively.
20, 20 and 20  
24, 24 and 24  
24, 24 and 20  
25, 25 and 24 
From the question we can see the below info:
Physical address size = 36 bits
Physical memory size = 2^{36} bytes
Page frame size = 4K bytes = 2^{12} bytes
No. of bits for offset = 12
No. of bits required to access physical memory frame = 36 – 12 = 24
So in third level of page table, 24 bits are required to access an entry.
In second level page table entry  9 bits of virtual address are used to access second level page table entry and size of pages in second level is 4 bytes.
So size of second level page table is (2^{9})*4 = 2^{11} bytes. It means there are (2^{36})/(2^{11}) possible locations to store this page table. Therefore the second page table requires 25 bits to address it. the first page table needs 25 bits.
Answer  D
First level
Question 68 
Let R and S be two relations with the following schema
 R(P,Q,R1,R2,R3)
S(P,Q,S1,S2)
Where {P, Q} is the key for both schemas. Which of the following queries are equivalent?
 I. Π_{P}(R ⨝ S)
II. Π_{P}(R) ⨝ Π_{P}(S)
III. Π_{P}(Π_{P,Q}(R) ∩ Π_{P,Q}(S))
IV. Π_{P}(Π_{P,Q}(R)  (Π_{P,Q}(R)  Π_{P,Q}(S)))
Only I and II  
Only I and III  
Only I, II and III  
Only I, III and IV 
We have two common columns in 'R' and 'S' which are 'P' and 'Q'.
(I) Both P and Q are used while doing the join, i.e., both P and Q are used to filter.
(II) Q is not used here for filtering. Natural join is done on all P's from R and all P's from S. So different from option (I).
(III) Through venn diagram it can be proved that A∩B = A  (AB).
So through above formula we can say that (III) and (IV) are equivalent.
So, finally (I), (III) and (IV) are equivalent.
Question 69 
Consider the following relational schemes for a library database:

Book(Title, Author, Catalog_ no, Publisher, Year, Price)
Collection (Title, Author, Catalog_no)
with in the following functional dependencies:

I. Title Author → Catalog_no
II. Catalog_no → Title Author Publisher Year
III. Publisher Title Year → Price
Assume {Author, Title} is the key for both schemes. Which of the following statements is true?
Both Book and Collection are in BCNF  
Both Book and Collection are in 3NF only
 
Book is in 2NF and Collection is in 3NF  
Both Book and Collection are in 2NF only 
Book(Title, Author, Catalog_no, Publisher, Year, Price)
Collection(Title, Author, Catalog_no)
I) Title Author ⟶ Catalog_no ⟶ BCNR
II) Catalog_no ⟶ Title, Author, Publisher, Year ⟶ 3NF
III) Publisher Title Year ⟶ Price ⟶ 2NF Book’s in 2NF
Collection is in 3NF.
Question 70 
Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a nonkey field, and the file organization is unspanned. The file is stored in a file system with block size 1024 bytes, and the size of a block pointer is 10 bytes. If the secondary index is built on the key field of the file, and a multilevel index scheme is used to store the secondary index, the number of firstlevel and secondlevel blocks in the multilevel index are respectively
8 and 0  
128 and 6  
256 and 4  
512 and 5 
Record size = 32 bytes
Key size = 6 bytes
Block pointer size = 10 bytes
Block size of file system = 1024 bytes
Record (or) index entry size = 10+6 = 16 bytes
In first level no. of blocks = No. of records in a file/Block size =16384 * 16/1024 = 256
In second level, it have = 256*16 entries
In second level, no. of blocks = No. of entries/Block size = 256*16/1024 = 4
Question 71 
Consider a machine with a 2way set associative data cache of size 64Kbytes and block size 16bytes. The cache is managed using 32 bit virtual addresses and the page size is 4Kbytes. A program to be run on this machine begins as follows:
double ARR[1024][1024]; int i, j; /* Initialize array ARR to 0.0 */ for(i=0; i<1024; i++) for(j=0; j<1024; j++) ARR[i][j] = 0.0;
The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no prefetching is done. The only data memory references made by the program are those to array ARR.
The total size of the tags in the cache directory is
32Kbits  
34Kbits  
64Kbits  
68Kbits 
Block size = 16 Bytes = 2^{4} Bytes, so block offset = 4 bits
Number of blocks in the cache = 64KB / 16B = 4K
It is 2way set associative cache, so each set contains 2 blocks.
So, number of sets = 4K / 2 = 2K = 2^{11}
So, we need 11bits for set indexing.
Since the address is 32 bits long, number of tag bits = 32−11−4 = 17
Total size of the tag directory = No. of tag bits ×Number of cache blocks = 17×4K
= 68 Kbits
Question 72 
Consider a machine with a 2way set associative data cache of size 64Kbytes and block size 16bytes. The cache is managed using 32 bit virtual addresses and the page size is 4Kbytes. A program to be run on this machine begins as follows:
double ARR[1024][1024]; int i, j; /* Initialize array ARR to 0.0 */ for(i=0; i<1024; i++) for(j=0; j<1024; j++) ARR[i][j] = 0.0;
The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no prefetching is done. The only data memory references made by the program are those to array ARR.
Which of the following array elements has the same cache index as ARR[0][0]?
ARR [0] [4]  
ARR [4] [0]  
ARR [0] [5]  
ARR [5] [0] 
Block size = 16 Bytes
Number of blocks in the cache = 64KB / 16B = 4K
It is 2way set associative cache, so each set contains 2 blocks.
So, number of sets = 4K / 2 = 2K = 2^{11}
Each element size = 8B and size of each block = 16 B
No. of elements in one block = 16/8 = 2 We know no. of elements in one row of the array = 1024. So, no. of blocks for one row of the array = 1024/2 = 512
We know there are 2^{11} sets, and each set has two blocks.
For any element to share the same cache index as ARR[0][0], it has to belong to the same set.
ARR[0][0] belongs to set0. The next element that belongs to set0 will have block number 2048 because 2048 mod 2^{11} = 0.
Block number 2048 will be from row number 2048/512 = 4, because each row has 512 blocks we divide the block number with 512 to get the row number.
From the given options ARR[4][0] will have the same cache index as ARR[0][0].
Question 73 
Consider a machine with a 2way set associative data cache of size 64Kbytes and block size 16bytes. The cache is managed using 32 bit virtual addresses and the page size is 4Kbytes. A program to be run on this machine begins as follows:
double ARR[1024][1024]; int i, j; /* Initialize array ARR to 0.0 */ for(i=0; i<1024; i++) for(j=0; j<1024; j++) ARR[i][j] = 0.0;
The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no prefetching is done. The only data memory references made by the program are those to array ARR.
The cache hit ratio for this initialization loop is
0%  
25%  
50%  
75% 
So in one block 2 elements will be stored.
To store 1024×1024 elements no. of blocks needed = 1024×1024/2 = 2^{20}/2 = 2^{19}.
In each block the first element will be a miss and second element will be a hit because on every miss that entire block is brought into the cache. So, there will be 2^{19} hits and 2^{19} misses. Total no. of references = no. of elements in the array = 2^{20}
⇒ hit ratio = No. of hits / Total no. of references
= 2^{19}/2^{20} = 1/2 = 0.5
= 0.5×100 = 50%
Question 74 
Consider the following C program
int f1 (int n) { if(n == 0n == 1) return n; else return (2*f1(n1)+3*f1(n2)); } int f2 (int n) { int i; int X[N], Y[N], Z[N]; X[0]=Y[0]=Z[0]=0; X[1]=1; Y[1]=2; Z[1]=3; for(i=2; i<=n; i++) { X[i] = Y[i1] + Z[i2]; Y[i] = 2*X[i]; Z[i] = 3*X[i]; } return X[n]; }
The running time of f1(n) and f2(n) are
θ(n) and θ(n)  
θ(2^{n}) and θ(n)  
θ(n) and θ(2^{n})  
θ(2^{n}) and θ(2^{n}) 
T(n) = T(n1) + T(n2) (multiplication by 2 and 3 won't affect complexity as it is a constant time operation)
T(0) = T(1) = 1
The recurrence is similar to Fibonacci series. The time complexity is O(2^{n})
T(n) = T(n1) + T(n2) + c
T(0) = 1
T(n1) ≈ T(n2)
But in reality, T(n1) > T(n2)
So to find upper bound the expression will be
T(n) = 2T(n1) + c
= 4T(n2) + 3c
= 8T(n3) + 7c
= 2^{k}T(nk) + (2^{k}1)c
nk=0 ⇒ k = n
T(n) = 2^{n}T(0) + (2^{n}1)c
= 2^{n} + (2^{n}1)c
⇒ T(n) = O(2^{n})
The time required for f2 is O(n) (because it consists of only one loop).
Question 75 
Consider the following C program
int f1 (int n) { if(n == 0n == 1) return n; else return (2*f1(n1)+3*f1(n2)); } int f2 (int n) { int i; int X[N], Y[N], Z[N]; X[0]=Y[0]=Z[0]=0; X[1]=1; Y[1]=2; Z[1]=3; for(i=2; i<=n; i++) { X[i] = Y[i1] + Z[i2]; Y[i] = 2*X[i]; Z[i] = 3*X[i]; } return X[n]; }
f1(8) and f2(8) return the values
1661 and 1640  
59 and 59  
1640 and 1640  
1640 and 1661 
f1(2) = 2*f1(1) + 3*f1(0) = 2
f1(3) = 2*f1(2) + 3*f1(1) = 2*2 + 3*1 = 7
f1(4) = 2*f1(3) + 3*f1(2) = 2*7 + 3*2 = 20
f1(5) = 2*f1(4) + 3*f1(3) = 2*20 + 3*7 = 40 + 21 = 61
We can skip after this as the only remaining choice is (C).
f1(6) = 2*f1(5) + 3*f1(4) = 2*61 + 3*20 = 122 + 60 = 182
f1(7) = 2*f1(6) + 3*f1(5) = 2*182 + 3*61 = 364 + 183 = 547
f1(8) = 2*f1(7) + 3*f1(6) = 2*547 + 3*182 = 1094 + 546 = 1640
Question 76 
Delayed branching can help in the handling of control hazards
For all delayed conditional branch instructions, irrespective of whether the condition evaluates to true or false
The instruction following the conditional branch instruction in memory is executed.  
The first instruction in the fall through path is executed.  
The first instruction in the taken path is executed.
 
The branch takes longer to execute than any other instruction. 
Question 77 
Delayed branching can help in the handling of control hazards
The following code is to run on a pipelined processor with one branch delay slot:
I1: ADD R2 ← R7+R8 I2 : SUB R4 ← R5R6 I3 : ADD R1 ← R2+R3 I4 : STORE Memory [R4] ← [R1] BRANCH to Label if R1 == 0
Which of the instructions I1, I2, I3 or I4 can legitimately occupy the delay slot without any other program modification?
I1  
I2  
I3  
I4 
From the given set of instructions I3 is updating R1, and the branch condition is based on the value of R1 so I3 can’t be executed in the delay slot.
Instruction I1 is updating the value of R2 and R2 is used in I3. So I1 also can’t be executed in the delay slot.
Instruction I2 is updating R4, and at the memory location represented by R4 the value of R1 is stored. So if I2 is executed in the delay slot then the memory location where R1 is to be stored as part of I4 will be in a wrong place. Hence between I2 and I4, I2 can’t be executed after I4. Hence I2 can’t be executed in the delay slot.
Instruction I4 can be executed in the delay slot as this is storing the value of R1 in a memory location and executing this in the delay slot will have no effect. Hence option D is the answer.
Question 78 
Let x_{n} denote the number of binary strings of length n that contain no consecutive 0s.
Which of the following recurrences does x_{n} satisfy?
x_{n} = 2x_{n1}
 
x_{n} = x_{⌊n/2⌋}+1  
x_{n} = x_{⌊n/2⌋}+n  
x_{n} = x_{n1}+x_{n2}

⇒ Let us consider n=1
Possible binary strings: 0, 1
So, x_{1} = 2
⇒ For n = 2;
Possible strings are,
010
110
111
011
101
So, x_{3} = 5
⇒ For n=4,
Possible strings are
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
0 1 1 0
0 1 0 1
1 0 1 0
1 1 1 1
So,
x_{4}=8,
Hence, for all values of x_{4} above only option (D) satisfies.
Question 79 
Let x_{n} denote the number of binary strings of length n that contain no consecutive 0s.
The value of x_{5} is
5  
7  
8  
16 
x_{n} = x_{n1} + x_{n2}
satisfies.
And also we have found the value of x_{4} and x_{3} for the above equation.
So, according to the equation the value of x_{5} will be,
x_{5} = x_{3} + x_{4}
= 5 + 8
= 13
Hence , none of the given option is correct.
Question 80 
The subsetsum problem is defined as follows. Given a set of n positive integers, S = {a_{1},a_{2},a_{3},...,a_{n}} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2dimensional Boolean array X, with n rows and W+1 columns. X[i,j],1≤i≤n,0≤j≤W, is TRUE if and only if there is a subset of {a_{1},a_{2},...,a_{i}} whose elements sum to j.
Which of the following is valid for 2≤i≤n and a_{i}≤j≤W?
X[i, j] = X[i1, j] ∨ X[i, j  a^{i}]
 
X[i, j] = X[i1, j] ∨ X[i1, j  a^{i}]  
X[i, j] = X[i1, j] ∧ X[i, j  a^{i}]  
X[i, j] = X[i1, j] ∧ X[i 1, j  a^{i}] 
1) Sum of weights excluding a^{i} is equal to j, i.e., if X[i1, j] is true.
2) Sum of weights including a^{i} is equal to j, i.e., if X[i1, ja^{i}] is true so that we get (j – a^{i}) + a^{i} as j.
Question 81 
The subsetsum problem is defined as follows. Given a set of n positive integers, S = {a_{1},a_{2},a_{3},...,a_{n}} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2dimensional Boolean array X, with n rows and W+1 columns. X[i,j],1≤i≤n,0≤j≤W, is TRUE if and only if there is a subset of {a_{1},a_{2},...,a_{i}} whose elements sum to j.
Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
X[1, W]  
X[n, 0]  
X[n, W]  
X[n1, n] 
Note: As per present GATE syllabus, this concept is not required.
Question 82 
Consider the following ER diagram
The minimum number of tables needed to represent M, N, P, R1, R2 is
2  
3  
4  
5 
➝ Here N is a Weak entity, but it need to modify the primary key of P such as P1
M = {M1, M2, M3, P1}
P = {P1, P2}
N = {N1, N2, P1}
➝ Relationship set has its own attribute, then no need to create a separate table.
➝ Finally we require 3 minimum tables to represent M, P, N, R1, R2.
Question 83 
Consider the following ER diagram
Which of the following is a correct attribute set for one of the tables for the correct answer to the above question?
{M1, M2, M3, P1}  
{M1, P1, N1, N2}  
{M1, P1, N1}  
{M1, P1} 
For M = {M1, M2, M3, P1}
P = {P1, P2}
N = {N1, N2, P1}
Question 84 
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
1. f(int Y[10], int x) { 2. int i, j, k; 3. i = 0; j = 9; 4. do { 5. k = (i + j) /2; 6. if( Y[k] < x) i = k; else j = k; 7. } while(Y[k] != x && i < j); 8. if(Y[k] == x) printf ("x is in the array ") ; 9. else printf (" x is not in the array ") ; 10. }
On which of the following contents of Y and x does the program fail?
Y is [1 2 3 4 5 6 7 8 9 10] and x < 10  
Y is [1 3 5 7 9 11 13 15 17 19] and x < 1  
Y is [2 2 2 2 2 2 2 2 2 2] and x > 2  
Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even

Question 85 
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
1. f(int Y[10], int x) { 2. int i, j, k; 3. i = 0; j = 9; 4. do { 5. k = (i + j) /2; 6. if( Y[k] < x) i = k; else j = k; 7. } while(Y[k] != x && i < j); 8. if(Y[k] == x) printf ("x is in the array ") ; 9. else printf (" x is not in the array ") ; 10. }
The correction needed in the program to make it work properly is
Change line 6 to: if (Y[k] < x) i = k + 1; else j = k1;
 
Change line 6 to: if (Y[k] < x) i = k  1; else j = k+1;  
Change line 6 to: if (Y[k] <= x) i = k; else j = k;  
Change line 7 to: } while ((Y[k] == x) && (i < j)); 
{
int i,j,k;
i=0; j=9;
do
{
k=(i+j)/2;
if(Y[k]
else
j=k1;
} while (Y[k]!=x && i
printf(“x is in the array”);
else
printf(“x is not in the array”);
}