Question on Summing up a series

Find the sum of the expression

(A) 7
(B) 8
(C) 9
(D) 10

Answer : (B)

Explanation : 

The expression can be written as :

= [sq_root(2) - sq_root(1) ] + [sq_root(3) - sq_root(2) ] + [sq_root(4) - sq_root(3) ] + ... + [sq_root(81) - sq_root(80) ]
= sq_root(81)  - - sq_root(1)
= 9 - 1
= 8

Hence the answer is 8.

Question on Speed & Distance

A tourist covers half of his journey by train at 60 km/h, half of the remainder by bus at 30 km/h and the rest by cycle at 10 km/h. The average of the tourist in km/h during his entire journey is

(A) 36
(B) 30
(C) 24
(D) 18

Answer: (C)

Explanation :

Lets assume the distance = X

Time it took for the tourist to cover first part of the journey = (X/2)/60 = X/120
Time it took for the tourist to cover second part of the journey = (X/4)/30 = X/120
Time it took for the tourist to cover third part of the journey = (X/4)/10 = X/40

Total time it took for the journey = X/120 + X/120 + X/40 = 5X/120

Average speed of the journey = Distance/ Time = X / (5X/120) = 120/5 = 24 Kmph

Question on Probability

Out of all the 2-digit integers between 1 and 100, a 2-digit number has to be selected at random. What is the probability that the selected number is not divisible by 7?

(A) 13/90
(B) 12/90
(C) 78/90
(D) 77/90

Answer : (D)

Explanation:
Number of 2 digit numbers between 1 and 100 = 90

2 digit numbers between (10 and 99) that are divisible by 7 : 7, 14, 21, 28, 35, 42, 49, 56, 73, 70, 77, 84, 91, 98

Number of 2 digit numbers between (10 and 99) that are divisible by 7 = 13.

Number of 2 digit numbers between (10 and 99) that are NOT divisible by 7 = 90 - 13 = 77

So, the probability that a number is NOT divisible by 7 = 77/90

Question on English : 3

Which one of the following options is the closest in meaning to the word given
below?
Nadir
(A) Highest (B) Lowest (C) Medium (D) Integration

Answer: (B)

Explanation : 
Nadir is the lowest point on a curve.

Question on English

Were you a bird, you ___________ in the sky.
(A) would fly (B) shall fly
(C) should fly (D) shall have flown

Answer: (A)

Question on English

Complete the sentence:
Universalism is to particularism as diffuseness is to ________
(A) specificity (B) neutrality (C) generality (D) adaptation

Answer: (A)
The relation is that of antonyms

Question on Series

What will be the maximum sum of 44, 42, 40, ... ?

(A) 502
(B) 504
(C) 506
(D) 500

Answer: C

Explanation :
44 + 42 + 40 + 38 + ..... + 4 + 2 + 0 + (-2) + (-4) + ....

This series is maximum when the series reaches 2.

So, the sum of
= 44 + 42 + 40 + 38 + ..... + 4 + 2
= 2 (22 + 21 + 20 + .... + 1)
= 2 (22 * 23) /2
= 506

Topics to revise :
Arithmetic Expressions

Question on Logical Expressions

What is the logical translation of the following statement?

                              “None of my friends are perfect.”

Answer : D

Explanation :

This question is not properly explained. Looks like F(X) returns TRUE if X is a friend and P(X) returns TRUE is X is prefect.

Analyzing Options Method

Option A :

This options says that, there exist a person X such that he is a friend to me AND he is not perfect. This sentence basically says :"Some of my friends are not perfect". So, obviously it is not saying “None of my friends are perfect.”.

Option B :

This options says, there is a person who is not a friend to me but he is perfect. Means "Some of people who are not friends with me are perfect". Obviously it does not say “None of my friends are perfect.”.

Option C :

This option says, there exist a person X who is not a friend to me and he is not perfect as well. Means "Some of people who are not friends with me are not perfect". Obviously it does not mean “None of my friends are perfect.”.

Option D :

This option basically says, there does not exist a person who is friends with me and perfect as well. That means "None of my friends are actually perfect". There could be persons who are friends with me but they are not perfect OR they are perfect but they are not friends with me. This is exactly we are looking for.

Derivation Approach

 “None of my friends are perfect.”

=> Vx (F(x) --> ~P(x)) [V means For All, ~ is negate operation]

=> Vx(~F(x) v ~P(x))

=> ~Ex(F(x) ^ P(x)) [E means There Exist]

Topics to revise :
Logical Expressions

References :

Question on Programming

Consider the following function

Answer : B

Explanation :

Loop A runs Log N times if you watch closely.
[ J becomes 2, 4, 8, 16, ...., 2^X. It stops when 2^X = N. That is X = Log N.]

Loop B runs for n/2 times. Each time Loop A runs it increments K by n/2.

