GATE 2009
Question 1 
Which one of the following in NOT necessarily a property of a Group?
Commutativity
 
Associativity  
Existence of inverse for every element
 
Existence of identity 
So, commutativity is not required.
Question 2 
What is the chromatic number of an nvertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.
2  
3  
n1  
n 
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Question 3 
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
No two vertices have the same degree.  
At least two vertices have the same degree.  
At least three vertices have the same degree.  
All vertices have the same degree.

If all vertices have different degrees, then the degree sequence will be {1,2,3,....n1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n1) vertices). Degree sequence has only (n1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) Consider a triangle, all vertices has same degree, so it is false
C) Consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) Consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
Question 4 
Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one of the following is TRUE?
R is symmetric but NOT antisymmetric
 
R is NOT symmetric but antisymmetric  
R is both symmetric and antisymmetric  
R is neither symmetric nor antisymmetric 
Antisymmetric Relation: A relation R on a set A is called antisymmetric if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.
In the given relation R, for (x,y) there is no (y,x). So, this is not Symmetric. (x,z) is in R also (z,x) is in R, but as per antisymmetric relation, x should be equal to z, where this fails.
So, R is neither Symmetric nor Antisymmetric.
Question 5 
(1217)_{8} is equivalent to
(1217)_{16}
 
(028F)_{16}  
(2297)_{10}  
(0B17)_{16} 
Divide the bits into groups, each containing 4 bits.
= (0010 1000 1111)_{2}
= (28F)_{16}
Question 6 
What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2input NOR gates?
2  
3  
4  
5 
AB+C
= (A+C)(B+C) ← Distribution of + over
= ((A+C)’+(B+C)’)’
1^{st} NOR (A+C)’. Let X = (A+C)’
2^{nd} NOR (B+C)’. Let Y = (B+C)’
3^{rd} NOR (X+Y)’
Question 7 
How many 32K × 1 RAM chips are needed to provide a memory capacity of 256Kbytes?
8  
32  
64  
128 
Needed memory capacity = 256K  bytes = 256K*8 bits
Number of chips needed = 256K*8 / 32K×1 = 64
Question 8 
A CPU generally handles an interrupt by executing an interrupt service routine
As soon as an interrupt is raised.  
By checking the interrupt register at the end of fetch cycle.  
By checking the interrupt register after finishing the execution of the current instruction.  
By checking the interrupt register at fixed time intervals. 
Question 9 
In which one of the following page replacement policies, Belady’s anomaly may occur?
FIFO  
Optimal  
LRU  
MRU 
Question 10 
The essential content(s) in each entry of a page table is/are
Virtual page number  
Page frame number  
Both virtual page number and page frame number  
Access right information 
Virtual page number can represents index in the page table to get the page frame number.
Question 11 
What is the number of swaps required to sort n elements using selection sort, in the worst case?
θ(n)  
θ(n log n)  
θ(n^{2})  
θ(n^{2} logn) 
Question 12 
The language generated by the above grammar over the alphabet {a,b} is the set of
all palindromes.  
all odd length palindromes.  
strings that begin and end with the same symbol.  
all even length palindromes. 
Question 13 
Which of the following statement(s) is/are correct regarding BellmanFord shortest path algorithm?

P. Always finds a negative weighted cycle, if one
Q. Finds whether any negative weighted cycle is reachable from the source.
P Only  
Q Only  
Both P and Q  
Neither P nor Q 
More Info: The Dijkstra'a algorithm:
A greedy algorithm
Works when weights are all nonnegative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
If there is no negative cycle, a shortest path has at most V1 edges
A dynamic programming algorithm
Note: Dijkastra is faster than BellmanFord
Question 14 
Let π_{A} be a problem that belongs to the class NP. Then which one of the following is TRUE?
There is no polynomial time algorithm for π_{A}.  
If π_{A} can be solved deterministically in polynomial time,then P = NP.  
If π_{A} is NPhard, then it is NPcomplete.  
π_{A} may be undecidable. 
Question 15 
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
The set of all strings containing the substring 00.
 
The set of all strings containing at most two 0’s.  
The set of all strings containing at least two 0’s.  
The set of all strings that begin and end with either 0 or 1. 
Question 16 
Which one of the following is FALSE?
There is unique minimal DFA for every regular language.  
Every NFA can be converted to an equivalent PDA.  
Complement of every contextfree language is recursive.
 
