Gate 2004IT
Question 1 
In a population of N families, 50% of the families have three children, 30% of the families have two children and the remaining families have one child. What is the probability that a randomly picked child belongs to a family with two children?
In that 50% of families having 3 childrens
i.e., 50×3 = 150 (No. of children)
→ Likes that 30% have 2 childrens = 30×2 = 60
→ 20% have 1 children = 20×1 = 20
Probability of choosing a children the family have two children
= 60/(150+60+20) = 60/230 = 6/23
Question 2 
In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 students have taken Computer Organization course; 50 students have taken both Programming Language and Data Structures, 35 students have taken both Data Structures and Computer Organization; 30 students have taken both Data Structures and Computer Organization, 15 students have taken all the three courses.How many students have not taken any of the three courses?
15  
20  
25  
35 
PL = 125
DS = 85
CO = 65
PL & DS = 50
DS & CO = 35
CO & PL = 30
PL & DS & CO = 15
⇒ Not taken any course = 200  (60 +15+15+35+15+15+20)
= 200  175
= 25
Question 3 
(∀x)(∃y)[(a(x, y) ∨ b(x, y)) → c(x, y)]  
(∃x)(∀y)[(a(x, y) ∨ b(x, y)) ∧¬ c(x, y)]  
¬(∀x)(∃y)[(a(x, y) ∧ b(x, y)) → c(x, y)]  
¬(∀x)(∃y)[(a(x, y) ∨ b(x, y)) → c(x, y)] 
Question 4 
R_{1}R_{2} = {(1, 2), (1, 4), (3, 3), (5, 4), (7, 3)}  
R_{1}R_{2} = {(1, 2), (1, 3), (3, 2), (5, 2), (7, 3)}  
R_{1}R_{2} = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)}  
R_{1}R_{2} = {(3, 2), (3, 4), (5, 1), (5, 3), (7, 1)} 
R_{1} ={(1,2), (1,8), (3,6), (5,4), (7,2), (7,8)}
where x+y is divisible by 3
R_{2} = {(2,2), (4,4), (6,2), (6,4), (8,2)}
where x+y is not divisible by 3
Then the composition of R_{1} with R_{2} denotes R_{1}R_{2}, is the relation from A to C defined by property such as:
(x,z) ∈ R_{1}R_{2}, iff if there is a y ∈ B such that (x,y) ∈ R_{1} and (y,z) ∈ R_{2}.
Thus, R_{1}R_{2} = {(1,2), (3,2), (3,4), (5,4), (7,2)}
Question 5 
n  1  
n  
n + 1  
2n  1 
= n  1
Question 6 
x = 6, y = 3, z = 2  
x = 12, y = 3, z = 4  
x = 6, y = 6, z = 4  
x = 12, y = 3, z = 0 
Question 7 
(a* + b* + c*)*  
(a*b*c*)*  
((ab)* + c*)*  
(a*b* + c*)* 
From option 'c' we cannot be able to create a without b. So option is not equivalent.
Question 8 
3  
4  
5  
6 
To create 2input ExclusiveOR function we require 4 NAND gates.
Question 9 
There exist contextfree languages such that all the contextfree grammars generating them are ambiguous  
An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it  
Both deterministic and nondeterministic pushdown automata always accept the same set of languages  
A finite set of string from one alphabet is always a regular language