So, value of K is approx, n/2 times the statement inside A runs.
=> n/2 * Number of times Loop B runs * Number of times Loop A runs
=> n/2 * n/2 * Log N
=> O(n^2 Log N)

Topics to revise :
C language

References :
None as of now

Question on Basic Graph Theorems

Which of the following statements is/are TRUE for undirected graphs?

P  : Number of odd degree vertices is even.
Q : Sum of degrees of all vertices is even.

(A) P only
(B) Q only
(C) Both P and Q
(D) Neither P nor Q

Answer: C

Explanation :

Example Method
Example 1:

P: number of add degree vertices = 2 (Even) => P is valid
Q: Sum of degrees of all vertices = 1+2+2+1 = 6 (Even) =>Q is valid

Example 2:

P: number of add degree vertices = 0 (Even) => P is valid
Q: Sum of degrees of all vertices = 2+2+2 = 6(Even) =>Q is valid





Example 3:

P: number of add degree vertices = 2 (Even) => P is valid
Q: Sum of degrees of all vertices = 2+2+3+3+2 = 12 (Even) =>Q is valid





Direct Proof Method
Prove P : Number of odd degree vertices is even.
Lets assume there are n nodes in undirected graph and n1 nodes are of add degree. This information can be put in an equation format as shown below.

We know that part C of the expression is even number as a undirected edge corresponds to 1 degree to each of the nodes attached.

B part of the expression is also even number because degrees of all vertices of Vn1+1 to Vn are even numbers.

If we observe A part of the expression, deg(Vi) for i=1 to n1 are odd numbers. To make the whole expression (A) even n1 has to be a even number.

Hence, the number of nodes (n1) of off degree are even.

Prove Q : Sum of degrees of all vertices is even. 
This property is obvious from the fact that while counting the degress of vertices, each edhe is counted twice (once at each end).

Topics to revise :
Undirected Graphs and Basic Theorems

References :
Please read Chapter 1: Introduction (Page 8) in Graph Theory by N.Deo

Question on Graphs & Probability

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is ½. What is the expected number of unordered cycles of length three?

(A) 1/8
(B) 1
(C) 7
(D) 8

Answer: C

Explanation :
To make a cycle of 3, we need 3 vertices.

The number of such sets of 3 vertices from set of 8 is = 8C3
[Not 8P3, because the order of nodes is not important]

For such each set of such 3 vertices, a loop/cycle will be made only of 3 edges exist between those nodes. Probability of having a cycle between those 3 nodes is = (1/2)(1/2)(1/2) = 1/8

Expected number of cycles will be = 8C3 * (1/8) = 7



Topics to revise :
Probability
Undirected Graphs and Cycles

References :

Question on Digital Circuits

A RAM chip has a capacity of 1024 words of 8 bits each (1K × 8) . The number of 2 × 4 decoders with enable line needed to construct a 16K × 16 RAM from 1K × 8 RAM is

A. 4
B. 5
C. 6
D. 7

Answer : (B)

Explanation :
Basic RAM chip size = 1K × 8
RAM to construct = 16K × 16

For each word in the new RAM, word size is 16 bits, So you need to put 2 RAMs (1K × 8) to create (1K × 16).We can put such 16 dual RAMs to create 16K × 16.i.e., 16 X (1K × 16).

To address 16K locations in 16K × 16 we need 14 bits. 10 bits will be used to to locate the word in 1K × 16 locations. Rest of the 4 bits will need to be used to identify one of the 16 locations. For this we will need 4×16 DECODER.

But we need to solve this problem with 2×4 decoders. You can arrange (or will need) 5 such 2×4 decoders to use 4×16 decoder.

Hence we need 5 2×4 decoders. Answer: B.

Topics to revisit :
Decoders
Encoders
Multiplexers
DeMultiplexers

References :

Question on sorting

The number of elements that can be sorted in Θ (log n) time using heap sort is

(A) Θ (1)
(B) Θ ( sq_root(log n) )
(C) Θ (log n/(log log n))
(C) Θ (log n)

Answer: C.

Explanation :

Sorting complexity of heap sort is O(n logn).

Lets assume that x number of elements can be sorted in log n time.
i.e., O(x log x) = O(log n)

Substitution method
Option A : x = O(1)

Complexity to sort the array of O(1) elements using heap sort is O(1 log(1)) = O(1). This is not an answer as O(log n) != O(1).

Option B : x = O (sq_root(log n))
Complexity to sort the array of O (sq_root(log n)) elements using heap sort is sq_root(log n)) log (sq_root(log n))) = O( sq_root(log n)) * log (log n) ) != O(log n)

Option C : x = Θ (log n/(log log n))
Complexity to sort the array of Θ (log n/(log log n)) elements using heap sort is
     =  O ( log n/(log log n) log (log n/(log log n)) )
     =  O ( log n/(log log n)  * [ log (log n) -  log (log log n)]
     =  O ( log n - [logn * log (log log n)/log log n)] )
     =   O (log n).