Every nondeterministic PDA can be converted to an equivalent deterministic PDA. 
L = {ww^{r}  w ϵ {a,b}*} is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA.
Question 17 
Match all items in Group 1 with correct options from those given in Group 2
Group 1 Group 2 P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization
P4, Q1, R2, S3
 
P3, Q1, R4, S2  
P3, Q4, R1, S2  
P2, Q1, R4, S3

Question 18 
Consider the program below:
#includeint fun(int n, int *f_p) { int t, f; if (n <= 1) { *f_p = 1; return 1; } t = fun(n 1,f_p); f = t+ * f_p; *f_p = t; return f; } int main() { int x = 15; printf (" %d n", fun(5, &x)); return 0; }
The value printed is:
6  
8  
14  
15 
printf(fun(5,&x));
The code is implemented using Tail Recursion.
fun(5,15)
↓
fun(4,15)
↓
fun(3,15)
↓
fun(2,15)
↓
fun(1,15)
→ First we will trace fun(1,15) which returns 1.
→ Then trace fun(2,15) using fun(1,15) value, it returns 2.
→ Then fun(3,15), it returns 3≃(1+2)
→ Then fun(4,15), it returns 5=(2+3)
→ Then fun(5,15), it returns 8=(3+5)
If you call fun(6,15) then it will return 13=(5+8)
Here fun(n,*x)≃fun(n1,&x)+fun(n2,&x), where fun(n1,&x) is storing in variable ‘t’ & fun(n2,&x) is storing in variable x(*fp).
∴ The program is nth Fibonacci number.
Question 19 
The coupling between different modules of a software is categorized as follows:
 I. Content coupling
II. Common coupling
III. Control coupling
IV. Stamp coupling
V. Data coupling
Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows:
IIIIIIIVV  
VIVIIIIII  
IIIIVIIIV
 
IVIIVIIII 
Question 20 
Consider the HTML table definition given below:
The number of rows in each column and the number of columns in each row are:
〈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 21 
An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even numbered face is the
If the probability that the face is even given that it is greater than 3 is 0.75, which one of the following options is closest to the probability that the face value exceeds 3?
0.453  
0.468  
0.485  
0.492 
P(e) = Probability of getting even no. face.
It is given that,
P(0) = 0.9 P(e)  (I)
Also we know that,
P(0) + P(e) = 1  (II)
Solving equation (I) and (II) we get,
P(e) = 0.52
Also even no. can be 2 or 4 or 6.
And given in question that P(2) = P(4) = P(6).
So, 3 × P(2) = 0.52
P(2) = 0.175
So, P(2) = P(4) = P(6) = 0.175
Also in question it is given that,
P(e/>3) = 0.75
P(even no. greater than 3)/ P(no. greater than 3) = 0.75
P(4,6)/P(>3) = 0.75
(0.175×2)/P(>3) = 0.75
P(>3) = 0.35/0.75 = 0.467
Question 22 
For the composition table of a cyclic group shown below
Which one of the following choices is correct?
a, b are generators  
b, c are generators  
c, d are generators  
d, a are generators

We can observe that, a is an identity element. ( a *x = x ). An identity element cannot be a generator, as it cannot produce any other element ( always a*a*... = a).
Also, b*b =a, so it also cannot produce all other elements ( always b*b*... =a , where a is identify element).
c,d are able to produce other elements like { c*c =b, c*(c*c) = c*b= d, c*(c*(c*c))) = c*(c*b)= c*d=a. }. Similar with d.
Question 23 
Which one of the following is the most appropriate logical formula to represent the statement?
“Gold and silver ornaments are precious”.
The following notations are used:
G(x): x is a gold ornament S(x): x is a silver ornament P(x): x is precious
∀x(P(x) → (G(x) ∧ S(x)))  
∀x((G(x) ∧ S(x)) → P(x))  
∃x((G(x) ∧ S(x)) → P(x)  
∀x((G(x) ∨ S(x)) → P(x))

(A) for all ornaments, if it is precious then they should be gold and silver.
But, given statement does not says that, “ only gold and silver are precious “ . So this is wrong.
(B) For all ornaments, which contains gold and silver are precious.
Which is only the shaded region in the venn diagrams. But, it misses p,r regions. So, this is wrong option.
C) Some ornaments, which are gold and silver are precious. It is false, because all gold or silver ornaments are precious.
D) For all ornaments, Any ornament which is gold or silver is precious. Which is true.
Question 24 
The binary operation □ is defined as follows
Which one of the following is equivalent to P ∨ Q ?
¬Q□¬P  
P□¬Q  
¬P□Q  
¬P□¬Q 
P∨Q = P□️Q
So, option B is correct.
Question 26 
Consider the following wellformed formulae:
 I. ¬∀x(P(x))