But nondeterministic ones can recognize all contextfree languages.
So, option C is false.
Question 10 
32 K × 16 bits  
64 K × 16 bits  
16 K × 32 bits  
64 K × 32 bits 
Possible combination in ROM = (2^{8} × (2^{8}) [size of truth table]
= 2^{16}
= 64 KB
= 64 K ×16 bits
Question 11 
What is the bit rate of a video terminal unit with 80 characters/line, 8 bits/character and horizontal sweep time of lOOµs (including 20 µs of retrace time)?
8 Mbps  
6.4 Mbps  
0.8 Mbps  
0.64 Mbps 
Total number of bits transmitted = 80 * 8 = 640 bits
Bit rate = (640 * 10^{6})/100 = 6.4 Mbps
Question 12 
13.0 ns  
12.8 ns  
12.6 ns  
12.4 ns 
H_{1} = 0.8, (1  H_{1}) = 0.2
H_{2} = 0.9, (1  H_{2}) = 0.1
T_{1} = Access time for level 1 cache = 1ns
T_{2} = Access time for level 2 cache = 10ns
H_{m} = Hit rate of main memory = 1
T_{m} = Access time for main memory = 500ns
Average access time = [(0.8 * 1) + (0.2 * 0.9 * 10) + (0.2)(0.1) * 1 * 500]
= 0.8 + 1.8 + 10
= 12.6ns
Question 13 
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worstcase time complexity of the best known algorithm to delete the node x from the list?
O(n)  
O(log^{2} n)  
O(logn)  
O(1) 
Question 14 
Stack  
Address Space  
File Descriptor Table  
Message Queue 
Question 15 
x = 1 + x;  
x = 1  x;  
x = x  1;  
x = 1 % x; 
For x = 0, it gives 1.
For x = 1, it gives 0.
Question 16 
II and III  
II and IV  
I and III  
II only 
Question 17 
effort and duration based on the size of the software  
size and duration based on the effort of the software  
effort and cost based on the duration of the software  
size, effort and duration based on the cost of the software 
Question 18 
Entity Relationship Diagram  
Deployment Diagram  
Data Flow Diagram  
Use Case Diagram 
Question 19 
A software organization has been assessed at SEI CMM Level 4. Which of the following does the organization need to practice beside Process Change Management and Technology Change Management in order to achieve Level 5?
Defect Detection  
Defect Prevention  
Defect Isolation  
Defect Propagation 
Question 20 
keeping track of the schedule based on the milestones reached  
maintaining different versions of the configurable items  
managing manpower distribution by changing the project structure  
all of the above 
Question 21 
Page  
Table  
Row  
Page, table and row level locking allow the same degree of concurrency

Table locking can be used for concurrency control with DDL operations.
In row share table is less restrictive but it consists of highest degree of concurrency compared to page and table.
Question 22 
Packet switching leads to better utilization of bandwidth resources than circuit switching.  
Packet switching results in less variation in delay than circuit switching.  
Packet switching requires more per packet processing than circuit switching.  
Packet switching can lead to reordering unlike in circuit switching. 
Question 23 
TCP guarantees a minimum communication rate  
TCP ensures inorder delivery  
TCP reacts to congestion by reducing sender window size  
TCP employs retransmission to compensate for packet loss

Sequence numbers can allow receivers to discard duplicate packets and properly sequence reordered packets.
Option C:
If the congestion is deleted, the transmitter decreases the transmission rate by a multiplicative factor.
Option D:
Acknowledgement allows the sender to determine when to retransmit lost packets.
Question 24 
HTTP runs over TCP  
HTTP describes the structure of web pages  
HTTP allows information to be stored in a URL  
HTTP can be used to test the validity of a hypertext link 
Question 25 
Sender encrypts using receiver’s public key  
Sender encrypts using his own public key  
Receiver decrypts using sender’s public key  
Receiver decrypts using his own public key 
Question 26 
14  
30  
62  
126 
= 2^{6} 2
= 64  2
= 62
Question 27 
A host is connected to a Department network which is part of a University network. The University network, in turn, is part of the Internet. The largest network in which the Ethernet address of the host is unique is:
the subnet to which the host belongs  
the Department network  
the University network  
the Internet 
Question 28 
byte  
word  
segment  
message 
Question 29 
session and request only  
request and response only  
response and session only  
session, request and response 
Question 30 
l and II only  
II and III only  
l and III only  
I, II and III 
Then there are certain compliance rules which may be used for inheritance. So other statement (I) and (II) are True.
Question 31 
P and Q only  
P and R only  
P and S only  
P, Q, R and S 
If we somehow get this fallacy (T→F) then an argument is invalid.
For options P and S you don't get any such combinations for T→F, so P and S are valid.
For option Q: If we put p=F, q=T, r=T then we get T→F. So its INVALID.
For option R: If we put p=F, q=F, r=F then we get T→F. So it is INVALID.
So, answer is (C).
Question 32 
Find its determinant, Determinant = 3.
Now check options, by putting n=1, I am getting following results,
A) 5
B) 7
C) 3
D) 3
(A), (B) can't be the answer.
Now, check for n=2, Determinant = 91 = 8.
Put n=2 in (C), (D)
C) 7
D) 8
So, (D) is the answer.
Question 33 
Question 34 
nH_{n+1} – (n + 1)  
(n + 1)H_{n} – n  
(n + 1)H_{n} – n  
(n+1)H_{n+1} – (n+1) 
Question 35 
44  
96  
120  
3125 
Question 37 
10  
11  
18  
19 
By Handshaking Lemma,
6 * 2 + 3 * 4 + (x  9) * 3 = 27 * 2
24 + (x  9) * 3 = 54
x = 19
Question 38 
Question 39 
QII, RIV, SII, TI  
QIII, RII, SI, TIV  
QII, RI, SIV, TIII  
QI, RIV, SII, TIII 
Question 40 
aaa  
aabab  
baaba  
bab 
Now, here transition ((s,a,t), (s,a)) implies reading input symbol 'a' in the state 's' we have to move 's' having any symbol on the top of stack ... epsilon here implies "anything on of Top of stack".
Now, observe the PDA carefully, it is saying that in the starting you have to push one 'a' for each of 'a' and 'b'. And in the end you have to pop one 'a' by one 'a' by one 'a' or one 'b'. Thus the count of a's and b's in first half of the string should be equal to second half of string. Now to move from first half to second half we are required one 'a', i.e., moving from s to f.
So, all odd strings in which 'a' is the middle element will be accpeted.
Thus in our question, option (B) is aabab having 'b' in the middle and thus can't be accepted.
Question 41 
{A→aB, A→bA, B→bA, B→aA, B→ε}  
{A→aA, A→bB, B→bB, B→aA, B→ε}  
{A→bB, A→aB, B→aA, B→bA, A→ε}  
{A→aA, A→bA, B→bB, B→aA, A→ε} 
Question 42 
1 only  
2 only  
3 only  
1 and 3 only 
1) Sign bit of two input numbers is 0, and the result has sign bit 1.
2) Sign bit of two input numbers is 1, and the result has sign bit 0.
So, only (2) causes overflow.
Question 43 
(A72E)_{16} and (22130232)_{4}  
(A72E)_{16} and (22131122)_{4}  
(A73E)_{16} and (22130232)_{4}  
(A62E)_{16} and (22120232)_{4}

