Gate 2007IT
Question 1 
7/8  
1/2  
7/16  
5/32 
The probability of obtaining heads
= (1/2)(5/8) + (1/2)(1/4)
= (5/16) + (1/8)
= 7/16
Question 3 
weight (u, v) < 12  
weight (u, v) ≤ 12  
weight (u, v) > 12  
weight (u, v) ≥ 12 
If the weight (u, v) < 12 then
min. weight of (s, v) = weight of (s, u) + weight of (u, v)
= 53 + (<12)
= less than 65
Question 4 
Iteration size  
Cost  
Adopted process such as Rational Unified Process or Extreme Programming  
Risk 
Question 5 
Expert system  
DB repository  
Aircraft flight controller  
Signal processing 
Question 6 
1.83  
2  
3  
6 
→ For a pipelined processor we take
max {3, 2, 5, 4, 6, 2} = 6 cycles
→ For 6 cycles we need = 6 × 6 + (n1) × 6
→ For large no. of instructions we need to consider
Question 7 
11, 00  
01, 10  
10, 01  
00, 11 
So, 00 input cause indeterminate state which may lead to oscillation.
Question 8 
X1 = b, X2 = 0, X3 = a  
X1 = b, X2 = 1, X3 = b  
X1 = a, X2 = b, X3 = 1  
X1 = a, X2 = 0, X3 = b

If we put
X1 = b
X2 = 0
X3 = a
Then we get,
F = ab
Question 9 
L (D) ⊂ L (G)  
L (D) ⊃ L (G)  
L (D) = L (G)  
L (D) is empty 
For example, by converting NFA to DFA language will not be changed.
Question 10 
(i) is false and (ii) is true  
Both (i) and (ii) are false  
(i) is true and (ii) is false  
Both (i) and (ii) are true 
Question 11 
16  
19  
20  
37 
At t = 8
At t = 10
At t = 11
J_{7} can be finished at t = 19.
Question 12 
0  
4  
7  
8 
0200  Page fault, address till 299 in memory
0430  Page fault, address till 529 in memory
0499  No page fault
0510  No page fault
0530  Page fault, address till 629 in memory
0560  No page fault.
0120  Page fault, address till 219 in memory
0220  Page fault, address till 319 in memory
0240  No page fault
0260  No page fault
0320  Page fault, address till 419 in memory
0410  No page fault
So, total page faults = 7.
Question 13 
(i) is false, but (ii) and (iii) are true  
(i) and (iii) are false, but (ii) is title  
(i) and (ii) are false, but (iii) is true  
(i), (ii) and (iii) are false 
The timeout value cannot be fixed for entire duration as it will turn timer to static timer, we need dynamic timer for timeout.
StatementII: It is True.
Basic algorithm, Jacobson's algorithm, Karl's modification; these three algorithms are to be appropriate to RTT estimation algorithm used to set timeout value dynamically.
StatementIII: It is False.
Because timeout value is set to twice the propagation delay in data link layer where hop to hop distance is known, not in TCP layer.
Question 14 
Consider a TCP connection in a state where there are no outstanding ACKs. The sender sends two segments back to back. The sequence numbers of the first and second segments are 230 and 290 respectively. The first segment was lost, but the second segment was received correctly by the receiver. Let X be the amount of data carried in the first segment (in bytes), and Y be the ACK number sent by the receiver. The values of X and Y (in that order) are
60 and 290  
230 and 291  
60 and 231  
60 and 230 
Question 15 
Both are false  
Statement (i) is true and the other is false  
Statement (ii) is true and the other is false  
Both are true

ii) It uses the PBox permutation.
StatementI is false, II is true.
Question 16 
5  
8  
12  
16 
a^{p1 mod p = 1 Here, p = 17 So, p1 = 16 is the answer.}
Question 17 
Recurrence relation T(n) = T(n/2) + O(1)
T(n) = O(log n)
Question 18 
A firewall is to be configured to allow hosts in a private network to freely open TCP connections and send packets on open connections. However, it will only allow external hosts to send packets on existing open TCP connections or connections that are being opened (by internal hosts) but not allow them to open TCP connections to hosts in the private network. To achieve this the minimum capability of the firewall should be that of
A combinational circuit  
A finite automaton  
A pushdown automaton with one stack  
A pushdown automaton with two stacks