II. ¬∃(P(x))
III. ¬∃(¬P(x))
IV. ∃x(¬(P(x))
Which of the above are equivalent?
I and III  
I and IV  
II and III  
II and IV 
II ) ¬∃x(P(x))= ∀x(~P(x))
III) ¬∃x(¬P(x)) = ∀x(P(x))
Question 27 
Given the following state table of an FSM with two states A and B, one input and one output:
If the initial state is A = 0, B = 0, what is the minimum length of an input string which will take the machine to the state A = 0, B = 1 with Output = 1?
3  
4  
5  
6 
From the given FSM we can clearly see that, if we start from initial state (00) and follow the input “101” {highlighted in RED color},
{state 00, 1} > state “01” , output 0,
{state 01, 0} > state “10” , output 0,
{state 10, 1} > state “01” , output 1,
Hence it require an input string of minimum length 3, which will take the machine to the state A=0, B=1 with Output = 1.
Question 28 
Consider a 4 stage pipeline processor. The number of cycles needed by the four instructions I1, I2, I3, I4 in stages S1, S2, S3, S4 is shown below:
What is the number of cycles needed to execute the following loop?
for (i=1 to 2) {I1; I2; I3; I4;}
16  
23  
28  
30 
Question 29 
Consider a 4way set associative cache (initially empty) with total 16 cache blocks. The main memory consists of 256 blocks and the request for memory blocks is in the following order:
0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155.
Which one of the following memory block will NOT be in cache if LRU replacement policy is used?
3  
8  
129  
216 
So number of sets = 16 / 4 = 4
Given main memory blocks will be mapped to one of the 4 sets.
The given blocks are 0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155, and they will be mapped to following sets(Since there are 4 sets we get the set number by doing mod 4):
0, 3, 1, 0, 3, 0, 1, 3, 0, 1, 3, 0, 0, 0, 1, 0, 3
The cache mapping and the replacement using LRU can be seen from the below diagram.
We can see that at the end of mapping the given block pattern block number 216 is not in the cache.
Question 30 
Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A nonpreemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the sources as follows if executed independently.
Which one of the following statements is TRUE if all three processes run concurrently starting at time t=0?
All processes will finish without any deadlock.  
Only P1 and P2 will be in deadlock.  
Only P1 and P3 will be in a deadlock.  
All three processes will be in deadlock. 
→ P1 requests 2 units of R2 which is granted.
→ P2 requests 2 units of R3 which is granted.
→ P3 requests 1 units of R4 which is granted.
Now Available resources are,
At t=1,
→ P1 requests 1 unit of R3 which is granted because it is available.
Now Available resources are,
At t=2,
→ P2 requests 1 unit of R4 which is granted.
→ P3 requests 2 units of R1.
Now Available resources are,
At t=3,
→ P1 requests 2 units of R1 which cannot be granted, and will wait for other processes to release.
Available resources are,
At t=4,
→ P2 requests 1 unit of R1, which is granted.
Available resources are
At t=5,
→ P3 releases 2 units of R1.
Now Available resources are,
→ Now P1 is waiting for R1, so now P1 will be granted 2 units of R1.
Now Available resources are,
→ Now P1 releases 1 unit of R2 and 1 unit of R1.
Now Available resources are
At t=6,
→ Now P2 releases 1 unit of R3.
Now available resources are,
At t=7,
→ P3 requests 1 unit of R2, which is granted.
→ P1 releases 1 unit of R3.
Now Available resources are,
At t=8,
→ P2 fnishes and releases remaining resources. So now Available resources,
→ P3 requests 1 unit of R3 which is granted.
Now Available resources are,
→ P1 requests 2 units of R4 which cannot be granted, so it will wait for other process to release them.
At t=9,
→ P3 finishes, and releases rest of the resources.
Now Available resources are
→ Now, P1 can be granted with resources 2 units of R4 for which it was waiting for.
Now Available resources are,
At t=10,
→ P1 finishes its execution.
So, finally we can conclude that all processes will finish without any deadlock.
Question 31 
Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence:
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?
95 ms  
119 ms  
233 ms  
276 ms 
4, 34, 10,7, 19, 73, 2, 15, 6, 20
Arrange the sequence in order
2, 4, 6, 10, 15, 19, 20, 34, 73
⇒ 1 ms to move from one cylinder to adjacent one
⇒ (16*1)+(14*1)+(1*1)+(4*1)+(5*1)+(3*1)+(1*1)+(2*1)+(2*1)+(71*1)
⇒ 16+14+1+4+5+3+1+2+2+71
⇒ 119 ms
Question 32 
In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state:
Now consider the following statements:
 I. If a process makes a transition D, it would result in another process making transition A immediately.