Option D : x = Θ (log n)
Complexity to sort the array of Θ (log n) elements using heap sort is
      = O (log n * log (log n)) != O(log n)
   
It is clear that C is the answer.

Topics to revisit :
Time complexity
Sorting
Heap sort

References :

Question on Semaphores

34. A certain computation generates two arrays a and b such that a[i]= f (i) for 0 ≤  i  < n and b[i] = g( a[i] ) for 0 ≤  i  < n . Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below.

Process X:
private i;
for  (i  = 0; i < n; i++)  { 
    a[i] = f(i);
    ExitX(R, S);
}

Process Y:
private i;
for  (i  = 0; i < n; i++)  { 
    Entry(R, S);
    b[i] = g(a[i]);
}

Which one of the following represents the CORRECT implementations of ExitX and EntryY ?

(A)
ExitX (R, S) {
    P(R) ;
    V(S) ;
}

EntryY (R, S) {
    P(S) ;
    V(R) ;
}

(B)
ExitX (R, S) {
    V(R) ;
    V(S) ;
}

EntryY (R, S) {
    P(R) ;
    P(S) ;
}

(C)
ExitX (R, S) {
    P(R) ;
    V(R) ;
}

EntryY (R, S) {
    V(S) ;
    P(R) ;
}

(D)
ExitX (R, S) {
    V(R) ;
    P(S) ;
}

EntryY (R, S) {
    V(S) ;
    P(R) ;
}

Answer : (C)

Explanation :

Lets see the difinition of Semaphore Wait (P) and Signal (V)

P(S) {
        While (S <= 0) ; //no op
         S--;
}

V(S) {
        S++;
}

If semaphore initialized to n, usually n processes can enter the critical section guarder by P(S).

Now, Lets examine the options.

Option A :

Process X:
private i;
for  (i  = 0; i < n; i++)  { 
    a[i] = f(i);
    P(R) ;
    V(S) ;
}

Process Y:
private i;
for  (i  = 0; i < n; i++)  { 
    P(S) ;
    V(R) ;
    b[i] = g(a[i]);
}

As you can see both the processes X and Y, wait for P(R) and P(S) respectfully as R and S are intialized to 0. This is like a deadlock situation.

Option B
Process X:
private i;
for  (i  = 0; i < n; i++)  { 
    a[i] = f(i);
    V(R) ;
    V(S) ;
}

Process Y:
private i;
for  (i  = 0; i < n; i++)  { 
    P(R) ;
    P(S) ;
    b[i] = g(a[i]);
}

As you can see, process Y cannot go further as it waits on R (and S). Process X can release those semaphores and process Y can go inside. This works well in normal scenario. But, it could be possible that after first execution of ExitX, process X can continue and try to execute ExitX before Y can execute EntryY. Since this is a binary semaphore (which can possibly have only two values), this is a invalid use-case.

Option D
Process X:
private i;
for  (i  = 0; i < n; i++)  { 
    a[i] = f(i);
    V(R) ;
    P(S) ;
}

Process Y:
private i;
for  (i  = 0; i < n; i++)  { 
    V(S) ;
    P(R) ;
    b[i] = g(a[i]);
}

The same invalid use-case can happen in this scenario as well. Process X runs V(R) and Process Y runs V(S) and then X can execute P(S) can go through the for loop again and try to run V(R). But that would be invalid as R is already 1.

Option C:
Process X:
private i;
for  (i  = 0; i < n; i++)  { 
    a[i] = f(i);
    P(S) ;
    V(R) ;
}

Process Y:
private i;
for  (i  = 0; i < n; i++)  { 
    V(S) ;
    P(R) ;
    b[i] = g(a[i]);
}

Process Y would go first here and execute V(S) and then it waits on P(R). Process X then executes P(S) and executes V(R) and continues. Process Y then can excute P(R) now and initialize b[i]. Now, X would come back at P(S) again and waits and similarly process Y would go through the for loop and executes V(S). This way X and Y execute altenatively one after the other i.e., X initializes a[0] and then Y generates b[0] and X generates a[1] etc.

Topics to Revise :
Semaphore

References :

Question ? on Semaphores

A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?
(A) –2
(B) –1
(C) 1
(D) 2

Answer: (D)

Explanation :

S is a counting semaphore initalized to 2 i.e., Two process can go inside a critical section protected by S.

W, X read the variable, increment by 1 and write it back.
Y, Z can read the variable, decrement by 2 and write it back.

Pseudo code W
1.    Wait(S)
2.       Read(x) //into a register
3.        x++
4.      Write(x)
5.    Release(S)

Pseudo code X
1.    Wait(S)
2.       Read(x) //into a register
3.        x++
4.      Write(x)
5.    Release(S)

Pseudo code Y
1.    Wait(S)
2.       Read(x) //into a register
3.         x = x - 2
4.      Write(x)
5.    Release(S)

