CS GATE 2013 (Test 5)



Tag: cs gate 2013
Q.1
After several defeats in wars, Robert Bruce went in exile and wanted to commit suicide. Just before committing suicide, he came across a spider attempting tirelessly to have its net. Time and again, the spider failed but that did not deter it to refrain from making attempts. Such attempts by the spider made Bruce curious. Thus, Bruce started observing the nearimpossible goal of the spider to have the net. Ultimately, the spider succeeded in having its net despite several failures. Such act of the spider encouraged Bruce not to commit suicide. And then, Bruce went back again and won many a battle, and the rest is history. Which one of the following assertions is best supported by the above information?
A. Failure is the pillar of success
B. Honesty is the best policy
C. Life begins and ends with adventures
D. No adversity justifies giving up hope
Answer : Option D
Explaination / Solution:
No Explaination.


Workspace
Report
Q.2
 Match the problem domains in Group I with the solution technologies in Group II
              Group I                                                                     Group II
(p) Services oriented computing                                      (1) Interoperability
(q) Heterogeneous communicating systems                    (2) BPMN
(R) Information representation                                         (3) Publish-find bind
(S) Process description                                                    (4) XML
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 : Option C
Explaination / Solution:
No Explaination.


Workspace
Report
Topic: Databases Tag: CS GATE 2013
Q.3
Using public key cryptography, X adds a digital signature σ to message M, encrypts , 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’s public key
Answer : Option D
Explaination / Solution:


Encryption: Source has to encrypt with its p r ivate key for formin g Digital signature for Authentication. source has to encrypt the <M, σ > with Y ' s public key to send it confidentially
Decryption: Destination Y has to decrypt first with its private key, then decrypt using source public key

Workspace
Report
Q.4
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 : Option D
Explaination / Solution:
No Explaination.


Workspace
Report
Q.5
Consider the languages L= Φ and L= {a} . Which one of the following represents L1 L2* UL1* ? 
A. {∈}
B. Φ
C. a *
D. {ε, a}
Answer : Option A
Explaination / Solution:
No Explaination.


Workspace
Report
Topic: Algorithms Tag: CS GATE 2013
Q.6
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
A. Θ(n2)
B. Θ(nlog n)
C. Θ(n3)
D. Θ(nlog n)
Answer : Option C
Explaination / Solution:

Bellman-ford time complexity: Θ(|V| × |E|)
For complete graph:  |E| = n(n - 1)/2
|V| = n
Θ(n × (n(n - 1)/2) = Θ(n3)

Workspace
Report
Q.7
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(1)
B. O(log n)
C. O(n)
D. O(n log n)
Answer : Option C
Explaination / Solution:

For skewed binary search tree on n nodes, the tightest upper bound to insert a node is O(n)

Workspace
Report
Q.8
What is the return value of f (p,p) if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.
int f (int & x, int c) {
c = c - 1;
if (c = 0) return 1;
x = x + 1;
return f (x,c)* x;
}
A. 3024
B. 6561
C. 55440
D. 161051
Answer : Option B
Explaination / Solution:



Workspace
Report
Q.9
The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed
void find _ and _ replace (char * A, char *oldc, char * newc) {
for (int i=0; i<5; i++)
for (int j=0; j<3; j++)
if (A[i] == oldc[j])          A[i] = newc[j];
}
The procedure is tested with the following four test cases 
(1) oldc = "abc", newc = "dab"              (2) oldc = "cde", newc = "bcd"
(3) oldc = "bca", newc = "cda"              (4) oldc = "abc", newc = "bac"
 The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?
A. Only one
B. Only two
C. Only three
D. All four
Answer : Option B
Explaination / Solution:

 Flaw in this given procedure is that one character of Array ‘A’ can be replaced by more than one character of newc array, which should not be so.Test case (3) and (4) identifies this flaw as they are containing ‘oldc’ and ‘newc’ array characters arranged in specific manner. Following string can reflect flaw, if tested by test case (3).

Likewise single character ‘b’ in A is replaced by ‘c’ and then by ‘d’. Same way test case (4) can also catch the flaw  

Workspace
Report
Q.10
Consider an instruction pipeline with five stages without any branch prediction: Fetch Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute Instruction (EI) and Write Operand (WO). The stage delays for FI, DI, FO, EI and WO are 5 ns, 7 ns, 10 ns, 8 ns and 6 ns, respectively. There are intermediate storage buffers after each stage and the delay of each buffer is 1 ns. A program consisting of 12 instructions I1, I2 ,I3 ,......I12 is executed in this pipelined processor. Instruction I4 is the only branch instruction and its branch target is I9 . If the branch is taken during the execution of this program, the time (in ns) needed to complete the program is  
A. 132
B. 165
C. 176
D. 328
Answer : Option B
Explaination / Solution:

Clock period=Maximum stage delay+ overhead (Buffer) =10+1=11 ns
Assume FI-1, DI-2, FO-3, EI-4, WO-5 

So number of clocks required to complete the program is = 15 clocks and time taken is = 15 ×11 ns=165 ns. 

Workspace
Report