Q5.Consider a source computer (S) transmitting a file of size 106 bits to a destination computer
(D) over a network of two routers (R1 and R2) and three links (L1, L2, and L3). L1 connects S
to R1; L2 connects R1 to R2; and L3 connects R2 to D. Let each link be of length 100km.
Assume signals travel over each line at a speed of 108 meters per second. Assume that the
link bandwidth on each link is 1Mbps. Let the file be broken down into 1000 packets each of
size 1000 bits. Find the total sum of transmission and propagation delays in transmitting the
file from S to D?
Answer : Option AExplaination / Solution: No Explaination.
Q6.Let W(n) and A(n) denote respectively, the worst case and average case running time of an
algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?
Answer : Option CExplaination / Solution:
The average case time can be lesser than or even equal to the worst case. So A(n) would be
upper bounded by W(n) and it will not be strict upper bound as it can even be same (e.g.
Bubble Sort and merge sort).
∴A(n) = O(W(n))
Q8.An Internet Service Provider (ISP) has the following chunk of CIDR-based IP addresses
available with it: 245.248.128.0/20. The ISP wants to give half of this chunk of addresses to
Organization A, and a quarter to Organization B, while retaining the remaining with itself.
Which of the following is a valid allocation of address to A and B?
Answer : Option AExplaination / Solution:
Since half of 4096 host addresses must be given to organization A, we can set 12th bit to 1
and include that bit into network part of organization A, so the valid allocation of addresses to
A is 245.248.136.0/21
Now for organization B, 12th bit is set to ‘0’ but since we need only half of 2048 addresses,
13th bit can be set to ‘0’ and include that bit into network part of organization B so the valid
allocation of addresses to B is 245.248.128.0/22
Q10. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem
with n discs is
Answer : Option DExplaination / Solution:
Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B
The following sequence of steps are executed recursively
1.move n−1 discs from A to B. This leaves disc n alone on peg A --- T(n-1)
2.move disc n from A to C---------1
3.move n−1 discs from B to C so they sit on disc n----- T(n-1)
So, T(n) = 2T(n-1) +1
Total Question/Mark :
Scored Mark :
Mark for Correct Answer : 1
Mark for Wrong Answer : -0.5
Mark for Left Answer : 0