Pseudo code Z
1.    Wait(S)
2.       Read(x) //into a register
3.        x = x - 2
4.      Write(x)
5.    Release(S)

Whenever Y or Z runs the count gets decreased by 2. So, to have the maximum sum, we should copy the variable into one of the processes which increases the count, and at the same time the decrementing processed should run in parallaly, so that whaterver they write back into memory can be overridden by incrementing process. So, in effect decrement would never happen.

This is how it should be done:
W executes statement 1 : Decreases the semaphone count by 1. S = 1 now.
W executes statement 2 : Reads x from memory and copies into internal register.
Y executes statement 1 :  Decreases the semaphore count by 1. S = 0 now. Now, both W, Y are in critical section and no other process can go inside it.
Y executes statements 2-4 : Reads x (i.e. 0), decrements it by 2 and writes back. Now, x = -2
Y executes statement 5 : Releases semaphore i.e., increments by 1. So, S = 1. Now, some other process can go inside ciritcal section.
Z executes statement 1 :  Decreases the semaphore count by 1. S = 0 now. Now, both W, Z are in critical section and no other process can go inside it.
Z executes statements 2-4 : Reads x (i.e. -2), decrements it by 2 and writes back. Now, x = -4
Z executes statement 5 : Releases semaphore i.e., increments by 1. So, S = 1. Now, some other process can go inside cirtical section.
W executes statement 3-4 : Increments x (i.e., 0, which it read long back) to 1, writes it back to memory. x = 1.
W executes statement 5 : Releases semaphore i.e., increments by 1. So, S = 2. Now, some other processes can go inside cirtical section.
X executes statement 1-5 : X reads the value of x (i.e., 1) and increments it by 1 and writes back to memory. x = 2 now.

this way the value of x gets maximized. Thus the answer is (D)

Topics to Revise :
Semaphores
Critical Section
Concurrent Executions

References :

Question on Logical expressions

Which one of the following expressions does NOT represent exclusive NOR of x
and y?

(A) xy  + x 'y '
(B) x  ⊕ y '
(C) x ' ⊕ y
(D) x ' ⊕ y '

Answer : (D)

Explanation :

Elimination Method

Option A : xy + x'y' => This is nothing but (x NOR y)

Option B : x ⊕ y' = x(y')'+x'(y') = xy+x'y' = X NOR y

Option C: x' ⊕ y = x'(y)'+(x')'y =x'y'+xy= X NOR y

Option D:  x ' ⊕ y ' = x'(y')'+(x')'y'=x'y+xy' = x ⊕ y <> x NOR y

So, answer is D.

Truth Table Method
Lets write truth tables for each of those expressions.

Truth tables for the expressions in question :

As you can see, except expression in (D), all expressions match x NOR y. So, answer is (D)

Topics to revise :
Logical Expressions
Truth Tables

References :

Question 16 on Deadlock

Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?

(A) X : P(a) P(b) P(c)    Y : P(b) P(c) P(d)   Z : P(c) P(d) P(a)
(B) X : P(b) P(a) P(c)    Y : P(b) P(c) P(d)   Z : P(a) P(c) P(d)
(C) X : P(b) P(a) P(c)    Y : P(c) P(b) P(d)   Z : P(a) P(c) P(d)
(D) X : P(a) P(b) P(c)    Y : P(c) P(b) P(d)   Z : P(c) P(d) P(a)

Answer: (B)

Explanation :
To solve this problem, we need to go through each of the options and check if they can create a deadlock at any point of their executions.

(A) X : P(a) P(b) P(c)    Y : P(b) P(c) P(d)   Z : P(c) P(d) P(a)
Lets assume X starts the process and executes P(a) and then Y executes P(b) and Z executes P(c). Now, X can not go forward because Y has a lock on b, and Y cannot go forward and execute P(c) because Z holds a lock on c. Now, the only process that can go forward is Z, so it executes P(d). But it cannot go further and execute P(a) because X holds the lock a. Now all the three processes cannot go ahead as they dependency on each other. Thus this method of access creates deadlocks.

(C) X : P(b) P(a) P(c)    Y : P(c) P(b) P(d)   Z : P(a) P(c) P(d)
Lets assume X starts processing with P(b) and then executes P(a). And then Y picks up P(c) and then waits on b to execute P(b) because b is locked by X -- where as X cannot go forward because it needs to execute P(c) but it was locked by Y. So, there is cleat cycle of dependencies between X and Y causing a deadlock situation.

We can also find a deadlock situation involving all of three processes as well. X executes P(b), Y executes P(c) and Z executes P(a). X cannot go forward now because Z holds the lock on a. Z cannot go forward and execute P(c) because Y holds lock on c. Similarly, Y cannot go ahead and execute P(b) because X holds lock c. As you can see, this is a deadlock situation. Also, clearly it also has circular cycle of dependencies.