= (00 1010 0111 0010 1110)_{2}
= (A72E)_{16}
Also,
(001 010 011 100 101 110)_{2}
= (00 10 10 01 11 00 10 11 10)_{2}
= (22130232)_{4}
Question 44 
AC’+ AB + A’C  
AB’+ AC’+ A’C  
A’B+ AC’+ AB’  
A’B + AC + AB’ 
⇒ A'C + AC' + AB'
Question 45 
A serial transmission T1 uses 8 information bits, 2 start bits, 1 stop bit and 1 parity bit for each character. A synchronous transmission T2 uses 3 eight bit sync characters followed by 30 eight bit information characters. If the bit rate is 1200 bits/second in both cases, what are the transfer rates of T1 and T2?
100 characters/sec, 153 characters/sec  
80 characters/sec, 136 characters/sec  
100 characters/sec, 136 characters/sec  
80 characters/sec, 153 characters/sec 
Transfer rate = 1200/12 = 100 char/sec
T_{2}: Transfer character in bits = 24 + 240 = 264 bits
In 264 = 30 characters
Then in 1200 = ? 264/30 = 1200/x
x = 136.3 char/sec
So, correct option is (C).
Question 46 
R1 → R3 R2 → M[100]  
M[100] → R2 R1 → R2 R1 → R3  
R1 → M[100] R2 → R3  
R1 → R2 R1 → R3 R1 → M[100] 
Question 47 
11 ns  
12 ns  
13 ns  
28 ns 
So, total time would be 13 ns.
Question 48 
4  
5  
6  
7 
4, 3, 25, 8, 19, 6, 16, 35
CPU array (first element being least recently used)
[4, 3, 19, 6, 25, 8, 16, 35]
So, 45 replaces 4.
45, 3, 25, 8, 19, 6, 16, 35 [3, 19, 6, 25, 8, 16, 35, 45]
Similarly, 22 replaces 3 to give,
45, 22, 25, 8, 19, 6, 16, 35 [19, 6, 25, 8, 16, 35, 45, 22]
8 hits in cache.
45, 22, 25, 8, 19, 6, 16, 35 [19, 6, 25, 16, 35, 45, 22, 8]
3 replaces 19,
45, 22, 25, 8, 3, 6, 16, 35 [6, 25, 16, 35, 45, 22, 8, 3]
16 and 25 hits in cache,
45, 22, 25, 8, 3, 6, 16, 35 [6, 35, 45, 22, 8, 3, 16, 25]
Finally, 7 replaces 6, which is in block 5.
Question 49 
T1.I1 + T2.I3 + T4.I3 + T3  
(T1 + T2 + T3).I3 + T1.I1  
(T1 + T2 ).I1 + (T2 + T4).I3 + T3  
(T1 + T2 ).I2 + (T1 + T3).I1 + T3 
So, Ain is 1 in T3 of I1, I2 and I3. Also during T1, and T2 and T4 of I3. So, answer will be
T1.I1 + T2.I3 + T4.I3 + T3.I1 + T3.I2 + T3.I3
Since, CPU is having only 3 instructions, T3.I1 + T3.I2 + T3.I3 can be replaced by T3.
So, T1.I1 + T2.I3 + T4.I3 + T3
Question 50 
1.155  
1.185  
1.255  
1.285 
Question 51 
The storage area of a disk has innermost diameter of 10 cm and outermost diameter of 20 cm. The maximum storage density of the disk is 1400 bits/cm. The disk rotates at a speed of 4200 RPM. The main memory of a computer has 64bit word length and 1µs cycle time. If cycle stealing is used for data transfer from the disk, the percentage of memory cycles stolen for transferring one word is
0.5%  
1%  
5%  
10% 
x μs is data transfer time.
% of time CPU idle is,
y/x × 100
Maximum storage density is given, so consider innermost track to get the capacity
= 2 × 3.14 × 5 × 1700 bits
= 3.14 × 14000 bits
Rotational latency = 60/4200 s = 1/70 s
Therefore, to read 64 bits, time required
(10^{6} × 64)/(70 × 3.14 × 17000) μs = 20.8 μs
As memory cycle time given is 1μs,
Therefore, % CPU cycle stolen = (1/20.8) × 100 ≈ 5%
Question 52 
A program attempts to generate as many permutations as possible of the string, 'abcd' by pushing the characters a, b, c, d in the same order onto a stack, but it may pop off the top character at any time. Which one of the following strings CANNOT be generated using this program?
abcd  
dcba  
abad  
cabd 
B) First push abcd, and after that pop one by one. Sequence of popped elements will come to dcba.
C) push abc, and after that pop one by one. Sequence of popped elements will come to cba. Now push 'd' and pop 'd', final sequence comes to cbad.
D) This sequence is not possible because 'a' cannot be popped before 'b' anyhow.
Question 53 
An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n  1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n  1)/2⌋, ⌊(n  3)/2⌋, ....., 0. The time required to construct a heap in this manner is
O(log n)  
O(n)  
O(n log log n)  
O(n log n) 
And we know that time complexity for building the heap is O(n)
Question 54 
Left root right.
Preorder traversal is,
Root left right.
Question 55 
f(n) + g(n) = O(h(n)) + h(n))  
f(n) = O(h(n))  
fh(n) ≠ O(f(n))  
f(n)h(n) ≠ O(g(n)h(n))

