GATE 2007IT
Question 1 
Suppose there are two coins. The first coin gives heads with probability 5/8 when tossed, while the second coin gives heads with probability 1/4. One of the two coins is picked up at random with equal probability and tossed. What is the probability of obtaining heads ?
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 2 
Let A be the What is the maximum value of x^{T}Ax where the maximum is taken over all x that are the unit eigenvectors of A?
5  
5+√5/2  
3  
5√5/2 
Question 3 
Consider a weighted undirected graph with positive edge weights and let uv be an edge in the graph. It is known that the shortest path from the source vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which one of the following statements is always true?
weight (u, v) < 12  
weight (u, v) ≤ 12  
weight (u, v) > 12  
weight (u, v) ≥ 12 
weight (u,v) ≥ 12
Lets check other options,
A) If the weight (u,v) < 12
Minimum weight of (s,v)
= weight of (s,v) + weight of (u,v)
= 53 + (<12)
= less than 65, which is not possible because shortest path from s to v has weight 65.
Similarly, we can check for option (B) and (C).
Question 4 
In the Spiral model of software development, the primary determinant in selecting activities in each iteration is
Iteration size  
Cost  
Adopted process such as Rational Unified Process or Extreme Programming  
Risk 
Question 5 
Which of the following systems is a most likely candidate example of a pipe and filter architecture ?
Expert system  
DB repository  
Aircraft flight controller  
Signal processing 
Question 6 
A processor takes 12 cycles to complete an instruction I. The corresponding pipelined processor uses 6 stages with the execution times of 3, 2, 5, 4, 6 and 2 cycles respectively. What is the asymptotic speedup assuming that a very large number of instructions are to be executed?
1.83  
2  
3  
6 
For a nonpipelined processor each instruction takes 12 cycles.
So for n instructions total execution time be 12 × n = 12n
For a pipelined processor each instruction takes
max (3, 2, 5, 4, 6, 2) = 6
So for n instructions total execution time be,
(1×6 + (n1) × 1) × 6
= (6 + n  1) × 6
= (5 + n) × 6
= 30 + 6n
∴ Speedup = time without pipeline/time with pipeline = 12n/30+6n
So, if n is very large,
Question 7 
Which of the following input sequences for a crosscoupled RS flipflop realized with two NAND gates may lead to an oscillation?
11, 00  
01, 10  
10, 01  
00, 11 
So, 00 input cause indeterminate state which may lead to oscillation.
Question 8 
The following circuit implements a twoinput AND gate using two 21 multiplexers. What are the values of X_{1}, X_{2}, X_{3} ?
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 
Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?
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 
Processes P1 and P2 use critical_flag in the following routine to achieve mutual exclusion. Assume that critical_flag is initialized to FALSE in the main program.
get_exclusive_access ( ) { if (critical _flag == FALSE) { critical_flag = TRUE ; critical_region () ; critical_flag = FALSE; } }
Consider the following statements. i. It is possible for both P1 and P2 to access critical_region concurrently. ii. This may lead to a deadlock.
Which of the following holds?
(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 
Let a memory have four free blocks of sizes 4k, 8k, 20k, 2k. These blocks are allocated following the bestfit strategy. The allocation requests are stored in a queue as shown below.
The time at which the request for J_{7} will be completed will be
16  
19  
20  
37 
At t = 8
At t = 10
At t = 11
J_{7} can be finished at t = 19.
Question 12 
The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 bytes per page is
0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0410.Suppose that the memory can store only one page and if x is the address which causes a page fault then the bytes from addresses x to x + 99 are loaded on to the memory. How many page faults will occur?
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 
Consider the following statements about the timeout value used in TCP.
(i) The timeout value is set to the RTT (Round Trip Time) measured during TCP connection establishment for the entire duration of the connection.
(ii) Appropriate RTT estimation algorithm is used to set the timeout value of a TCP connection.
(iii) Timeout value is set to twice the propagation delay from the sender to the receiver.
Which of the following choices hold?
(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 
Consider the following two statements:
(i) A hash function (these are often used for computing digital signatures) is an injective function.
(ii) An encryption technique such as DES performs a permutation on the elements of its input alphabet.
Which one of the following options is valid for the above two statements?
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 
The minimum positive integer p such that 3^{p} modulo 17 = 1 is
5  
8  
12  
16 
a^{p1 mod p = 1 Here, p = 17 So, p1 = 16 is the answer.}
Question 17 
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute b^{n} mod m, 0≤b, n≤m?
O(log n)  
O(√n)  
O(n/log n)  
O(n) 
C_{1} = b^{n/2} × b^{n/2}
C_{2} = b^{n/4} × b^{n/4}
C_{3} = b^{n/8} × b^{n/8}
⋮
C_{k} = b^{2} × b^{2}
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 19 
Given below are HTML lines,
With reference to the HTML lines given above, consider the following statements.
(i) Clicking on the point <80, 75> does not have any effect.
(ii) The web browser can identify the area applicable to the mouseclick within the image and the subsequent action to be taken without additional responses from the web server.
(iii) The dots in the cgibin URL will be resolved by the web browser before it is sent to the web server.
(iv) The "fd.html" request when sent to the web server will result in a GET request.
Exactly how many of the statements given above are correct?
0  
1  
2  
3 
Question 20 
Consider the XML document fragment given below:
Consider the XPath expression: *[not (self)::TOC]
What would be the result of the given XPath expression when the current node is Book?
The Title and Content elements  
The Content and TOC elements  
The Title and TOC elements  
The Title, Content and TOC elements

Question 21 
Which one of these firstorder logic formula is valid?
∀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 (️×)