(D) X : P(a) P(b) P(c)    Y : P(c) P(b) P(d)   Z : P(c) P(d) P(a)
Similar to option C, this also has a deadlock problem. X executes P(a) and P(b) and Y executes P(c). X cannot go forward now because c is locked by Y and Y cannot go forward because b is already locked by X, thus causing a deadlock situation between X & Y.

Apart from this other deadlock situations can also be found (e.g., X & Z in the circular loop waiting for lock on c and a respectively).

(B) X : P(b) P(a) P(c)    Y : P(b) P(c) P(d)   Z : P(a) P(c) P(d)
In this situation, we cannot find any deadlock. So, this is our answer.

Topics to revise
Semaphores
Deadlocks

References

Question 15: Clustered Indexes

An index is clustered, if

(A) it is on a set of fields that form a candidate key.
(B) it is on a set of fields that include the primary key.
(C) the data records of the file are organized in the same order as the data
(D) the data records of the file are organized not in the same order as the data

Answer: (C)

Explanation:
Clustered index is index whose search key specifies the sequential order of the file. Clustered index key is usually but not necessarily the primary key (link). Hence the right answer is C.

Lets evaluate the options one by one.
(A) it is on a set of fields that form a candidate key : ?
(B) it is on a set of fields that include the primary key.: If the index is on primary key (or on the fields including the primary key), it is definitely a clustered index. But if it a clustered index, it is not necessary that it would include the primary key.
(C) the data records of the file are organized in the same order as the data : This is correct
(D) the data records of the file are organized not in the same order as the data: This is not true according to the definition of clustered index.

Concepts to revise
Indexing & Hashing

References

Question 14: Transport & Datalink layer

Assume that source S and destination D are connected through two intermediate routers labeled R. Determine how many times each packet has to visit the network layer and the data link layer during a transmission from S to D.

(A) Network layer – 4 times and Data link layer-4 times
(B) Network layer – 4 times and Data link layer-3 times
(C) Network layer – 4 times and Data link layer-6 times
(D) Network layer – 2 times and Data link layer-6 times

Answer : (C)

Explanation :

As you can see in the above diagram, The packet goes to Network Layer 4 times and Data Link layer 6 times.

Why network layer is considered as only once and data link layer is considered twice ?
Once the message comes to Network layer, it tries to connect to R's network level. Network level sends message via Data link layer.

Pseudo Code for network layer at the Source (S)
Find R
Send Message to R
                 Send Message via Datalink layer.

Pseudo Code for network layer at the Receiver (R)
Ready to receive messages.
Receive Message from Source
               Message is received via Datalink layer.
Find  next R
Send Message to next R
              Send Message via Datalink layer.

As you can see datalink layer gets called twice for the message transfer (or pass through), but message gets processed only once at the network layer.

Concepts to Cover :
TCP/IP Stack
Datalink layer
Transport layer
Physical layer

References :

Question 13: Public Key Encryption

Using public key cryptography, X adds a digital signature σ to message M, encrypts <M, σ>, and sends it to Y, where it is decrypted. Which one of the following sequences of keys is used for the operations?

(A) Encryption: X’s private key followed by Y’s private key; Decryption: X’s public key  followed   by  Y’s  public key
(B) Encryption: X’s private key followed by Y’s public key; Decryption: X’s public key followed by Y’s private key
(C) Encryption: X’s public key followed by Y’s private key; Decryption: Y’s public key followed by X’s private key
(D) Encryption: X’s private key followed by Y’s public key; Decryption: Y’s private key followed by X’spublic key

Answer : (D)

Explanation :

The encryption & decryption logic in the options are related to Public Key encryption. Public keys are universally available but private keys are kept with the key owners.

When X needs to send message to Y, X first needs to encrypt it with their own private key and Y's public key and Y needs to apply decrypt the message using the keys in reverse order i.e., first with its own private key and then X's public key.

Important point to note here is that decryption needs to be done in the reverse order.

Clearly D is the answer.

Elimination approach
(A) Encryption: X’s private key followed by Y’s private key; Decryption: X’s public key  followed   by  Y’s  public key : This is clearly wrong because X does not access to Y's private key.

(B) Encryption: X’s private key followed by Y’s public key; Decryption: X’s public key followed by Y’s private key : This is clearly wrong answer as well, because Y is not decrypting in the reverse order. Y is decrypting the message with X's private key which is encrypted with Y's public key.

(C) Encryption: X’s public key followed by Y’s private key; Decryption: Y’s public key followed by X’s private key : This is wrong answer as well as X does not access to Y's private key.

(D) Encryption: X’s private key followed by Y’s public key; Decryption: Y’s private key followed by X’spublic key : This is the correct answer as the encryption and decryption are done with correct keys and decryption was also done in reverse order.

References :

Question 12: Network Protocols