Turing machine can do everything as the normal computer can do, so firewall can be created by the TM.
Question 20 
The Title and Content elements  
The Content and TOC elements  
The Title and TOC elements  
The Title, Content and TOC elements

Question 21 
∀x(P(x) ⇒ Q(x)) ⇒ (∀xP(x) ⇒ ∀xQ(x))  
∃x(P(x) ∨ Q(x)) ⇒ (∃xP(x) ⇒ ∃xQ(x))  
∃x(P(x) ∧ Q(x)) (∃xP(x) ∧ ∃xQ(x))  
∀x∃y P(x, y) ⇒ ∃y∀x P(x, y)

RHS = if P(x) holds for all x, then Q(x) holds for all x
LHS ⇒ RHS (✔)
RHS ⇒ LHS (️❌)
Question 22 
(iv) only  
(iii) and (iv) only  
(ii), (iii) and (iv) only  
(i), (ii), (iii) and (iv) 
Question 23 
(i) and (iii)  
(ii) and (iv)  
(i) and (iv)  
(iii) and (iv) 
The given condition can be satisfied by
(iii) (145, 265) → 5 ≤ 5, 4 < 6 and 1< 2
(iv) (0, 153) → 0 < 3
Question 24 
d[u] < d[v]  
d[u] < f[v]  
f[u] < f[v]  
f[u] > f[v] 
Option A:
d[u]
d[u]
f[u]
Question 25 
1  
2  
3  
n 
→ If we create a different spanning tree by removing one edge at a time.
→ For cycle required 3 minimum edges. So there is at least 3 spanning trees in such a graph.
Question 26 
Nondecreasing order of t_{i}  
Nonincreasing order of w_{i}  
Nonincreasing order of w_{i}t_{i}  
Noneincreasing order of w_{i}/t_{i} 
So answer is the nonincreasing order of w_{i}/t_{i}.
Question 27 
(i) and (iii)  
(i) and (iv)  
(ii) and (iii)  
(ii) and (iv) 
→ Let n=3, then it is terminated in 2^{nd} iteration.
→ Let n=5, then sequence is 5→14→7→20→10 and it will repeat.
→ Any number with factor 5 and 2 leads to infinite recursion.
So, (iv) is True and (iii) is False.
Question 28 
5  
6  
7  
10 
Probability of collision for each entry = 1/20
After inserting X values then probability becomes 1/2
i.e., (1/20)X = 1/2
X = b
Question 29 
35  
64  
128  
5040 
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35
Question 30 
Leaves the queue Q unchanged  
Reverses the order of the elements in the queue Q  
Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements in the same order  
Empties the queue Q 
Question 31 
9  
8  
7  
6 
Question 32 
15  
25  
30  
150 
push 2
pop 2
pop 5
5 * 2 = 10
push 10
push 3
push 3
push 2
pop 2
pop 3
3 + 2 = 5
push 5
pop 5
pop 3
3 * 5 = 15
push 15
pop 15
pop 10
10 + 15 = 25
push 25
Finally, pop 25 and print it.
Question 33 
Call by value : i = 70, j = 10; Call by reference : i = 60, j = 70  
Call by value : i = 50, j = 60; Call by reference : i = 50, j = 70  
Call by value : i = 10, j = 70; Call by reference : i = 100, j = 60  
Call by value : i = 100, j = 60; Call by reference : i = 10, j = 70 
'i' is a global variable. Then in main( ) a local variable 'j' as integer declared, i.e., j=60 and global varible 'i' is initialized to 50 by i=50.
Now procedure f called and values of 'i' and 'j' are passed to it, i.e., in f(i, j)→f(x, y).
Content of memory location of 'i' (here 50) is copied to memory location of x (which is different from i) and content of memory location of 'j' (here 60) is copied to memory location of y. Then in f(x, y) i=100 changes the global i to 100, x=10 changes the local x from 50 to 10 and y=y+i means y=60+100=160. Now, when return back to main, i & j will be 100 & 60 respectively.
Call by reference:
Now procedure f called and passed reference of i and j to it, i.e., in f(i,j)→f(x,y). x and y are pointing to same memory location of i and j respectively. So i=100 changes the global i to 100 and x=10 means as well as global i=10 (as the i being passed is the global variable and x and i share the same address).
y=y+i means y=60+10=70 and this changes the value of j also to as j and y have the same addresses. Now when return to main, i and j will be 10 and 70.
Question 34 
x = 10, y = 10  
x = 20, y = 10  
x = 10, y = 20  
x = 20, y = 20

