Indian Institute of Technology Kanpur (IIT-K) 2008 M.E Computer Science Gate - Question Paper

(A) 10000 bits
(B) 10000 bytes
(C) 5000 bits
(D)5000 bytes
72. A channel has a bit rate of four kbps and one-way propagation delay of 20 ms. The channel
uses stop and wait protocol. The transmission time of the acknowledgement frame is
negligible. To get a channel efficiency of at lowest 50°h, the minimum frame size should be
(A) 80 bytes
(B) 80 bits
(C) 160 bytes
(D) 160 bits
73. On a TCP connection, current congestion window size is Congestion Window = four KB. The
window size advertised by the received is Advertise Window = six KB. The last byte sent by the
sender is LastByteSent = 10240 and the last byte acknowledged by the receiver is
LastByteAcked = 8192. The current window size at the sender is:
(A) 2048 bytes
(B) 4096 bytes
(C) 6144 bytes
(D)8192 bytes
74. In a communication network, a packet of length L bits takes link Li with a probability of Pi
or link L2 with a probability of P2. Link Li and L2 have bit fault probability of b1 and b2
respectively. The probability that the packet will be received without fault via either Li or L2
is:
(A) (i_b1)Lp1+(i_b2)Lp2 (B) [i_(b1+b2)P1P2
(C) (1—b1 )L (1 — b2 )L p1p2 (D) i — (bi’-p, + b21- p)
75. In a TDM medium access control bus LAN, every station is assigned 1 time slot per cycle
for transmission. presume that the length of every time slot is the time to transmit 100 bits plus
the end-to-end propagation delay. presume a propagation speed of 2xiO8m/sec. The length of
the LAN is one km with a bandwidth of 10 Mbps. The maximum number of stations that can be
Visit http://groups.yahoo.com/group/OneStopGATE/ for joining the club of GATE Aspirants
www.OneStopGATE.com – GATE Study Material, Forum,
downloads, discussions & more!
allowed in the LAN so that the throughput of every station can be Mbps is:
(A) 3
(B) 5
(C) 10
(D)20
76. A company has a class C network address of 204.204.204.0. It wishes to have three
subnets, 1 with 100 hosts and 2 with 50 hosts every. Which 1 of the subsequent choices
represents a feasible set of subnet address/subnet mask pairs?
(A) 204.204.204.128/255.255.255.192
204.204.204.0/255.255.255.128
204.204.204.64/255.255.255.128
(B) 204.204.204.0/255.255.255.192
204.204.204.192/255.255.255.128
204.204.204.64/255.255.255.128
(C) 204.204.204.128/255.255.255.128
204.204.204.192/255.255.255.192
204.204.204.224/255.255.255.192
(D) 204.204.204.128/255.255.255.128
204.204.204.64/255.255.255.192
204.204.204.0/255.255.255.192
77. presume that “hostl.mydomain.dom” has an IP address of 145.128.16.8. Which of the
subsequent choices would be most improper as a subsequence of steps in performing the
reverse lookup of 145.128.16.8? In the subsequent choices “NS” is an abbreviation of
“nameserver”?
(A) Query a NS for the root domain and then NS for the “dom” domains
(B) Directly query a NS for “dom” and then a NS for “mydomain.dom” domains
(C) Query a NS for in-addr.arpa and then a NS for 128.145.in-addr.arpa domains
(D) Directly query a NS for 145.in-addr.arpa and then a NS for 128.145.in- addr.arpa
domains.
78. Consider the subsequent message M = 1010001101. The cyclic redundancy check (CRC) for
this message using the divisor polynomial x5 + x4 + x2 + one is:
(A) 01110
(B) 01011
(C) 10101
(D)10110
79. Suppose that 2 parties A and B wish to setup a common secret key (D-H key) ranging from
themselves using the Diffie-Hellman key exchange technique. They agree on seven as the modulus
and three as the primitive root. Party A selects two and party B selects five as their respective
secrets. Their D-H key is:
(A) 3
(B) 4
(C) 5
(D)6
80. provided beneath is an excerpt of an xml specification.




10237623786



0024154807

provided beneath are several possible excerpts from “libratry.dtd”. For which excerpt would the
above specification be valid?
(A)




(B)




(C)




(D)




Linked ans Questions: Q.81a to Q85b Carry 2 Marks every.
Statement for Linked ans ques. 81a and 81b:
A disk has eight equidistant tracks. The diameters of the innermost and outermost tracks are 1
cm and eight cm respectively. The innermost track has a storage capacity of 10 MB.
81. (A) What is the total amount of data that can be stored on the disk if it is used with a
drive that rotates it with
(i) Constant Linear Velocity
(ii) Constant Angular Velocity
(A) (i) 80 MB (ii) 2040 MB (B) (i) 2040 MB (ii) 80 MB
(C) (i) 80 MB (ii) 360 MB (D) (i) 360 MB (ii) 80 MB
(B) If the disk has 20 sectors per track and is currently at the end of the fifth sector of the
inner most track and the head can move at a speed of 10 meters/sec and it is rotating at
constant angular velocity of 6000 RPM, how much time will it take to learn one MB contiguous
data starting from the sector four of the outer most track?
(A) 13.5 ms
(B) 10 ms
(C) 9.5 ms
(D)20 ms
Statement for Linked ans ques. 82a and 82b:
A database table Ti has 2000 records and occupies 80 disk blocks. a different table T2 has 400
records and occupies 20 disk blocks. These 2 tables have to be joined as per a specified join
condition that needs to be evaluated for every pair of records from these 2 tables. The
memory buffer space available can hold exactly 1 block of records for Ti and 1 block of
records for T2 simultaneously at any point in time. No index is available on either table.
82. (A) If Nested loop join algorithm is employed to perform the join, with the most
improper option of table to be used in outer loop, the number of block accesses needed for
studying the data are:
(A) 800000
(B) 40080
(C) 32020
(D) 100
(B) If, instead of Nested loop join, Block nested loop join is used, again with the most
improper option of table in the outer loop, the reduction in number of block accesses
needed for studying the data will be:
(A) 0
(B) 30400
(C) 38400
(D)798400
Statement for Linked ans ques. 83a and 83b:
Consider the context-free grammar
E -E+E
E _(E*E)
E - Id
Where E is the starting symbol, the set of terminals is {id,(,+,),*, and the set of
non-terminals is {E}.
83. (A) Which of the subsequent terminal strings has more than 1 parse tree when parsed
according to the above grammar?
(A) id + id + id + id
(B) id + (id* (id * id))
(C) (id * (id*id)) + id
(D) ((id * id + id) * id)
(B) For the terminal string with more than 1 parse tree found as solution to ques.
83a, how many parse trees are possible?
(A) 5
(B) 4
(C) 3
(D)2
Statement for Linked ans ques. 84a and 84b:
A sink in a directed graph is a vertex isuch that there is an edge from every vertex j Ito land
there is no edge from Ito any other vertex. A directed graph G with n vertices is represented
by its adjacency matrix a, where A[ijjl = one if there is an edge directed from vertex I tojand 0
otherwise. The subsequent algorithm determines whether there is a sink in the graph G.
I = 0;
do {
j=i+1;
while((j
if (j
} while (j
flag =1;
for(j = 0 ;j < n ;j + +)
if (j!=i)&&E3) flag =0;
if(flag) printf(”Sink exists”) else printf(”Sink does not exist”);
84. (A) select the accurate expressions for E1 and E2
(A) E1 : A [1111 and E2 : =
(B) (!A[ijjl& &!A[jjij)
(C) E1 : !A[ijjl and E2 :1 =
(D) (A[ijfj !A[jji1)
(B) select the accurate expression for E3
(A) (A[ijjl& &!A[f Ill)
(C) (!A[ijfj !A[jji1)
(B) E1:!A[ijjl and E2:i=j+1;
(D) E1 :A[ijjl and E2 :i=j+1;
Statement for Linked ans ques. 85a and 85b:
Consider a simple graph with unit edge costs. every node in the graph represents a router.
every node maintains a routing table indicating the next hop router to be used to relay a
packet to its destination and the cost of the path to the destination through that router.
Initially, the routing table is empty. The routing table is synchronously updated as follows. In
every updation interval, 3 tasks are performed.
(i) A node determines whether its neighbours in the graph are accessible. If so, it sets the
tentative cost to every accessible neighbour as 1. Otherwise, the cost is set to .
(ii) From every accessible neighbour, it gets the costs to relay to other nodes via that
neighbour (as the next hop)
(iii) every node updates its routing table based on the info received in the previous two
steps by choosing the minimum cost.
85. (A) For the graph provided above, possible routing tables for different nodes after they have
stabilized, are shown in the subsequent choices. Identify the accurate table?
(A) Table for node A (B) Table for node C
A- AA1
BB1 BB1
Ccl C- -
DB3 DD1
EC3 EEl
FC4 FE3
(C) Table for node B (D) Table for node D
A A one A B3
B - - B B1
C C one C C1
D Dl D
E C two E E1
F D two F Fj]
(B) Continuing from the earlier problem, suppose at a few time t, when the costs have
stabilized, node A goes down. The cost from node F to node A at time (t+100)is:
(A) > 100 but finite
(B)
(C) 3
(D) >3 and 100

Earning:   Approval pending.