The transport ayer protocols used for real time multimedia, file transfer, DNS and email, respectively are
(A) TCP, UDP, UDP and TCP
(B) UDP, TCP, TCP and UDP
(C) UDP, TCP, UDP and TCP
(D) TCP, UDP, TCP and UDP

Ans: (C)

Explanation :
TCP is a connection oriented, reliable protocol and UDP is a connection-less, unreliable protocol.

Realtime multimedia (e.g., youtube) stream is implemented using UDP protocol because it is occassinally fine to get a noise (few pixels disturbed) but it is irritating to wait for the next screen to appear (if implemented on a realiable connection oriented architecture).

File transfers need TCP protocol, because file transfer is expected to copy each and every bit of the original file. That is why FTP (File Transfer Protocol) depends on TCP at the transport layer.

DNS (Domain naming system) is used to easily translate memorized domain names to numerical IP addresses needed for the purpose of locating computer services and devices worldwide. It is implemented on top of UDP. If there is error, the clients basically retry.

Emails : Emails are sent through application layer called SMTP (Simple Mail Transfer Protocol) which is implemented on top of TCP, because it is not acceptable to send some text of the e-mail garbeled.

Concepts to revise :
OSI Model
TCP/IP Protocol
Different layers in these models.

References :

Question 11: Match Domains & Solution Technologies

Match the problem domains in Group I with the solution technologies in Group II.

(A) P – 1, Q – 2, R – 3, S – 4
(B) P – 3, Q – 4, R – 2, S – 1
(C) P – 3, Q – 1, R – 4, S – 2
(D) P – 4, Q – 3, R – 2, S – 1

Answer : (C)

Explanation :
In my opinion, this question is vague. But you can answer the question if you know 1 or 2 of the mappings.


Service Oriented Computing : Using this kind of methodology discrete pieces of heterogeneous systems can communicate with each other e.g., a service to calculate to service tax can call another service to figure out the service tax rate in a given country.

Usually service owners publish the service interface the users can call and client programs can call those services using those interfaces (bind to those interfaces).

So, it looks like P matches both of 1 & 3.

Heterogeneous communication systems : This is similar to Service oriented computing, where two or multiple heterogeneous systems (one could be a SAP service, other could be written in Java) can interact with each other using already published interface. So, Q also matches with both 1 & 3.

Looking at just these two we can easily see option C is the right choice here.

Information Representation : XML is way of representing information in a predefined way (using tags).

Process Description : BPMN (Business Process Model Notation) is a graphical representation for specifying business processes in a business process model.

You can clearly see C is the right match here.

Question 10: Job Scheduling

10. A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero(the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?

 (A) This algorithm is equivalent to the first-come-first-serve algorithm.
 (B) This algorithm is equivalent to the round-robin algorithm.
 (C) This algorithm is equivalent to the shortest-job-first algorithm.
 (D) This algorithm is equivalent to the shortest-remaining-time-first algorithm.

Answer : (B)

Explanation:

Two important things to note.

1. Process Priority is proportional to waiting time.
2. Re-evaluation happens after every T time units.

 When all processes arrive at time zero, algorithm randomly picks one of the processes Pi because all processes have priority 0. Once Pi gets executed for T time unites, re-evaluation happens. Now, priority for Pi would be 0 and all other priority would be proportional to T ( I will just call the priority as T). Now, scheduler randomly picks one of the remaining processes other than Pi. Lets assume Pj. After another T, priority for Pi would be T and Pj would be T, and for rest of them it would be 2T. Now, scheduler picks up another remaining tasks.

Assuming all processing need sufficiently large amount of time, After N*T time units, all processes have waited for (N-1)*T time units and they become equal again -- and again, same Pi would be chosen. You could clearly see that, it is following a round robin aproach i.e., P1, P2, P3, ... , PN then back to P1, P2....

The algorithm no where considers the length of the job or the remaining time of the job. It also does not matter who came first as well. So, clearly answer is B.

Example Based Approach
Lets consider 4 jobs with running times of 7, 8, 6, 5 (you can assume any random numbers). Lets name them as P1, P2, P3 and P4 respectively. Lets assume T = 3.

First P1 gets chosen as everyone has same priority.
|P1|P1|P1|

After 3 sec, priorities would be
P1 = 0, P2 = 3, P3 = 3, P4 = 3.
So, P2 gets selected.
|P1|P1|P1|P2|P2|P2|

After 6 sec, priorities would be
P1 = 0, P2 = 3, P3 = 6, P4 = 6.
So, P2 gets selected.
|P1|P1|P1|P2|P2|P2|P3|P3|P3|


continuing this way... the execution timeline would be.
|P1|P1|P1|P2|P2|P2|P3|P3|P3|P4|P4|P4|P1|P1|P1|P2|P2|P2|P3|P3|P3|P4|P4|P1|P2|P2|

It can be clearly seen, it is round robin.

Does the length of the job mattered ?
You can clearly see that the P1 with neither the smallest was chosen before other jobs.

Does the remaining job time mattered ?
Same explanation as above. P1 with remaining time of 7 is chosen before P2 (with remaining time of 8) and P4(remaining time of 5). So, clearly remaining time did not matter.

Does the first come first serve mattered ?
We cant see that in this example. Lets try another example to emphasis the first come job did not matter.

Lets tweak the example in discussion. Assume P2,P3,P4 come after 1 sec.

After first epoch of T secs. Priorities would be.
P1 = 0, P2 = 2, P3 = 2, P4 = 2.

So, now P2 would be chosen even though P1 came first. This proves that, first come job has no advantage.

Concepts to Revise :
Job Scheduling

References :

Question 9: Bottomup Parser, Maximum reduction moves

9. What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A→ ∈ and A → a) to parse a string with n tokens?

