## GATE 2007-IT

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 non-pipelined 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 + (n-1) × 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 cross-coupled R-S flip-flop 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 two-input AND gate using two 2-1 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 best-fit 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 |

__Statement-I__: It is False.

The timeout value cannot be fixed for entire duration as it will turn timer to static timer, we need dynamic timer for timeout.

__Statement-II__: 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.

__Statement-III__: 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 |

^{st}segment data is from byte number 230 to byte number 289, that is 60 bytes. As 1

^{st}segment is lost, so TCP will send ACK for the next-in-order segment receiver is to be expecting. So, it will be for 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 P-Box permutation.

Statement-I 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

^{p-1 mod p = 1 Here, p = 17 So, p-1 = 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 mouse-click within the image and the subsequent action to be taken without additional responses from the web server.

(iii) The dots in the cgi-bin 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 | |