II. A process P2 in blocked state can make transition E while another process P1 is in running state.
III. The OS uses preemptive scheduling.
IV. The OS uses nonpreemptive scheduling.
Which of the above statements are TRUE?
I and II  
I and III
 
II and III  
II and IV 
Statement II is true, a process can move to ready state when I/O completes irrespective of other process being in running state or not.
Statement III is true, the transition C, represents preemptive scheduling.
Statement IV is false, because it is preemptive scheduling.
Correct Answer is OptionC (II & III are true).
Question 33 
The enter_CS() and leave_CS() functions to implement critical section of a process are realized using testandset instruction as follows:
void enter_CS(X) { while testandset(X) ; } void leave_CS(X) { X = 0; }
In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements:
 I. The above solution to CS problem is deadlockfree.
II. The solution is starvation free.
III. The processes enter CS in FIFO order.
IV More than one process can enter CS at the same time.
Which of the above statements is TRUE?
I only  
I and II  
II and III  
IV only 
It is not using any queue to avoid starvation and there is no use of FIFO.
In CS, only one process can enter.
So, Answer is option A.
Question 34 
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because
It reduces the memory access time to read or write a memory location.
 
It helps to reduce the size of page table needed to implement the virtual address space of a process.
 
It is required by the translation lookaside buffer.  
It helps to reduce the number of page faults in page replacement algorithms. 
Question 35 
The running time of an algorithm is represented by the following recurrence relation:
Which one of the following represents the time complexity of the algorithm?
θ(n)  
θ(n log n)  
θ(n^{2})  
θ(n^{2}log n) 
The recurrence relation is T(n) = T(n/3) + cn
Here a=1 , b=3, k=1, p=0.
So, ak and p>=0. So, it comes under case 3.
Therefore T(n) = θ(n^{k}(log^{p}n)) => θ(n^{1}(log^{0} n)) => θ(n)
Question 36 
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
They are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k)=k mod 10 & linear probing is used.
12 % 10 = 2
18 % 10 = 8
13 % 10 = 3
2 % 10 = 2 (Index 4 is empty)
3 % 10 = 3 (Index 5 is empty)
23 % 10 = 3 (Index 6 is empty)
5 % 10 = 5 (Index 7 is empty)
15 % 10 = 5 (Index 9 is empty)
Hence Option C is correct.
A & B doesn’t include all the keys & option D is similar to chaining. So, will go with C.
Question 37 
What is the maximum height of any AVLtree with 7 nodes? Assume that the height of a tree with a single node is 0.
2  
3  
4  
5 
2^{h}1 = 7
∴ h=3
Question 38 
Consider the following graph
Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?
(b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
 
(b,e)(e,f)(a,c)(f,g)(b,c)(c,d)  
(b,e)(a,c)(e,f)(b,c)(f,g)(c,d)  
(b,e)(e,f)(b,c)(a,c)(f,g)(c,d) 
1. It follows like forest structure(Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
As per the options below Option A,B,C, are following correct order but Option D is violating Kruskal’s procedure. The edge between ac of weight 4 comes after bc of weight 3.
Question 39 
In quick sort, for sorting n elements, the (n/4)^{th} smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
θ(n)  
θ(n log n)  
θ(n^{2})  
θ(n^{2} log n) 
n→n/(4/3)→n/(4/3)^{2}→n/(4/3)^{3}n/(4/3)^{k}=1
n/(4/3)^{k} = 1
⇒n=(4/3)^{k} ⇒ k = log_{4/3}n [k=no. of levels]
In each level workdone = Cn
So, total workdone = Cn⋅log_{4/3}n = (nlog_{4/3}n)
Question 40 
Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:
 L1 = {a^{m}b^{m}ca^{n}b^{n}  m,n ≥ 0 }
L2 = {a^{i}b^{j}c^{k}  i,j,k ≥ 0 }
Then L is
Not recursive  
Regular  
Context free but not regular  
Recursively enumerable but not context free 
Clearly, L_{1} ∩ L_{2} is {a^{x}b^{x}  x ≥0}, which is CFL but not regular.
Question 41 
The above DFA accepts the set of all strings over {0,1} that
begin either with 0 or 1  
end with 0
 
end with 00  
contain the substring 00 
Question 42 
Which of the following statements are TRUE?

I.There exist parsing algorithms for some programming languages whose complexities are less than θ(n^{3}).
II.A programming language which allows recursion can be implemented with static storage.
III.No Lattributed definition can be evaluated in the framework of bottomup parsing.
IV.Code improving transformations can be performed at both source language and intermediate code level.
I and II
 
I and IV  
III and IV  
I, III and IV 
Statement I is true, as the bottom up and top down parser take O(n) time to parse the string , i.e. only one scan of input is required.
Statement IV is true,Code improving transformations can be performed at both source language and intermediate code level. For example implicit type casting is also a kind of code improvement which is done during semantic analysis phase and intermediate code optimization is a topic itself which uses various techniques to improve the code such as loop unrolling, loop invariant.
Question 43 
Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1 and T2 as given below:
 T1 = R1[X] W1[X] W1[Y]
T2 = R2[X] R2[Y] W2[Y]
S1 = R1[X] R2[X] R2[Y] W1[X] W1[Y] W2[Y]
S2 = R1[X] R2[X] R2[Y] W1[X] W2[Y] W1[Y]
S3 = R1[X] W1[X] R2[X] W1[Y] R2[Y] W2[Y]
S1 = R1[X] R2[Y]R2[X]W1[X] W1[Y] W2[Y]
Which of the above schedules are conflictserializable?
S_{1} and S_{2}  
S_{2} and S_{3}  
S_{3} only  
S_{4} only 
Dependency graph is,
So, there is no cycle.
Schedule S3,
Dependency graph is,
S_{4} also has a cycle T_{1}→T_{2} and T_{2}→T_{1}.
So, S_{2} and S_{3} are conflict serializable.
Question 44 
The following key values are inserted into a B+  tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The B^{+}tree is initially
10, 3, 6, 8, 4, 2, 1
The maximum number of times leaf nodes would get split up as a result of these insertions is
2  
3  
4  
5 
Insert 3:
Insert 6:
Insert 4:
Insert 2:
Insert 1:
So, total splits are 3.
Question 45 
Let R and S be relational schemes such that R={a,b,c} and S={c}. Now consider the following queries on the database:
I. π_{RS}(r)π_{RS}(π_{RS}(r)×sπ_{RS,S}(r)) II. {tt∈ π_{RS}(r) ∧ ∀u ∈ s(∃v ∈ r(u = v[s] ∧ t = v[R  S]))} III. {tt∈ π_{RS}(r) ∧ ∀v ∈ r(∃u ∈ s(u = v[s] ∧ t = v[R  S]))} IV. Select R.a, R.b from R, S where R.c = S.c
Which of the above queries are equivalent?
I and II  
I and III  
II and IV  
III and IV 
S={c}
I. π_{RS}(r)π_{RS}(π_{RS}(r)×sπ_{RS,S(r)) It looks like Division operator. Since a division operator in E(A,B)/ P(B) will be equal to Now replacing A=RS P=r B=S E=r we will get, equivalent to I ∴ It is equivalent to division operator. ⇒ r(RS,S)/r(S) This logical statement means that ① Select t(RS) from r such that ② for all tuples U in S, ③ there exists a tuple V in r, such that ④ U=V[S] & t=V[RS] A(x,y) & B(y) A/B = {(x)  ∃(x,y)∈A(y)∈B} which means that A/B contains all x tuples, such that for every tuple in B, there is an xy tuple in A. So, this is just equivalent to I. This logical statement means that ① Select t(RS) from r such that ② for all tuples V in r, ③ there exists a tuple U in r, such that ④ U=V[S] & t=V[RS] ⇒ Select (RS) values from r, where the S value is in (r/r), which will be true only if S in r is a foreign key referring to S is r. IV. Select R.a, R.b From R, S Where R.c = S.c This selects (a,b) from all tuples from r which has an equivalent value in S.}
Question 46 
In the RSA public key cryptosystem, the private and public keys are (e, n) and (d, n) respectively, where n = p*q and p and q are large primes. Besides, n is public and p and q are private. Let M be an integer such that 0 < M < n and f(n) = (p 1)(q1). Now consider the following equations.
I. M’= M^{e} mod n M = (M’)^{d} mod n II. ed ≡ 1 mod n III. ed ≡ 1 mod f(n) IV. M’= M^{e} mod f(n) M = (M’)^{d} mod f(n)
Which of the above equations correctly represent RSA cryptosystem?
I and II  
I and III  
II and IV  
III and IV 
1. Generate randomly two “large” primes p and q.
2. Compute n=pq and ∅=(p1)(q1).
3. Choose a number e so that
gcd(e,∅)=1
4. Find the multiplicative inverse of e modulo ∅, i.e., find d so that
ed≡1 (mod ∅)
This can be done efficiently using Euclid’s Extended Algorithm.
The encryption public key is K_{E}=(n,e) and the decryption private key is K_{D}=(n,d).
The encryption function is
E(M)=M^{e} mod n
The decryption function is
D(M)=M^{d} mod n
Question 47 
While opening a TCP connection, the initial sequence number is to be derived using a timeofday (ToD) clock that keeps running even when the host is down. The low order 32 bits of the counter of the ToD clock is to be used for the initial sequence numbers. The clock counter increments once per millisecond. The maximum packet lifetime is given to be
Which one of the choices given below is closest to the minimum permissible rate at which sequence numbers used for packets of a connection can increase?
0.015/s  
0.064/s  
0.135/s  
0.327/s 
The maximum packet lifetime is given is given 64s.
Maximum data rate possible(bandwidth) to avoid the wraparound = 2^{32}/64 = 2^{26} Byte/sec.
The clock counter increments once per milliseconds = That means when then counter increments next possible sequence number is generated. The packet lifetime is 64 seconds and after this 64 seconds next sequence number is come. So that means in this 64 seconds only 1 sequence number is generated.
Hence the minimum rate is = 1/64 = 0.015/sec.
Question 48 
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?
G(x) contains more than two terms  
G(x) does not divide 1+x^{k}, for any k not exceeding the frame length  
1+x is a factor of G(x)  
G(x) has an odd number of terms 
Question 49 
Which of the following statements are TRUE?

I. The context diagram should depict the system as a single bubble.
II. External entities should be identified clearly at all levels of DFDs.
III. Control information should not be represented in a DFD.
IV. A data store can be connected either to another data store or to an external entity.
II and III  
II and III  
I and III  
I, II and III 
Question 50 
Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE?
 I. The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph.
II. The cyclomatic complexity of a module is the number of decisions in the module plus one, where a decision is effectively any conditional statement in the module.
III. The cyclomatic complexity can also be used as a number of linearly independent paths that should be tested during path coverage testing.
I and II  
II and III  
I and III  
I, II and III 
Question 51 
A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple
The address <400, 16, 29> corresponds to sector number:
505035  
505036  
505037  
505038 
To reach a cylinder numbered n, we need to cross cylinders numbered from 0 to n1.
To reach cylinder numbered 400 (401^{th} cylinder) we need to skip cylinders numbered from 0 to 399, (from cylinder number 0 to 399 there are total 400 cylinders).
Each cylinder consists of 10 plates with 2 recording surfaces and 63 sectors per track.
So total number of tracks to be crossed to reach cylinder numbered 400 = 400 * (10*2) * 63 = 504,000 sectors.
Then, to reach the 16th surface of the cylinder numbered 400, we need to skip another 16*63 = 1,008 sectors.
Finally, to find the 29 sector, we need to move another 29 sectors.
In total, we moved 504,000 + 1,008 + 29 = 505,037 sectors.
Hence, option C is the answer.
Question 52 
A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple
The address of the 1039^{th} sector is
〈0, 15, 31〉
 
〈0, 16, 30〉  
〈0, 16, 31〉  
〈0, 17, 31〉 
From the given options we can calculate the sector numbers as
Option A  15*63+31 = 976
Option B  16*63+30 = 1038
Option C  16*63+31 = 1039
Option D  17*63+31 = 1102
Hence Option C is the answer.
Question 53 
A subsequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0.
We wish to find the length of the longest common subsequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:
l(i,j) = 0, if either i=0 or j=0 = expr1, if i,j>0 and X[i1]=Y[j1] = expr2, if i,j>0 and X[i1]!=Y[j1]
Which one of the following options is correct?
expr1 ≡ l(i1, j) + 1  
expr1 ≡ l(i, j1)  
expr2 ≡ max(l(i1, j), l(i, j1))  
expr2 ≡ max(l(i1,j1), l(i,j)) 
Question 54 
A subsequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0.
The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i,j] = l(i,j).
Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?
All elements L should be initialized to 0 for the values of l(i,j) to be properly computed.  
The values of l(i,j) may be computed in a row major order or column major order of L(M,N).  
The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N).  
L[p,q] needs to be computed before L[r,s] if either p 
Question 55 
Consider the following relational schema:
Suppliers(sid:integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real)
Consider the following relational query on the above database:
SELECT S.sname FROM Suppliers S WHERE S.sid NOT IN (SELECT C.sid FROM Catalog C WHERE C.pid NOT IN (SELECT P.pid FROM Parts P WHERE P.color <> 'blue'))
Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?
Find the names of all suppliers who have supplied a nonblue part.  
Find the names of all suppliers who have not supplied a nonblue part.  
Find the names of all suppliers who have supplied only blue parts.  
Find the names of all suppliers who have not supplied only blue parts. 
If we execute the given query the output will be S3 and S4 i.e., names of all suppliers who didn’t supply blue parts which is option (A).
Option (D) says names of suppliers who didn’t supply only blue parts that means, supplier should supply all other parts for sure and shouldn’t supply blue part.
Question 56 
Consider the following relational schema:
Suppliers(sid:integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real)
Assume that, in the suppliers relation above, each supplier and each street within a city has a unique name, and (sname, city) forms a candidate key. No other functional dependencies are implied other than those implied by primary and candidate keys. Which one of the following is TRUE about the above schema??
The schema is in BCNF  
The schema is in 3NF but not in BCNF  
The schema is in 2NF but not in 3NF  
The schema is not in 2NF 
(Sid, Street) → Sname
As Sid is a primary key, then
(Sid, Street) will be super key.
Hence, it is in BCNF.
Question 57 
Frames of 1000 bits are sent over a 10^{6} bps duplex link between two hosts. The propagation time is 25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).
What is the minimum number of bits (l) that will be required to represent the sequence numbers distinctly? Assume that no time gap needs to be given between transmission of two frames.
I = 2  
I = 3  
I = 4  
I = 5 
Maximum number of frames that can be transmit to maximally pack them is = (T_{t}+2T_{p})/T_{x} = (25+1)/1 = 26 which is window size
Minimum sequence numbers required = 26
Minimum number of bits required for sequence number is 5.
Question 58 
Frames of 1000 bits are sent over a 10^{6} bps duplex link between two hosts. The propagation time is 25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).
Suppose that the sliding window protocol is used with the sender window size of 2^{l}, where l is the number of bits identified in the earlier part and acknowledgements are always piggy backed. After sending 2^{l} frames, what is the minimum time the sender will have to wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time.)
16ms  
18ms  
20ms  
22ms 
From above diagram we can say that Total RTT will be
1ms (transmitting time for first frame)
+ 25ms (propagation delay from S to R)
+ 1ms (transmitting time for piggybacked ACK)
+ 25ms (propagation delay from R to S)
= 52 ms
Also total time for sender needed to transmit 32 frames (2^{2} = 2^{5} = 32) is 32×1ms = 32ms
So sender has to wait for,
(52  32)ms
= 20ms
Question 59 
Consider a binary maxheap implemented using an array.
Which one of the following array represents a binary maxheap?
{25,12,16,13,10,8,14}  
{25,14,13,16,10,8,12}  
{25,14,16,13,10,8,12}  
{25,14,12,13,10,8,16} 
Violating a max heap property.
OptionB:
Violating a max heap property.
OptionC:
Question 60 
Consider a binary maxheap implemented using an array.
What is the content of the array after two delete operations on the correct answer to the previous question?
{14,13,12,10,8}  
{14,12,13,8,10}  
{14,13,8,12,10}  
{14,13,12,8,10} 
Step 1: Delete 25
Step 2:
Step 3: Delete 16
Step 4:
Step 5:
∴ Binary array elements: 14, 13, 12, 8, 10.