(A) n/2
(B) n-1
(C) 2n-1
(D) 2n

Answer : (C)

Explanation :
Coming Up.

Question 8: Operations on Languages

8. Consider the languages L1 = Φ and L2  = {a} . Which one of the following represents L1L2*UL1* ?
(A) {∈}
(B) Φ
(C) a *
(D) {ε, a}

Ans: (A)

Explanation :
L2* = {a}* = strings of a of any length and ∈
L1L2* =  Φ {a}* = Φ [Concatenation of empty language with any language will give the empty language ]

L1* = Φ* = ∈
L1L2*UL1* = ΦU∈ = { ∈ }
So, the answer is A.

Concepts to Revise :
Languages
Operations on Languages

References :

Question 6: Number of swaps Selection sort

6. Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

(A) O(log n)
(B) O(n)
(C) O(n log n)
(D) O(n^2)

Ans : (B)

Explanation :
One important thing to observe in the question is that, they have not asked the complexity of the selection sort, but instead they have asked the number of swaps required only.

Lets try to recollect what Selection Sort does.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Pseudo Code
For N times.
        Find the smallest element in the rest of the unsorted array. {Complexity : O(N)}
        Swap the smallest number with the first unsorted element.
        Adjust sorted and unsorted arrays.
Done.

You can clearly see, each iteration corresponds to O(N) of work. So, complexity would be O(N^2). But we need to do swap only N times in the worst case. So, the number of swaps required would be O(N).

Concepts to Revise :
Sorting Algorithms
Selection Sort
Searching Algorithms

References :

Question 7: Complexity of tree insertion

19. Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

(A) O(l)
(B) O(log n)
(C) O(n)
(D) O(n log n)

Ans: (C)

Explanation :

For a highly balanced binary tree, the number of comparisons it would take to insert a number would be log(n), because we need to compare at each level and height of such tree would be log n (because nodes gets divided into 2 at each step).

But for a skewed tree this is not true. For the worst case assume, a Right Most Tree. The height of such tree would be N, basically because at each step the nodes do not get divided but would be chained. To insert a number, in the worst case, you have to compare with each and every node in the tree. So, the number of comparisons needed would be n.

That means the complexity would be O(n).

Advise :
The best way to answer these questions is to practice writing code for the basic operation of trees i.e., insertion, deletion, addition of elements, height of the tree, in/post/pre order traversals, How to make a balanced tree etc. Write pseudo code for them at the least and and answer how much complexity is this algorithm.

Remember, there is no easy way or short cut for these.

Concepts to Revise :
Trees
Binary Search Trees
Tree basic operation algorithms
Balanced Trees
Complexities

References :

Question 5: Truth Table

5. In the following truth table, V = 1 if and only if the input is valid.

What function does the truth table represent?
(A) Priority encoder
(B) Decoder
(C) Multiplexer
(D) Demultiplexer

Answer : (A)

Explanation :
TBD

Concepts to Revise :

References :

Question 4: 2's Compliment of Binary Numbers

4. The smallest integer that can be represented by an 8-bit number in 2’s complement form is 

(A) -256 

(B) -128 

(C) -127 

(D) 0

Answer : (B)

Explanation :

Range for n-bit 2's compliment number is : -2^(n-1) to  +(2^(n-1))-1. So, for n-bit number the range would be -128 to +127. So, the answer is B.

Elimination Method
Lets try to see if we can represent the numbers in 2's compliment form.

-256 :  We will need 9 bits to represent 256 in basic unsigned form. So, it is out of question to represent -256 in 2's compliment form in 8 bits.

