Question 1 
If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?
Suffix (L) = {y ∈ Σ* such that xy ∈ L}  
{ww^{R} │w ∈ L}  
Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L}  
L ∙ L^{R} = {xy │ x ∈ L, y^{R} ∈ L} 
Question 2 
The chip select logic for a certain DRAM chip in a memory system design is shown below. Assume that the memory system has 16 address lines denoted by A_{15} to A_{0}. What is the range of addresses (in hexadecimal) of the memory system that can get enabled by the chip select (CS) signal?
C800 to C8FF  
C800 to CFFF  
DA00 to DFFF  
CA00 to CAFF 
The chip select address for given figure:
A_{4}  A_{15} = 2^{5}
So, total addressable loactions = 2^{16}/2^{5} = 2^{11}
2^{11} = 2048 or location 0 to 2047
∴ CFFF  C800 = 2047
Answer is C800 to CFFF.
Question 4 
Which of the following protocol pairs can be used to send and retrieve emails (in that order)?
SMTP, MIME  
SMTP, POP3  
IMAP, POP3  
IMAP, SMTP 
POP3: Post Office Protocol (Responsible for retrieve email)
SMTP: Simple Mail Transfer Protocol (Responsible for send Email)
IMAP: Internet Message Access protocol (Responsible for store and view)
MIME: Multi purpose Internet Mail Extensions (For media)
Question 5 
Which one of the following statements is NOT correct about the B^{+} tree data structure used for creating an index of a relational database table?
Each leaf node has a pointer to the next leaf node  
Nonleaf nodes have pointers to data records  
B^{+} Tree is a heightbalanced tree  
Key values in each node are kept in sorted order 
In B+ trees nonleaf nodes do not have pointers to data records.
Question 6 
#include <stdio.h> int main () { int arr [] = {1,2,3,4,5,6,7,8,9,0,1,2,5}, *ip = arr+4; printf ("%d\n", ip[1]); return 0; }
The number that will be displayed on execution of the program is _____.
5  
6  
7  
8 
We know that arr is a pointer to arr[ ] & hence arr+4 is pointer to 4^{th} index of array (starting from 0 to 4).
Now *ip is a pointer of int type pointing to memory location108, which is part of arr.
Hence, when we will print ip[1] it will be equivalent to *(ip+1).
Address of ip will be incremented by 1 & value inside 110 will be printed.
Question 7 
A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32bit address. How many bits are required for the Tag and the Index fields resectively in the addresses generated by the processor?
28 bits and 0 bits  
24 bits and 4 bits  
24 bits and 0 bits  
28 bits and 4 bits 
No index bits is there. So, now for tag bits,
Total bits  Offset bits = 32  4 = 28
So, tag bits = 28, Index bits = 0
Question 8 
Consider the following two statements about database transaction schedules:
I. Strict twophase locking protocol generates conflict serializable schedules that are also recoverable. II. Timestampordering concurrency control protocol with Thomas Write Rule can generate view serializable schedules that are not conflict serializable.Which of the above statements is/are TRUE?
Both I and II  
Neither I nor II  
II only  
I only 
In strict 2PL, a transaction T does not release any of its exclusive (write) locks until after it commits or aborts.
Hence, no other transaction can read or write an item that is written by T unless T has committed, leading to a strict schedule for recoverability.
(Ref: Fundamentals of Database Systems by Elmasri and Navathe, 7e Pg. No. 789)
By ignoring the write, Thomas write rule allows schedules that are not conflict serializable but are nevertheless correct.
Those nonconflictserializable schedules allowed satisfy the definition of view serializable schedules.
(Ref: Database System Concepts by Silberschatch, Korth and Sudarshan, 6e Pg No. 686)
Question 9 
S → Aa A → BD B → b  ε D → d  εLet a, b, d, and $ be indexed as follows:
Compute the FOLLOW set of the nonterminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $}, then the answer should be 3210)
30  
31  
10  
21 
{Follow(B) = Follow(A) when D is epsilon}
Follow(B) = {d} Union {a} = {a,d}
Hence Answer is : 31
Question 10 
Let G be an arbitrary group. Consider the following relations on G:
R1: ∀a,b ∈ G, aR1b if and only if ∃g ∈ G such that a = g1bg R2: ∀a,b ∈ G, aR2b if and only if a = b1Which of the above is/are equivalence relation/relations?
R_{2} only  
R_{1} and R_{2}  
Neither R_{1} and R_{2}  
R_{1} only 
Consider Statement R_{1}:
Reflexive:
aR_{1}a
⇒ a = g^{1}ag
Left multiply both sides by g
⇒ ga = gg^{1}ag
Right multiply both sides by g^{1}
⇒ gag^{1} = gg^{1}agg^{1}
⇒ gag^{1} = a [∴ The relation is reflexive]
Symmetric:
If aR_{1}b, then ∃g ∈ G such that gag^{1} = b then a = g^{1}bg, which is Correct.
⇒ So, given relation is symmetric.
Transitive:
The given relation is Transitive.
So, the given relation R_{1} is equivalence.
R_{2}:
The given relation is not reflexive. So, which is not equivalence relation. Such that a ≠ a^{1}. So, only R_{1} is true.
Question 11 
1111 1111 1110 0100  
1111 1111 0001 1100  
0000 0000 1110 0100  
1000 0000 1110 0100 
1’s complement = 1111 1111 1110 0011
2’s complement = 1’s complement + 1
2’s complement = 1111 1111 1110 0100
= (28)
Question 12 
Two numbers are chosen independently and uniformly at random from the set {1, 2, ..., 13}. The probability (rounded off to 3 decimal places) that their 4bit (unsigned) binary representations have the same most significant bit is ______.
0.502  
0.461  
0.402  
0.561 
1  0001
2  0010
3  0011
4  0100
5  0101
6  0110
7  0111
8  1000
9  1001
10  1010
11  1011
12  1100
13  1101
The probability that their 4bit binary representations have the same most significant bit is
= P(MSB is 0) + P(MSB is 1)
= (7×7)/(13×13) + (6×6)/(13×13)
= (49+36)/169
= 85/169
= 0.502
Question 13 
Leftmost in reverse  
Rightmost in reverse  
Leftmost  
Rightmost 
Question 14 
Consider a sequence of 14 elements: A = [5, 10, 6, 3, 1, 2, 13, 4, 9, 1, 4, 12, 3, 0]. The subsequence sum . Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)
19  
39  
29  
09 
Ex: {A,B,C,D}
{ A,AB,AC,AD,ABC,ABD,ACD,
B, BC,BD,BCD,
C,CD,
D }
Step1: Array of elements A = [5, 10, 6, 3, 1, 2, 13, 4, 9, 1, 4, 12, 3, 0 ]
Step2: As per the given question, if they want to find maximum subsequence means
{6,3,13,4,4,12}
= 42
Step3: But according to given recurrence relation, the sequence should be continuous. {6,3,13,4,4,12}.
This is not continuous subsequence.
Step4: The continuous sequence is {6, 3, 1, 2, 13, 4, 9, 1, 4, 12}
Total is {29}
Note: We can't get more than 29 maximum subsequence sum.
Question 15 
Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100.
The process are executed on a uniprocessor system running a timeshared operating system. If the minimum and maximum possible values of D after the three processes have completed execution are X and Y respectively, then the value of Y–X is _______.
10  
40  
60  
80 
P2 reads D=100, preempted.
P1 executes D=D+20, D=120.
P3 executes D=D+10, D=130.
Now, P2 has D=100, executes
D = D50 = 10050 = 50
P2 writes D=50 final value. This is minimum.
Next,
P2 reads D=100, executes D = D50, before that assume P1 & P3 has read D=100.
P2 makes D=50 & writes it.
P1 executes (D=100), D=D+20 & P3 executes D=D+10 gives maximum value D=130.
So, Y  X = 130  50 =80.
Question 16 
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _____.
0.08  
0.01  
1  
8 
Step2: Pivot element = uniformly random.
Step3: Worst case position in the pivot element is either first (or) last.
Step4: So total 2 possibilities among 25 distinct elements
= 2/25
= 0.08
Question 17 
Let X be a square matrix. Consider the following two statements on X.
I. X is invertible. II. Determinant of X is nonzero.Which one of the following is TRUE?
I implies II; II does not imply I.  
II implies I; I does not imply II.  
I and II are equivalent statements.  
I does not imply II; II does not imply I. 
That means we can also say that determinant of X is nonzero.
Question 18 
For Σ = {a,b}, let us consider the regular language L = {xx = a^{2+3k} or x = b^{10+12k}, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
3  
9  
5  
24 
For any language L, there exists an integer n, such that for all x ∈ L with x ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) uv ≤ n
(2) v ≥ 1
(3) for all i ≥ 0: uv^{i}w ∈ L
We have to find "n" which satisfies for all the strings in L.
Considering strings derived by b^{10+12k}.
The minimum string in L = "bbbbbbbbbb" but this string b^{10} cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts "uvw" must be greater than 10 .
Question 19 
Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to
n!  
1  
(n1)!  
The total number of hamiltonian cycles in a complete graph are
(n1)!/2, where n is number of vertices.
Question 20 
Consider Z = X  Y, where X, Y and Z are all in signmagnitude form. X and Y are each represented in n bits. To avoid overflow, the representation of Z would require a minimum of:
n bits  
n + 2 bits  
n  1 bits  
n + 1 bits 
To store overflow/carry bit there should be extra space to accommodate it.
Hence, Z should be n+1 bits.
Question 21 
3  
5  
2  
1 
⇒ 3^{1} = 3 ⇒ 3 mod 5 = 3
3^{2} ⇒ 9 mod 5 = 4
3^{3} ⇒ 27 mod 5 = 2
3^{4} ⇒ 81 mod 5 = 1
3^{5} ⇒ 243 mod 5 = 3
For every four numbers sequence is repeating.
So, (51 % 4) = 3
⇒ 3^{3} = 27
⇒ 27 mod 5 = 2
Question 22 
(x + y) ⊕ z = x ⊕ (y + z)  
(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)  
x ⊕ y = x + y, if xy = 0  
x ⊕ y = (xy + x'y')' 
(x+y) ⊕ z = (1+1)⊕ 0 = 1 ⊕ 0 = 1
x ⊕ (y+z) = 1⊕(1+0) = 1 ⊕ 1 = 0
So,
(x+y) ⊕ z ≠ x ⊕ (y+z)
Question 23 
#include <stdio.h> int jumble (int x, int y) { x = 2 * x + y ; return x ; } int main ( ) { int x=2, y=5 ; y = jumble (y, x) ; x = jumble (y, x) ; printf ("%d \n", x) ; return 0 ; }The value printed by the program is ______.
26  
67  
25  
13 
#include
int jumble(int x, int y)
{
printf("Inside jumble : 2*%d + %d\n", x,y);
x = 2*x +y;
return x;
}
int main()
{
int x=2, y=5;
printf("Initial x=%d, y=%d\n",x,y);
printf("1st jumble call:jumble(%d,%d)\n",y,x);
y = jumble(y,x);
printf("Value of y after 1st jumble = %d\n", y);
printf("2^{nd} jumble call: jumble(%d,%d)\n", y,x);
x = jumble(y,x);
printf("Value of x after 2nd jumble = %d\n", x);
printf("Final : %d\n", x);
return 0;
}
////////////////////////////////////OUTPUT
Initial x=2, y=5
1^{st} jumble call: jumble(5,2)
Inside jumble : 2*5 + 2
Value of y after 1^{st} jumble = 12
2^{nd} jumble call: jumble(12,2)
Inside jumble : 2*12 + 2
Value of x after 2nd jumble = 26
Final : 26
Question 24 
The following C program is executed on a Unix/Linux system:
#include <unistd.h> int main () { int i ; for (i=0; i<10; i++) if (i%2 == 0) fork ( ) ; return 0 ; }The total number of child processes created is _____.
26  
33  
31  
28 
#include
int main( )
{
int i;
fork( );
fork( );
fork( );
fork( );
fork( );
}
n  fork statements will have 2^{n}1 child.
Hence, n = 5 ⇒ We have 31 child processes.
Question 25 
Let U = {1,2,...,n}. Let A = {(x,X)x ∈ X, X ⊆ U}. Consider the following two statements on A.
Which of the above statements is/are TRUE?
Only II  
Only I  
Neither I nor II  
Both I and II 
and given A = {(x, X), x∈X and X⊆U}
Possible sets for U = {Φ, {1}, {2}, {1, 2}}
if x=1 then no. of possible sets = 2
x=2 then no. of possible sets = 2
⇒ No. of possible sets for A = (no. of sets at x=1) + (no. of sets at x=2) = 2 + 2 = 4
Consider statement (i) & (ii) and put n=2
Statement (i) is true
Statement (i) and (ii) both are true. Answer: (C)
Question 26 
Consider the following relations P(X,Y,Z), Q(X,Y,T) and R(Y,V).
How many tuples will be returned by the following relational algebra query?
∏x(σ(P.Y=R.Y ∧ R.V=V2)(P × R))  ∏x(σ(Q.Y=R.Y ∧ Q.T>2)(Q × R))
0  
1  
2  
3 
∏_{x}(σ_{(P.Y=R.Y ∧ R.V=V2)}(P × R))
σ_{(Q.Y=R.Y ∧ Q.T>2)}(Q × R)
∏_{x}(σ_{(Q.Y=R.Y ∧ Q.T>2)}(Q × R))
∏_{x}(σ_{(P.Y=R.Y ∧ R.V=V2)}(P × R))  ∏_{x}(σ_{(Q.Y=R.Y ∧ Q.T>2)}(Q × R))
Question 27 
What is the minimum number of 2input NOR gates required to implement a 4variable function function expressed in sumofminterms form as f = Σ(0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available.
2  
4  
7  
1  
3(Option not given) 
Question 28 
Consider three machines M, N, and P with IP addresses 100.10.5.2, 100.10.5.5, and 100.10.5.6 respectively. The subnet mask is set to 255.255.255.252 for all the three machines. Which one of the following is true?
M, N, and P all belong to the same subnet  
Only M and N belong to the same subnet  
M, N, and P belong to three different subnets  
Only N and P belong to the same subnet 
Therefore, N and P belong to the same subnet.
Question 29 
Consider three 4variable functions f_{1}, f_{2} and f_{3}, which are expressed in sumofminterms as
f_{1} = Σ(0, 2, 5, 8, 14), f_{2} = Σ(2, 3, 6, 8, 14, 15), f_{3} = Σ(2, 7, 11, 14)
For the following circuit with one AND gate and one XOR gate, the output function f can be expressed as:
Σ (2, 14)  
Σ (7, 8, 11)  
Σ (2, 7, 8, 11, 14)  
Σ (0, 2, 3, 5, 6, 7, 8, 11, 14, 15) 
f3 = ∑(2,7,11,14)
f1*f2 ⊕ f3 = ∑(2,8,14) ⊕ ∑(2,7,11,14)
= ∑(8,7,11) (Note: Choose the terms which are not common)
Question 30 
S' → S S → 〈L〉  id L → L,S  S
Let I_{0} = CLOSURE ({[S' → ·S]}). The number of items in the set GOTO (I_{0} , 〈 ) is: _____.
4  
5  
6  
7 
Hence, the set GOTO (I0 , 〈 ) has 5 items.
Question 31 
I. The smallest element in a maxheap is always at a leaf node II. The second largest element in a maxheap is always a child of the root node III. A maxheap can be constructed from a binary search tree in Θ(n) time IV. A binary search tree can be constructed from a maxheap in Θ(n) timeWhich of the above statements are TRUE?
I, II and III  
II, III and IV  
I, III and IV  
I, II and IV 
(ii) TRUE: The second smallest element in a heap is always a child of root node.
(iii) TRUE: Converting from binary search tree to max heap will take O(n) time as well as O(n) space complexity.
(iv) FALSE: We can’t convert max heap to binary search tree in O(n) time.
Question 32 
In an RSA cryptosystem, the value of the public modulus parameter n is 3007. If it is also known that Φ(n) = 2880, where Φ() denotes Euler's Totient Function, then the prime factor of n which is greater than 50 is ______.
107  
97  
45  
92 
n = 3007, fi(n) = 2880 → fi(n) = (p – 1) (q – 1),
where p, q are prime factor of n.
The unit place of n is 7, it is a prime number and factor will be
1.7=7
11*17
21*37
31*47
….
31*97 =>3007
n = 3007 => 31*97
Therefore, 31 & 97 are the two prime numbers, which is satisfying the condition and 97 is greater than 50.
So, 97 is the correct answer.
Other methods:
When ϕ(n) is given when n=pq where p and q are prime numbers, then we have
ϕ(n) = (p−1)(q−1) = pq−(p+q)+1
But pq=n,
therefore, ϕ(n) = n−(p+q)+1 and p+q = n+1−ϕ(n).
Now, p and q are the roots of the equation,
x^{2} − (p+q)x + pq = (xp)(xq)
Substituting for p+q and pq in the above equation
x^{2}  (n+1ϕ(n))x + n
Question 33 
A relational database contains two tables Student and Performance as shown below:
The primary key of the Student table is Roll_no. For the Performance table, the columns Roll_no. and Subject_code together from the primary key. Consider the SQL query given below:
SELECT S.Student_name, sum (P.Marks) FROM Student S, Performance P WHERE P.Marks > 84 GROUP BY S.Student_name;
The number of rows returned by the above SQL query is _____.
0  
9  
7  
5 
SQL> SELECT S.Student_name,sum(P.Marks)
2 FROM Student S,Performance P
3 WHERE P.Marks>84
4 GROUP BY S.Student_name;
Question 34 
Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Lookaside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?
8×2^{20}  
4×2^{20}  
16×2^{10}  
256×2^{10} 
So, it can refer to 2^{7} pages.
Each page size is 8 kB & word is 4 bytes.
So, the total addresses of virtual address spaces that can be addressed
Question 35 
Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below:
These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is _____.
2  
7  
1  
4 
At this point P4 arrives with burst 'Z' & P3 is in queue with burst 3.
P1 & P2 have executed with P1 incurred delay 1unit & P2 0units.
Hence, Avg = 0+1+x/4 =1
⇒ x=3, the next delay should be 3. It would happen if assume Z=2.
It executes and completes at 6.
P3 will wait totally for 3units.
Hence, Avg=1.
Z=2
Question 36 
Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _____.
5.54  
1.34  
4.25  
3.82 
A node can be chosen twice and the path from that node to itself will be zero.
∴ Path 1 = 0
Similarly,
Path 2 = 2
Path 3 = 4
Path 4 = 4
Path 5 = 6
Path 6 = 6
Path 7 = 6
Path 8 = 6
∴ Expected value = Σ Path length × Probability of selecting path
= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8
= 1/4 + 1/1 + 3/1 + 0
= 4 + 1/4
= 17/4
= 4.25
Question 37 
Consider that 15 machines need to be connected in a LAN using 8port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum number of switches needed is _____.
3  
7  
1  
5 
Therefore the total required number of the switches = Ceil (15 /7) = 3
Question 38 
There are n unsorted arrays: A_{1}, A_{2}, ..., A_{n}. Assume that n is odd. Each of A_{1}, A_{2}, ..., A_{n} contains n distinct elements. There are no common elements between any two arrays. The worstcase time complexity of computing the median of the medians of A_{1}, A_{2}, ..., A_{n} is
O(n)  
O(n log n)  
Ω(n^{2} log n)  
O(n^{2}) 
But it is similar to quicksort but in quicksort, partitioning will take extra time.
→ Find the median will be (i+j)/2
1. If n is odd, the value is Ceil((i+j)/2)
2. If n is even, the value is floor((i+j)/2)
> Here, total number of arrays are
⇒ O(n)*O(n)
⇒ O(n^{2})
Note:
They are clearly saying that all are distinct elements.
There is no common elements between any two arrays.
Question 39 
Suppose Y is distributed uniformly in the open interval (1,6). The probability that the polynomial 3x^{2} + 6xY + 3Y + 6 has only real roots is (rounded off to 1 decimal place) _____.
0.3  
0.9  
0.1  
0.8 
3x^{2} + 6xY + 3Y + 6
= 3x^{2} + (6Y)x + (3Y + 6)
whch is in the form: ax^{2} + bx + c
For real roots: b^{2}  4ac ≥ 0
⇒ (6Y)^{2}  4(3)(3Y + 6) ≥ 0
⇒ 36Y^{2}  36Y  72 ≥ 0
⇒ Y^{2}  Y  2 ≥ 0
⇒ (Y+1)(Y2) ≥ 0
Y = 1 (or) 2
The given interval is (1,6).
So, we need to consider the range (2,6).
The probability = (1/(61)) * (62) = 1/5 * 4 = 0.8
Question 40 
#include <stdio.h> int main() { int a[] = {2, 4, 6, 8, 10} ; int i, sum = 0, *b = a + 4 ; for (i = 0; i < 5; i++) sum = sum + (*b  i)  *(b  i) ; printf ("%d\n", sum) ; return 0 ; }The output of the above C program is _____.
3  
7  
11  
10 
#include
int main()
{
int a[] = {2,4,6,8,10};
int i, sum = 0, *b = a+4;
for(i=0; i<5; i++)
{ printf("*b, (*bi): %d , %d\n",*b, (*bi) );
printf("*(bi): %d\n",*(bi) );
printf("sum = %d + %d  %d\n",sum, (*bi),*(bi));
sum = sum + (*bi)  *(bi);
printf("sum = %d\n", sum);
}
printf("%d\n", sum);
return 0;
}
//////////////////////////////OUTPUT
*b, (*bi): 10 , 10
*(bi): 10
sum = 0 + 10  10
sum = 0
*b, (*bi): 10 , 9
*(bi): 8
sum = 0 + 9  8
sum = 1
*b, (*bi): 10 , 8
*(bi): 6
sum = 1 + 8  6
sum = 3
*b, (*bi): 10 , 7
*(bi): 4
sum = 3 + 7  4
sum = 6
*b, (*bi): 10 , 6
*(bi): 2
sum = 6 + 6  2
sum = 10
10
Question 41 
Let the set of functional dependencies F = {QR → S, R → P, S → Q} hold on a relation schema X = (PQRS). X is not in BCNF. Suppose X is decomposed into two schemas Y and Z, where Y = (PR) and Z = (QRS).
Consider the two statements given below.I. Both Y and Z are in BCNF II. Decomposition of X into Y and Z is dependency preserving and losslessWhich of the above statements is/are correct?
I only  
Neither I nor II  
II only  
Both I and II 
R → P
R^{+} = RP
* In R → P, 'R' is a super key. So, Y is in BCNF.
Z = (QRS)
QR → S
S → Q
CK's = QR, RS
* In, S → Q, 'S' is not a super key. So, Z is not in BCNF.
* Y is in BCNF and Z is not in BCNF.
* 'R' is common attribute in the relations Y and Z and R is candidate key for Y. So, the decomposition is lossless.
* The FD, R → P is applicable on Y and QR → S, S → Q are applicablein 2.
So, the decomposition is dependency preserving.
* Hence, Statement II is correct.
Question 42 
 ∀x[(∀z zx ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z zw ⇒ ((w = z) ∨ (z = 1)))]
Here 'ab' denotes that 'a divides b', where a and b are integers. Consider the following sets:
S1. {1, 2, 3, ..., 100} S2. Set of all positive integers S3. Set of all integersWhich of the above sets satisfy φ?
S1 and S3  
S1, S2 and S3  
S2 and S3  
S1 and S2 
Question 43 
A certain processor deploys a singlelevel cache. The cache block size is 8 words and the word size is 4 bytes. The memory system uses a 60MHz clock. To service a cache miss, the memory controller first takes 1 cycle to accept the starting address of the block, it then takes 3 cycles to fetch all the eight words of the block, and finally transmits the words of the requested block at the rate of 1 word per cycle. The maximum bandwidth for the memory system when the program running on the processor issues a series of read operations is ______ × 10^{6} bytes/sec.
160  
145  
172  
124 
Cache block = 8 words
Word size = 4 bytes
Cache block size = 32 bytes
Clock = 60 MHz
⇒ T = 1/clock = 1/60×10^{6} seconds
Cache miss
= 1 cycle(Address) + 3 cycles (8 words) + 1word/cycle ×8 (transfer)
= 12 cycles
= 12/60×10^{6}
Total bandwidth = total data/total time = 32 bytes/(12/60×10^{6}) = 160 × 10^{6} bytes/second
Answer: 160
Question 44 
S1. Set of all recursively enumerable languages over the alphabet {0,1} S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet {0,1} S4. Set of all nonregular languages over the alphabet {0,1}Which of the above sets are uncountable?
S2 and S3  
S3 and S4  
S1 and S4  
S1 and S2 
S2 is countable, since a valid C program represents a valid algorithm and every algorithm corresponds to a Turing Machine, so S2 is equivalent to set of all Turing Machines.
S3 is is uncountable, it is proved by diagonalization method.
S4 is uncountable, as set of nonregular languages will have languages which is set of all languages over alphabet {0,1} i.e., S3.
Question 45 
Consider the following grammar and the semantic actions to support the inheriteatd type declaration attributes. Let X_{1}, X_{2}, X_{3}, X_{4}, X_{5} and X_{6} be the placeholders for the nonterminals D, T, L or L_{1} in the following table:
Which one of the following are the appropriate choices for X_{1}, X_{2}, X_{3} and X_{4}?
X_{1} = L, X_{2} = L, X_{3} = L_{1}, X_{4} = T  
X_{1} = L, X_{2} = T, X_{3} = L_{1}, X_{4} = L  
X_{1} = T, X_{2} = L, X_{3} = L_{1}, X_{4} = T  
X_{1} = T, X_{2} = L, X_{3} = T, X_{4} = L_{1} 
L → L_{1}, id {X_{3}.type = X_{4}.type } , this production has L and L_{1}, hence X_{3} and X_{4} cannot be T.
So option 1, 3 and 4 cannot be correct.
Hence, 2 is correct answer.
Question 46 
Which one of the following languages over Σ = {a,b} is NOT contextfree?
{ww^{R} w ∈ {a,b}*}  
{wa^{n}w^{R}b^{n} w ∈ {a,b}*, n ≥ 0}  
{a^{n}b^{i}  i ∈ {n, 3n, 5n}, n ≥ 0}  
{wa^{n}b^{n}w^{R} w ∈ {a,b}*, n ≥ 0} 
This is similar to language
L = {a^{n}b^{m}c^{n}d^{m}  n, m > 0}
Suppose we push “w” then a^{n} and then w^{R}, now we cannot match b^{n} with a^{n}, because in top of stack we have w^{R}.
Question 47 
#include <stdio.h> int r() { static int num=7 ; return num ; } int main () { for (r(); r (); r()) printf ("%d", r()); return 0 ; }
Which one of the following values will be displayed on execution of the programs?
41  
63  
52  
630 
#include
int r()
{
int x;
static int num=7;
x =num;
printf("num: %d\n",x);
return x;
}
int main()
{
for(r(); r(); r())
{
printf("%d\n", r());
}
return 0;
}
//////////////////////////////OUTPUT
num: 7
num: 6
num: 5
5
num: 4
num: 3
num: 2
2
num: 1
num: 0
Question 48 
Suppose that in an IPoverEthernet network, a machine X wishes to find the MAC address of another machine Y in its subnet. Which one of the following techniques can be used for this?
X sends an ARP request packet to the local gateway's IP address which then finds the MAC address of Y and sends to X  
X sends an ARP request packet with broadcast IP address in its local subnet  
X sends an ARP request packet to the local gateway's MAC address which then finds the MAC address of Y and sends to X  
X sends an ARP request packet with broadcast MAC address in its local subnet 
Since both are present in the same subnet thus an ARP request packet can be sent as broadcast MAC address, all will see but the only destination will reply as a unicast reply.
Video Reference :
http://eclassesbyravindra.com/mod/page/view.php?id=147
Question 50 
void convert (int n) { if (n < 0) printf ("%d", n); else { convert (n/2); printf ("%d", n%2); } }
Which one of the following will happen when the function convert is called with any positive integer n as argument?
It will print the binary representation of n in the reverse order and terminate  
It will not print anything and will not terminate  
It will print the binary representation of n and terminate  
It will print the binary representation of n but will not terminate 
Sequence of function calls
Convert(6)
Convert(3)
Convert(1)
Convert(0)
:
Convert(0)
:
:
It will not terminate and never produce any output.
Note:
There is no instruction which stops the loop.
Question 51 
The index node (inode) of a Unixlike file system has 12 direct, one singleindirect and one doubleindirect pointers. The disk block size is 4 kB, and the disk block address is 32bits long. The maximum possible file size is (rounded off to 1 decimal place) ______ GB.
7.0  
9.0  
2.0  
4.0 
Max. file size
= (12 × 1k + 1k × 1k) × 4kB ≈ (1024 × 12 + 1024 × 1024) × 4 × 1024 bytes
≈ 4GB
Question 52 
Consider the following snapshot of a system running n concurrent processes. Process i is holding X_{i} instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R are currently in use. Further, for all i, process i can place a request for at most Y_{i} additional instances of R while holding the X_{i} instances it already has. Of the n processes, there are exactly two processes p and q such that Y_{p} = Y_{q} = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?
Min (X_{p}, X_{q}) ≥ Min {Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q}  
X_{p} + X_{q} < Max {Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q}  
Min (X_{p}, X_{q}) ≤ Max {Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q}  
X_{p} + X_{q} < Min {Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q} 
P_{i} holds X_{i} instances.
P_{i} can request additional Y_{i} instances.
Given two process p & q such that their additional requests are zero.
Y_{p} = Y_{q} = 0
{Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q} means that out of 'n' processes, we are left with (n2) process (except p&q), i.e., Y_{k} indicates additional request of all the processes (n2) except p & q.
For p & q to complete first, accordingly
X_{p} + X_{q} < Min {Y_{k}}
Option D is correct.
There are exactly two process p and q which do not need any additional instances of resources.
So, p and q will complete their execution and will release X_{p} and X_{q} instances of resources.
Now to guarantee that no other process apart from p and q can complete execution, the no. of instances of resources available must be less than the minimum no. of instances of resources required by any other process, i.e.,
X_{p} + X_{q} < Min {Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q}
Question 53 
Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}, where id denotes the identity function i.e. id(j) = j,∀j. Let º denote composition on functions. For a string x = x_{1} x_{2} ... x_{n} ∈ Σ^{n}, n ≥ 0. Let π(x) = x_{1} º x_{2} º ... º x_{n}.
Consider the language L = {x ∈ Σ*  π(x) = id}. The minimum number of states in any DFA accepting L is ______.
120  
136  
125  
132 
Question 54 
#include <stdio.h> int main () { float sum = 0.0, j = 1.0, i = 2.0; while (i/j > 0.0625) { j = j + j; sum = sum + i/j; printf ("%f \n", sum); } return 0; }
The number of times the variable sum will be printed, when the above program is executed , is ______.
5  
2  
7  
10 
#include
int main()
{
float sum= 0.0, j=1.0, i=2.0;
while(i/j > 0.0625)
{
j = j+j;
sum = sum+i/j;
printf("%f\n",sum);
}
return 0;
}
//////////////////////////////////OUTPUT
1.000000
1.500000
1.750000
1.875000
1.937500
Question 55 
I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimumweight edge crossing the cut.Which of the above statements is/are TRUE?
I only  
II only  
Both I and II  
Neither I nor II 
I. TRUE: G Graph is unique, no two edges of the graph is same.
Step1: Using Kruskal's algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step2:
Step3: 17 + 18 + 20 + 21 + 22 + 23 + 26 = 147
Step4: Here, all the elements are distinct. So, the possible MCST is 1.
II. TRUE: As per the above graph, if we are cut the edge, that should the be the minimum edge.
Because we are already given, all minimum edge weights if graph is distinct.
Question 56 
(P)↔(ii), Q↔(iii), (R)↔(i)  
(P)↔(iii), Q↔(i), (R)↔(ii)  
(P)↔(ii), Q↔(i), (R)↔(iii)  
(P)↔(i), Q↔(ii), (R)↔(iii) 
(Q) QuickSort is a Divide and Conquer algorithm.
(R) Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using Dynamic Programming.
Some important points regarding Greedy Vs Dynamic Programming
Greedy: →
It always gives polynomial time complexity
→ It is not an optimal
→ It always selects only either minimum or maximum among all possibilities
→ Ex: Dijkstra’s algorithm for SSSP, Optimal Merge Pattern, Huffman coding, Fractional knapsack problem, etc..,
Dynamic Programming:
→ It gives either polynomial or exponential time complexity.
→ It gives always an optimal result.
→ It checks all possibilities of a problem.
→ Ex: Longest Common sequence, Matrix chain Multiplication, Travelling sales Problem, etc..,
Question 57 
∀x(∃z(¬β)→∀y(α))  
∀x(∀z(β)→∃y(¬α))  
∀x(∀y(α)→∃z(¬β))  
∀x(∃y(¬α)→∃z(¬β)) 
∀x(∃z(¬β) → ∀y(α))
⇒ ∀x(¬∃z(¬β) ∨ ∀y(α))
⇒ ∀x(∀z(β)∨y(α))
⇒ ¬∃x¬(∀z(β)∨∀y(α))
⇒ ¬∃x(¬∀z(β)∧¬∀y(α))
A is Not equivalent to the given.
Option B:
∀x(∀z(β)→∃y(¬α))
⇒ ∀x(¬∀z(β)∨∃y(¬α))
⇒ ¬∃x¬(¬∀z(β)∨∃y(¬α))
⇒ ¬∃x(∀z(β)∨∀y(α))
B is Matching and equivalent to given.
Option C:
∀x(∀y(α)→∃z(¬β))
⇒ ∀x(¬∀y(α)∨∃z(¬β))
⇒ ¬∃x¬(¬∀y(α)∨∃z(¬β))
⇒ ¬∃x(∀y(α)∧z(β))
C is equivalent to the given.
Option D:
∀x(∃y(¬α)→∃z(¬β))
⇒ ∀x(¬∃y(¬α)∨∃z(β))
⇒ ∀x(∀y(α)∨∃z(β))
⇒ ¬∃x¬(∀y(α)∨∃z(β))
⇒ ¬∃x(¬∀y(α)∧¬∃z(β))
⇒ ¬∃x(¬∀y(α)∧∀z(¬β))
So D is Not equivalent to the given.
Question 59 
234.25  
932.50  
287.80  
122.40 
Question 60 
Embed web objects from different sites into the same page  
Refresh the page automatically after a specified interval  
Automatically redirect to another page upon download  
Display the client time as part of the page 
Question 61 
Functional Requirements
 
NonFunctional Requirements
 
Goals of Implementation
 
Algorithms for Software Implementation 
Question 62 
T1, T2, T3, T6  
T1, T3, T4, T5  
T2, T4, T5, T6  
T2, T3, T4, T5 
T1 and T2 checking same condition a = 0 hence, any one of T1 and T2 is redundant.
T3, T4: in both case discriminant (D) = b2 – 4ac = 0. Hence any one of it is
T5 : D > 0
T6 : D < 0
Question 64 
P3, Q2, R4, S1  
P2, Q3, R1, S4  
P3, Q2, R1, S4  
P2, Q3, R4, S1 
Question 65 
T1, T2, T3
 
T2, T4  
T3, T4
 
T1, T2, T4 
T2 covers S3
T4 covers S2, S4.
Question 66 
IIIIIIIVV  
VIVIIIIII
 
IIIIVIIIV
 
IVIIVIIII 
Question 67 
〈2, 2, 3〉 and 〈2, 3, 2〉  
〈2, 2, 3〉 and 〈2, 2, 3〉
 
〈2, 3, 2〉 and 〈2, 3, 2〉  
〈2, 3, 2〉 and 〈2, 2, 3〉 
Question 68 
II and III
 
II and III
 
I and III
 
I, II and III

Question 69 
I and II  
II and III
 
I and III
 
I, II and III 
Question 70 
True, True  
True, False  
False, True  
False, False 
Question 71 
It is derived from SGML  
It describes content and layout  
It allows user defined tags  
It is restricted only to be used with web browsers

Question 75 
S4 and S3  
S4 and S2  
S3 and S1  
S2 and S1 
Question 76 
Q_{1} is the correct query
 
Q_{2} is the correct query  
Both Q_{1} and Q_{2} produce the same answer  
Neither Q_{1} nor Q_{2} is the correct query 
Query 1: Results the empId's which have higher salary than anyone in the department 5.
Query 2: Results the empId's which have higher salary than atleast one employee of department 5.
Question 77 
Iteration size  
Cost  
Adopted process such as Rational Unified Process or Extreme Programming  
Risk 
Question 78 
Expert system  
DB repository  
Aircraft flight controller  
Signal processing 
Question 80 
The Title and Content elements  
The Content and TOC elements  
The Title and TOC elements  
The Title, Content and TOC elements

Question 81 
0.45  
0.63  
0.84  
0.95 
The probability or reliability that the product will work for a defined period of time without failure is given by
Question 84 
T1, T2, T8, T10  
T1, T3, T8, T10  
T1, T2, T3, T4, T5, T6, T7, T8, T9, T10  
T1, T4, T5, T7, T8, T10 
Question 87 
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at most once  
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at most once  
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once  
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at least once 
Question 89 
A software program consists of two modules M_{1} and M_{2} that can fail independently, but never simultaneously. The program is considered to have failed if any of these modules fails. Both the modules are ‘repairable’ and so the program starts working again as soon as the repair is done. Assume that the mean time to failure (MTTF) of M_{1}is T_{1} with a mean time to repair (MTTR) of R_{1}. The MTTF of M_{2} is T_{2} with an MTTR of R_{2}. What is the availability of the overall program given that the failure and repair times are all exponentially distributed random variables?
Question 90 
III and IV  
I and IV  
II and IV  
I, II and IV 
Question 91 
The professor with the lowest course evaluation  
Professors who have all their course evaluations above the university average  
The course with the lowest evaluation  
Courses with all evaluations above the university average 
Question 94 
P1P2P4, 1 day  
P1P3P4, 1 day  
P1P3P4, 2 days  
P1P2P4, 2 days 
Question 95 
100 and 1000  
100 and 1200  
150 and 1200  
200 and 2000 
Question 96 
6  
4  
3  
2 
f(Ø)=0 and f(push(S,i) = max(f(S),0) + i;
Initially stack is empty and for empty stack 0 is given.
f(push(0,2)) = max(f(Ø),0) + 2 = max(Ø,0) + 2 = 2
f(push(2,3)) = max(2,0) + (3) = 2  3 = 1
f(push(1,2)) = max(1,0) + 2 = 0 + 2 = 2
f(push(2,1)) = max(2,0)+ (1) = 2  1 = 1
f(push(1,2)) = max(1,0) + 2 = 1 + 2 = 3
So, 3 will be the answer.
∴ Option C is correct.
Question 97 
Except in case of an Operating System crash  
Except in case of a Disk crash  
Except in case of a power failure  
Always, even if there is a failure of any kind 
Question 98 
In a data link protocol, the frame delimiter flag is given by 0111. Assuming that bit stuffing is employed, the transmitter sends the data sequence 01110110 as
01101011  
011010110  
011101100  
0110101100 
Thus using the above logic,
Delimiter flag: 0111
Data sequence: 01110110
So, for a flag of 4 bits we will compare data sequence with a pattern of 3 bits, i.e., 011.
0 1 1 0 1 0 1 1 0 0
In the above pattern the underlined bits are found matched. Hence, 0 in italics is stuffed. Thus resulting in the data sequence as 0110101100 which is option (D).
Question 99 
at a fixed address in main memory  
at a fixed location on the disk  
anywhere on the disk  
at a fixed location on the system disk  
anywhere on the system disk 