Question 35 
Early, late, decrease, increase  
Late, early, increase, decrease  
Late, early, decrease, increase  
Early, late, increase, decrease 
Dynamic scoping requires late binding (during execution time).
Late binding decreases efficiency as this binding needs to be done at run time.
Question 36 
The floating point unit of a processor using a design D takes 2t cycles compared to t cycles taken by the fixed point unit. There are two more design suggestions D1 and D2. D1 uses 30% more cycles for fixed point unit but 30% less cycles for floating point unit as compared to design D. D2 uses 40% less cycles for fixed point unit but 10% more cycles for floating point unit as compared to design D. For a given program which has 80% fixed point operations and 20% floating point operations, which of the following ordering reflects the relative performances of three designs? (Di > Dj denotes that Di is faster than Dj)
D1 > D > D2  
D2 > D > D1  
D > D2 > D1  
D > D1 > D2 
D = 0.8 × t + 0.2 × 2t = 1.2t
D1 = 0.8 × 1.3t + 0.2 × 0.7 × 2t = 1.32t
D2 = 0.8 × 0.6t + 0.2 × 1.1 × 2t = 0.92t
⇒ D2 > D > D1
Question 37 
3  
18  
20  
30 
So memory block 18 is not in the cache.
Question 38 
1  
a’ + b’ + c’ + d’  
a’ + b + c’ + d’  
a’ + b’ + c + d’ 
= ((ab)'c)' + ((a'c)'d)' + ((bc)'d)' + (ad)'
= ab + c' + a'c + d' + bc + d' + a' + d'
= ab + c' + a'c + bc + a' + d'
= ab + c' + bc + a' + d'
= b + c' + bc + a' + d'
= a' + b + c' + d'
Question 39 
(i) and (iii)  
(i) and (iv)  
(ii) and (iii)  
(ii) and (iv)  
Only (i) 
(ii) Is false. Because R2 gets the correct data in both LHS and RHS, but Loc is not updated in RHS.
(iii) Is false. Because R2 is writing last in LHS, but not in RHS.
(iv) Is true. The first write to Loc in LHS is useless as it is overwritten by the next write.
Question 41 
7  
10  
13  
14 
If an instruction is in execution phase then any other instructions cannot be in the execution phase. So, atleast 7 clock cycles will be taken.
Now, it is given that between two instructions latency or delay should be there based on their operation.
0  
1  
2  
3 
The no. of bits that can be corrected is
Question 44 
300.5 ms  
255.5 ms  
255.0 ms  
300.0 ms 
For Avg. seek time:
Given that, time to move between successive tracks is 1ms.
Time to move from track1 to track1 = 0ms
Time to move from track1 to track2 = 1ms
Time to move from track1 to track3 = 2ms
⋮ Time to move from track1 to track500 = 499ms
∴ Avg. seek time = 0+1+2+...+499/500 = 249.5ms
Avg. rotational delay:
600 rotations in 60sec.
One rotation takes 60/600 s = 100ms ∴ Avg. rotational delay = 100/2 = 50ms
Data transfer time:
In one rotation, we can read data on one complete track
= 100 × 500 = 50,000B data is read in one complete rotation
One complete rotation takes 100ms.
100ms → 50,000B
250B → 100/50000 × 250 = 0.5ms
∴ Avg. time to transfer = 249.5 × 50 + 0.5 = 300ms
Question 45 
0000  
0111  
1111  
None of these 
Since the problem is in the link T which is connected as input to NOR gate. So to check link T we have to make the output dependent on T by deactivating link M. So to deactivate link M, the output at M should be 0, as link M is input to NOR gate. So, to output at M as 0,
X1 = 1
X2 = 1
X3 = 1
X4 = 0
∴ None of the given option is correct.
Question 46 
G1 : No y appears before any x G2 : Every x is followed by at least one y  
G1 : No y appears before any x G2 : No x appears before any y  
G1 : No y appears after any x G2 : Every x is followed by at least one y  
G1 : No y appears after any x G2 : Every y is followed by at least one x 
(x + z)* + (x + z)* y(y + z)*
Regular expression for G2:
(y + z + xy)*
Question 47 
All strings of x and y  
All strings of x and y which have either even number of x and even number of y or odd number or x and odd number of y  
All strings of x and y which have equal number of x and y  
All strings of x and y with either even number of x and odd number of y or odd number of x and even number of y 
Question 48 
(i), (ii), and (iii)  
(ii), (v), and (vi)  
(ii), (iii), and (iv)  
(i), (iii), and (iv) 
S → xB
S → xxBB
S → xxyB
S → xxyyS
S → xxyyxB
S → xxyyxy
(iii) xyxy
S → xB
S → xyS
S → xyxB
S → xyxy
(iv) yxxy
S → yA
S → yxS
S → yxxB
S → yxxy
Question 49 
G_{1} is contextfree but not regular and G_{2} is regular  
G_{2} is contextfree but not regular and G_{1} is regular  
Both G_{1} and G_{2} are regular  
Both G_{1} and G_{2} are contextfree but neither of them is regular 
Similarly, in right linear grammar, nonterminal appears at the right most position.
Here we can write a right linear grammar for G_{1} as
S → w(E
E → id)S
S → o
(wwhile, oother)
So, L(G_{1}) is regular.
Now for G_{2} also we can write a right linear grammar:
S → w(E
E → id)S
E → id+E
E → id*E
S → o
making its language regular.
So, both G_{1} and G_{2} have an equivalent regular grammar. But given in the question both these grammars are neither right linear nor left linear and hence not a regular grammar. So, (D) must be the answer.
Question 50 
Question 51 
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 54 
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 56 
signal (mutex), wait (wrt), signal (wrt), wait (mutex)  
signal (wrt), signal (mutex), wait (mutex), wait (wrt)  
wait (wrt), signal (mutex), wait (mutex), signal (wrt)  
signal (mutex), wait (mutex), signal (mutex), wait (mutex)

S2: After readcount has been updated, UP on mutex.
S3: DOWN on mutex to update readcount.
S4: If readcount is zero, i.e., no reader is reading, UP on wrt to allow some writer to write.
Question 57 
In a multiuser operating system on an average, 20 requests are made to use a particular resource per hour. The arrival of requests follows a Poisson distribution. The probability that either one, three or five requests are made in 45 minutes is given by :
6.9 × 10^{6} × e^{20}  
1.02 × 10^{6} × e^{20}  
6.9 × 10^{3} × e^{20}  
1.02 × 10^{3} × e^{20} 
So, λ=15
Question 58 
A demand paging system takes 100 time units to service a page fault and 300 time units to replace a dirty page. Memory access time is 1 time unit. The probability of a page fault is p. In case of a page fault, the probability of page being dirty is also p. It is observed that the average access time is 3 time units. Then the value of p is
0.194  
0.233  
0.514  
0.981  
0.0194 
(if the page is not dirty)
Page fault service time = 300
(if there is dirty page)
Probability of page fault = P
Probability pf page being dirty = P
So, total page fault service time
= P(300) + (1  P)100
= 300P + 100  100P
= 300P + 100
Now given,
Effective average memory access time = 3
So,
3 = m + P × total page fault service time
= 1 + P(200P + 100)
= 1+ 200P^{2} + 100P
⇒ 200P^{2} + 100P  2 = 0
⇒ P = 0.0194
Question 60 
Using distance vector routing protocol, F→D→B yeilds distance as 20 which eliminates option (B) and (D).
Question 61 
1000010111 and Differential Manchester respectively  
0111101000 and Differential Manchester respectively  
1000010111 and Integral Manchester respectively  
0111101000 and Integral Manchester respectively

As per IEEE (B) is correct.
As per GE Thomas (A) is correct.
As we usually follow IEEE thus (B) is correct.
Question 62 
Let us consider a statistical time division multiplexing of packets. The number of sources is 10. In a time unit, a source transmits a packet of 1000 bits. The number of sources sending data for the first 20 time units is 6, 9, 3, 7, 2, 2, 2, 3, 4, 6, 1, 10, 7, 5, 8, 3, 6, 2, 9, 5 respectively. The output capacity of multiplexer is 5000 bits per time unit. Then the average number of backlogged of packets per time unit during the given period is
5  
4.45  
3.45  
0 
If the no. of packets transmitted is larger than 5 then the extra packets are backlogged. This means gets added to the next number and further backlog is calculated.
Average no. of backlogged packets = 89/20 = 4.45
Question 63 
A group of 15 routers are interconnected in a centralized complete binary tree with a router at each tree node. Router j communicates with router j by sending a message to the root of the tree. The root then sends the message back down to router j. The mean number of hops per message, assuming all possible router pairs are equally likely is
3  
4.26  
4.53  
5.26 
Message goes up from sender to root,
Average hops message goes to root
= (3×8) + (2×4) + (1×2) + (0×1)/15
= 2.267
Here, (3×8) represents 3 hops and 8 routers for bottom most level and so on.
Step 2:
Similarly, average hops when message comes down
= (3×8) + (2×4) + (1×2) + (0×1)/15
= 2.267
So, Total hops = 2×2.267 = 4.53
Question 64 
1 Mbps  
100/11 Mbps  
10 Mbps  
100 Mbps 
Question 65 
Consider a selection of the form σ_{A≤100}(r), where r is a relation with 1000 tuples. Assume that the attribute values for A among the tuples are uniformly distributed in the interval [0, 500]. Which one of the following options is the best estimate of the number of tuples returned by the given selection query ?
50  
100  
150  
200 
Values for A among the tuples are uniformly distributed in the interval [0, 500]. This can be split to 5 mutually exclusive and exhaustive intervals of same width of 100 ([0100], [101200], [201300], [301400], [401500], 0 makes the first interval larger  this must be typ0 in this question) and we can assume all of them have same number of values due to uniform distribution. So no. of tuples with A value in first interval should be,
Total no. of tuples/5 = 1000/5 = 200
Question 66 
i) Exclusive locks should be released after the commit.
ii) No locking can be done after the first unlock.
(A) Wrong because to write x you need Exclusive Lock.
(B) Wrong because violating the 1^{st} requirement.
(C) Correct.
(D) Wrong because violating the 1^{st} requirement.
Question 67 
0  
1  
2  
3 
if A→B then A→→B holds but reverseis not true.
So,
(i) False.
(ii) True.
(iii) False.
(iv) True.
Question 68 
П_{cname} (σ_{bal < 0} (σ_{bcity = “Agra”} branch ⋈ account) ⋈ depositor)  
П_{cname} (σ_{bcity = “Agra”}branch ⋈ (σ_{bal < 0} account ⋈ depositor))  
П_{cname} (σ_{bcity = “Agra”} branch ⋈ σ_{bcity = “Agra” ⋀ bal < 0} account) ⋈ depositor)  
П_{cname} (σ_{bcity = “Agra” ⋀ bal < 0} account ⋈ depositor)) 
Options (C) and (D) are invalid as there is no bcity column in aschema.
Question 69 
IMAP(i), FTP(ii), HTTP(iii), DNS(iv), POP3(v)  
FTP(i), POP3(ii), SMTP(iii), HTTP(iv), IMAP(v)  
POP3(i), SMTP(ii), DNS(iii), IMAP(iv), HTTP(v)  
SMTP(i), HTTP(ii), IMAP(iii), DNS(iv), FTP(v) 
(v) FTP needs two ports, 20 for data and 21 for control.
Hence, only (D) matches.
Question 70 
zdp  
fpq  
qwA  
oze 
10100011 00110111 11101001 10101011
So, in total we have 32 bits. And for base 64we need 6 digits of binary no. to represent one digit of base 64 no.
So lets padd 4 bits on RHS, so that total digits will become 36 and we can separate then as group of 6 digits each.
Now, the longest substring will be from checking option is 'fpq'.
Question 71 
But option (B), (C), (D) accepts aba, which do not contain aa or bb as substring.
Hence, (A) is correct.
Question 72 
(C) It is not accepting 'abb' which is in language.
(D) It is not accepting 'aa' and 'bb' which is in language.
Question 73 
(a(ba)* + b(ab)*)(a + b)^{+}  
(a(ba)* + b(ab)*)*(a + b)*  
(a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)*  
(a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)^{+} 
Having NFA:
Equivalent DFA:
Question 74 
0.545  
0.6  
0.857  
0.961 
Question 75 
0.545  
0.655  
0.9375  
0.961 
Question 76 
Then,
x_{1} = c ⋅ (x_{0})^{2}  2 = 1 ⋅ (1)^{2}  2 = 1
x_{2} = c ⋅ (x_{1})^{2}  2 = 1 ⋅ (1)^{2}  2 = 1
So, the value converges to 1, which is equal to
Exactly, only (B) is answer. As all the term of x converges to 1.
Question 77 
(i) 0nly  
(i) and (ii) only  
(i), (ii) and (iii) only  
(i), (ii), (iii) and (iv) 
From the recurrence we should have c(x_{n})^{2}  x_{n}  2 < 0
For all the above values of c we have above equation as negative.
Question 78 
Hence, option (A) matches.
Question 79 Explanation: Let's check for option (C): a'c' + ad' + abc' + c'd Not equivalent to the Kmap, we get in previous question.
Question 80 Explanation: Draw the line from the first to third point, and look at whether the middle point is above, at or below it. If the middle point is on the line, all slopes are equal. If the middle point is above the line, then the slope from the first to the second point is the highest. If the middle point is below the line, then the slope from the middle point to the second is highest. In any case, you can find a greater slope betweem two adjacent points.
Question 81 Explanation: For gradient to be maximum x_{2}x_{1} should be minimum. So, sort the points (in Θ(n logn) time) according to n coordinate and find the minimum difference between them (in Θ(n) time). ∴ Complexity = Θ(n logn + n) = Θ(n logn)
Question 82 Explanation: Hence, correct option is (B).
Question 83 Explanation: We need two conditions to satisfy: 1) The alternating direction with SSTF policy. 2) Maximize the no. of requests. The first condition can be satisfied by not having two requests in the equal distance from the current location. As shown below, we must not have request located in the circle marked positions. Now to maximize the no. of request we need the requests to be located as compact as possible, which can be done by just placing the request in the next position after the circle marked position in particular direction (the direction in which the head need to move). Now to satisfy the 1^{st} criteria: Seek length sequence for maximum cardinality and alternating head movements: → 1, 3, 7, 15, ... → or, 2^{1}1, 2^{2}1, 2^{3}1, 2^{4}1, ... → We have 2048 tracks so, maximum swing (seek length) can be 2047. → Which corresponds to a seek length of 2^{11}1 in the 11^{th} service.
Question 84 Explanation: It is B^{+} Tree. After inserting K15 we get, Now, we insert K25, which gives So, we see in the final tree only (K20, K25) is present. Hence, 1 (Answer).
Question 85 Explanation: The B^{+} tree in previous question we get was, Now after deleting 50 we get B^{+} tree as Hence, correct statement is only (i) & (ii).
There are 85 questions to complete.