-128 :
      128 = 1000 0000 => 1000 0000 (in 2's compliment form). So, it looks clear that we can represent 128 in 2's compliment form.

-127 = 0111 1111 => 1000 0001 (in 2's compliment form).

0 = 0000 0000 => 0000 0000 (in 2's compliment form).

So, the lowest number is -128.

Alternate Method

In 2's compliment form, MSB will be 1 for negative numbers. So the number format possible will be
1XXX XXXX

The boundary numbers we can think about would be
1111 1111 or 1000 0000

1111 1111(in 2's compliment) would be => - 0000 0001 i.e., -1
1000 0000 (in 2's compliment) would be => - 1000 0000 i.e., -128

Concepts to Revise
1. What is 2's compliment ? Wiki
2. How to find 2's compliment of a number ?
3. How to find a number corresponding to 2's compliment number ?
4. What are compliments ? Why they are used ?

References
Read Chapter 1(Binary Systems) from Morris Mano.

Question 3 : On Matrix Det

3.                                                                          |1    x    x^2|

    Which one of the following does NOT equal           |1    y    y^2|

                                                                             |1    z    z^2|

     | 1    x(x+1)     x+1|

A. | 1    y(y+1)     y+1|
     | 1    z(z+1)      z+1|

     | 1    x+1     x^2+1|
B. | 1    y+1     y^2+1|
     | 1    z+1     z^2+1|

     | 0    x-y     x^2-y^2|
C. | 0    y-z     y^2-z^2|
     | 1    z               z^2|

     | 2    x+y     x^2 + y^2|
D. | 2    y+z     y^2 + z^2|
     | 1    z                   z^2|

Answer : (A)

Explanation :

Detailed Method
TBD (Using row/column manipulations).


Substitution Method :
Lets assume x = 1, y = 2, z = 3.

Original Matrix Det
|1    x    x^2|    |  1  1  1  |

|1    y    y^2| = |  1  2  4  | = 1(18-12)-1(9-4)+1(3-2) = 6-5+1 = 2

|1    z    z^2|     |  1  3  9 |

Option A matrix Det
| 1    x(x+1)     x+1|       | 1    2   2 |
| 1    y(y+1)     y+1|  =   | 1    6   3 | = -2
| 1    z(z+1)      z+1|       | 1  12  4 |

The det of this matrix is not equal to det of original matrix, so answer is A.

But, anyway, lets calculate the det of other matrices for safety.
     | 1    x+1     x^2+1|        | 1   2   2  |
B. | 1    y+1     y^2+1| =     | 1   3   5  | = 2
     | 1    z+1     z^2+1|        | 1   4   10|

     | 0    x-y     x^2-y^2|      |  0   -1   -3  |
C. | 0    y-z     y^2-z^2| =    |  0   -1   -5 | = 2
     | 1    z               z^2|       |  1    3     9 |

     | 2    x+y     x^2 + y^2|      | 2   3   5  |
D. | 2    y+z     y^2 + z^2| =   | 2   5   13| = 2
     | 1    z                   z^2|      | 1   3    9 |

you can clearly see Det of other matrices is 2, which is equal to det of the original matrix in the question.

Question 2: Probability

2. Suppose p is number of cars per minute passing through a certain road junction between 5 PM and 6PM, and p has a Poisson distribution with mean 3. What is the probability of observing fewer than 3 cars during any given minute in this interval?

A. 8/(2e^3)
B. 9/(2e^3)
C. 17/(2e^3)
D. 26/(2e^3)

Ans : (C)

Explanation :

Formula for Poisson distribution P(p = n) = (e^-u)(u^n)/n!

Here, Mean is 3. i.e., u = 3

Probability of observing fewer than 3 cars is = P(p < 3)
P(p < 3) =  P(p = 0) + P(p = 1) + P(p = 2)
              = (e^-3) (3^0)/0! + (e^-3) (3^1)/1! + (e^-3) (3^2)/2!
              = (e^-3) + (e^-3)(3)/(1) + (e^-3) (9)/(2)
              = (1+3+(9/2)) (e^-3)
              = 17/2e^3

Hence the answer is C.

Question 1

1. A binary operation ⊕ on a set of integers is defined as x ⊕ y = x^2 + y^2 . Which one of the following statements is TRUE about ⊕ ?

(A) Commutative but not associative
(B) Both commutative and associative 
(C) Associative but not commutative
(D) Neither commutative nor associative

Answer : A

Explanation :

Is this commutative ?
          x ⊕ y = x^2 + y^2 = y^2 + x^2 = y ⊕ x
         Since  x ⊕ y = y ⊕ x, it is commutative.

Is this associative ?
    That means is (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z ) ?
    Lets take an example: x = 1, y = 2, z = 3
       (x ⊕ y) ⊕ z = (1 + 4) ⊕ 3 = 5 ⊕ 3 = 25 + 9 = 34
       x ⊕ (y ⊕ z ) = 1 ⊕ (4 + 9) = 1 ⊕ 13 = 1 + 169 = 170

    So,  (x ⊕ y) ⊕ z != x ⊕ (y ⊕ z ). That means, it is not associative.

Now lets look at the answers and see which one makes sense.

(A) Commutative but not associative : This makes sense according to our analysis till now.
(B) Both commutative and associative  : This does not make sense, since it is not associative.
(C) Associative but not commutative : This does not make sense, since it is commutative.
(D) Neither commutative nor associative : This does not makes sense, since it is commutative.

References :