So, f(n)g(n) = O(g(n)h(n)) is True.
Hence, (D) is false.
Question 56 
(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)  
(A, D), (A, B), (A, C), (C, F), (G, E), (F, G)  
(A, B), (A, D), (D, F), (F, G), (G, E), (F, C)  
(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)

(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
Question 57 
PII, QIII, RIV, SI  
PIV, QIII, RI, SII  
PIII, QII, RIV, SI  
PIV, QII, RI, SIII 
Binary search  T(n/2) + 1
Merge sort  T(n) = 2T(n/2)+ cn
Tower of hanoi  T(n) = 2T(n1) +1
Question 58 
In (D) , given statements is wrong as temporary variable needs to be assigned some value and not viceversa.
Question 59 
43 80  
42 74  
33 37  
32 32 
In first case of funcf, which in turn calls funcg, y becomes 11 and it returns 5+11=16.
In second call of funcg, y becomes 12 and it returns 5+12=17.
So, in main y is incremented by 16+17=33 to become 10+33 =43.
In second iteration:
y will be incremented by 18+19=37 to give 43+37=80.
Question 60 
?1 is getchar() ! = ‘\n’ ?2 is getchar(c);  
?1 is (c = getchar()); ! = ‘\n’ ?2 is getchar(c);  
?1 is c! = ‘\n’ ?2 is putchar(c);  
?1 is (c = getchar()) ! = ‘\n’ ?2 is putchar(c); 
putchar( ) = writes a character specified by the argument to stdout.
As getchar( ) and putchar( ), both are needed to read the string and prints its reverse and only option (D) contains both the function. (D) is the answer.
Now coming to the code, wrt_id(void) is calling itself recursively. When \n is encountered, putchat( ) gets executed and prints the last character and then the function returns to its previous call and prints last 2^{nd} character and so on.
Question 61 
AB UV VW VW  
AB UV AB VW  
AB UV UV VW  
AB UV VW UV 
→ f1 is call by value. The changes applicable only for local from f1. UV is printed.
→ Back in main( ), AB is printed.
→ Then in f2, VW is printed.
Hence, answer is (B).
Question 62 
2 and 3  
3 and 3  
3 and 4  
4 and 4

Direction changes at 120, 110, 130.
FCFS: (90) 120 30 70 115 130 110 80 20 25
Direction changes at 120, 30, 130, 20.
Question 63 
The scheme is deadlockfree, but not starvationfree  
The scheme is not deadlockfree, but starvationfree  
The scheme is neither deadlockfree nor starvationfree  
The scheme is both deadlockfree and starvationfree 
So, starvation is possible, but deadlock is not possible.
Question 64 
n  
2^{n}  1  
3^{n}  1 
2^{n}  1.
Question 65 
P(full), V(empty), P(full), V(empty)  
P(full), V(empty), P(empty), V(full)  
P(empty), V(full), P(empty), V(full)  
P(empty), V(full), P(full), V(empty) 
In process P_{1}, wait on semaphore 'empty' signifies that if there is no space in buffer then P_{2} cannot produce more items. Signal on semaphore 'full' is to signify that one item has been added to the buffer.
In process P_{2}, wait on semaphore 'full' signifies that if the buffer is empty then consumer cannot consume any item. Signal on semaphore 'empty' increments a space in the buffer after consumption of an item.
Question 66 
In a virtual memory system, size of virtual address is 32bit, size of physical address is 30bit, page size is 4 Kbyte and size of each page table entry is 32bit. The main memory is byte addressable. Which one of the following is the maximum number of bits that can be used for storing protection and other information in each page table entry?
2  
10  
12  
14 
No. of frames = Physical memory size/Page size
= (2^{30})/(2^{12})
= 2^{18}
18+4 = 32 (PT entry size = 32 bits)
k = 14 bits
Question 67 
In a particular Unix OS, each data block is of size 1024 bytes, each node has 10 direct data block addresses and three additional addresses: one for single indirect block, one for double indirect block and one for triple indirect block. Also, each block can contain addresses for 128 blocks. Which one of the following is approximately the maximum size of a file in the file system?
512 MB  
2 GB  
8 GB  
16 GB 
= (10 + 2^{7} + 2^{7} × 2^{7} + ^{7} × ^{7} × ^{7}) × 2^{10}
≈ 2^{31}
≈ 2 GB
Question 68 
A software project involves execution of 5 tasks T1, T2, T3, T4 and T5 of duration 10, 15, 18, 30 and 40 days, respectively. T2 and T4 can start only after T1 completes. T3 can start after T2 completes. T5 can start only after both T3 and T4 complete. What is the slack time of the task T3 in days?
0  
3  
18  
30 
Question 69 
1  
2  
3  
4 
Question 70 
Assume that the delivered lines of code L of a software is related to the effort E in person months and duration t in calendar months by the relation L = P* (E/B)^{1/3} * t^{4/3}, where P and B are two constants for the software process and skills factor. For a software project, the effort was estimated to be 20 person months and the duration was estimated to be 8 months. However, the customer asked the project team to complete the software project in 4 months. What would be the required effort in person months?
10  
40  
160  
320 
Question 71 
A software was tested using the error seeding strategy in which 20 errors were seeded in the code. When the code was tested using the complete test suite, 16 of the seeded errors were detected. The same test suite also detected 200 nonseeded errors. What is the estimated number of undetected errors in the code after this testing?
4  
50  
200  
250 
Question 73 
2  
3  
5  
4 
Then, we get
T1: {A11, A12, A13}  key is A11
T2: {A21, A22, A11}  key is A21
T3: {A21, A23}  key is {A21, A23}
Question 74 
0 row and 4 columns  
3 rows and 4 columns  
3 rows and 5 columns  
6 rows and 5 columns 
rows = 3 * 2 = 6
Columns = 3 + 2 = 5
Question 75 
A relation Empdtl is defined with attributes empcode (unique), name, street, city, state and pincode. For any pincode, there is only one city and state. Also, for any given street, city and state, there is just one pincode. In normalization terms, Empdtl is a relation in
1NF only  
2NF and hence also in 1NF  
3NF and hence also in 2NF and 1NF  
BCNF and hence also in 3NF, 2NF an 1NF 
Here key is empcode and contains only one attribute, hence no partial dependency. But there is transitive dependency in this.
Pincode → city, state, so it is not in 3NF.
Question 76 
18.75  
20  
25  
NULL 
(15+25+35)/3 = 25
Question 77 
S is serializable only as T1, T2  
S is serializable only as T2, T1  
S is serializable both as T1, T2 and T2, T1  
S is serializable either as T1 or as T2  
None of these 
Question 78 
Both (i) and (ii) will fail  
(i) will fail but (ii) will succeed  
(i) will succeed but (ii) will fail  
Both (i) and (ii) will succeed 
But in (ii) if we set in Department table, Dept_id = Null, then it will produce inconsistency because in Student table we will still have the tuples containing the Dept_id = 1.
Question 79 
Consider a table T in a relational database with a key field K. A Btree of order p is used as an access structure on K, where p denotes the maximum number of tree pointers in a Btree index node. Assume that K is 10 bytes long; disk block size is 512 bytes; each data pointer P_{D} is 8 bytes long and each block pointer P_{B} is 5 bytes long. In order for each Btree node to fit in a single disk block, the maximum value of p is
20  
22  
23  
32 
r = record_ptr_size
b = block_ptr_size
(p  1) (k + r) + p × b ≤ 512
(p  1) (10 + 8) + p × 5 ≤ 512
23p ≤ 530
p ≤ 23.04
So, maximum value of p possible will be 23.
Question 80 
In a data link protocol, the frame delimiter flag is given by 0111. Assuming that bit stuffing is employed, the transmitter sends the data sequence 01110110 as
01101011  
011010110  
011101100  
0110101100 
Thus using the above logic,
Delimiter flag: 0111
Data sequence: 01110110
So, for a flag of 4 bits we will compare data sequence with a pattern of 3 bits, i.e., 011.
0 1 1 0 1 0 1 1 0 0
In the above pattern the underlined bits are found matched. Hence, 0 in italics is stuffed. Thus resulting in the data sequence as 0110101100 which is option (D).
Question 81 
In a sliding window ARQ scheme, the transmitter's window size is N and the receiver's window size is M. The minimum number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is
min (M,N)  
max (M,N)  
M + N  
MN 
Question 82 
Consider a 10 Mbps token ring LAN with a ring latency of 400 µs. A host that needs to transmit seizes the token. Then it sends a frame of 1000 bytes, removes the frame after it has circulated all around the ring, and finally releases the token. This process is repeated for every frame. Assuming that only a single host wishes to transmit, the effective data rate is
1Mbps  
2Mbps  
5Mbps  
6Mbps 
Question 83 
A 20 Kbps satellite link has a propagation delay of 400 ms. The transmitter employs the "go back n ARQ" scheme with n set to 10. Assuming that each frame is 100 bytes long, what is the maximum data rate possible?
5 Kbps  
10 Kbps  
15 Kbps  
20 Kbps 
Question 84 
I and III  
I, II and III  
II and IV  
I, II, III and IV

Given transmitted codewords are
By inspection we can find the rule for generating each of the parity bits,
Now from above we can see that (I) and (III) are only codewords.
Question 85 
Consider a simplified time slotted MAC protocol, where each host always has data to send and transmits with probability p = 0.2 in every slot. There is no backoff and one frame can be transmitted in one slot. If more than one host transmits in the same slot, then the transmissions are unsuccessful due to collision. What is the maximum number of hosts which this protocol can support, if each host has to be provided a minimum through put of 0.16 frames per time slot?
1  
2  
3  
4 
0.16 = 0.2 × 0.8^{N1}
⇒ 0.8 = 0.8^{N1}
⇒ N = 2
Question 86 
Fragment Offset  
Source IP address  
Destination IP address  
Destination port number 
Question 87 
A TCP message consisting of 2100 bytes is passed to IP for delivery across two networks. The first network can carry a maximum payload of 1200 bytes per frame and the second network can carry a maximum payload of 400 bytes per frame, excluding network overhead. Assume that IP overhead per packet is 20 bytes. What is the total IP overhead in the second network for this transmission?
40 bytes  
80 bytes  
120 bytes  
160 bytes 
2120B reach R1's network layer. It removes original IP header, fragments data part at IP and then appends IP header to all fragments and forwards . So, it divides 2100 Bytes into two fragments of size 1200 and 900. And both fragments are sent to R2.
At Router2:
Both fragments that reach R2 exceed MTU at R2. So, both are fragmented. First packet of 1200B is fragmented into 3 packets of 400 Bytes each. And second packet of 900B is fragmented into 3 fragments of 400, 400 and 100 Bytes respectively.
So, totally 6 packets reach destinations.
So, total IP overhead = 6 × 20 = 120 Bytes
Question 88 
Suppose that the maximum transmit window size for a TCP connection is 12000 bytes. Each packet consists of 2000 bytes. At some point of time, the connection is in slowstart phase with a current transmit window of 4000 bytes. Subsequently, the transmitter receives two acknowledgements. Assume that no packets are lost and there are no timeouts. What is the maximum possible value of the current transmit window?
4000 bytes  
8000 bytes  
10000 bytes  
12000 bytes 
and packet size =2000 B (or MSS)
Receiver window size = 6 MSS and
Current sender window size = 2 MSS
Slow start threshold = receiver window/2 = 3 MSS
Now current sender window size = 2 MSS <3 MSS,
which implies transmission is in slow start phase.
After receiving first Ack: Current sender window should increase exponentially to 4 MSS but since threshold = 3 MSS, current sender window size goes to threshold which is 3 MSS, then after receiving second Ack: Since now it is in congestion avoidance phase, sender window size increases linearly which makes current sender window
= 4 MSS
= 4 × 2000 B
= 8000 B