# CS GATE 2012 (Test 1)

Tag: cs gate 2012
Q.1
Which one of the following options is the closest in meaning to the word given below? Mitigate
A. Diminish
B. Divulge
C. Dedicate
D. Denote
Explaination / Solution:
No Explaination.

Workspace
Report
Q.2
Wanted Temporary, Part-time persons for the post of Field Interviewer to conduct personal interviews to collect and collate economic data. Requirements: High School-pass, must be available for Day, Evening and Saturday work. Transportation paid, expenses reimbursed. Which one of the following is the best inference from the above advertisement?
A. Gender-discriminatory
B. Xenophobic
C. Not designed to make the post attractive
D. Not gender-discriminatory
Explaination / Solution:

Workspace
Report
Q.3
The protocol data unit (PDU) for the application layer in the Internet stack is
A. Segment
B. Datagram
C. Message
D. Frame
Explaination / Solution:

The PDU for Datalink layer, Network layer , Transport layer and Application layer are frame, datagram, segment and message respectively.

Workspace
Report
Topic: Databases Tag: CS GATE 2012
Q.4
Which of the following is TRUE?
A. Every relation is 3NF is also in BCNF
B. A relation R is in 3NF if every non-prime attribute of R is fully functionally dependent on every key of R
C. Every relation in BCNF is also in 3NF
D. No relation can be in both BCNF and 3NF
Explaination / Solution:

Option A is false since BCNF is stricter than 3NF (it needs LHS of all FDs should be candidate key for 3NF condition) Option B is false since the definition given here is of 2NF Option C is true, since for a relation to be in BCNF it needs to be in 3NF, every relation in BCNF satisfies all the properties of 3NF. Option D is false, since if a relation is in BCNF it will always be in 3NF.

Workspace
Report
Q.5
The amount of ROM needed to implement a 4 bit multiplier is
A. 64 bits
B. 128 bits
C. 1 kbits
D. 2 kbits
Explaination / Solution:

For a 4 bit multiplier there are 24 × 24 = 28 = 256 combinations.
Output will contain 8 bits.
So the amount of ROM needed is 28 ×8 bits = 2Kbits

Workspace
Report
Q.6
Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is context-free language, then, is  also context-free?
3) If L is regular language, then, is  also regular?
4) If L is recursive language, then, is  also recursive?
A. 1,2,3,4
B. 1,2
C. 2,3,4
D. 3,4
Explaination / Solution:

CFL’s are not closed under complementation. Regular and recursive languages are closed under complementation.

Workspace
Report
Q.7
For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, \$ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S
The appropriate entries for E1, E2, and E3 are
A. E1: S →aAbB, A →S
E2: S →bAaB, B → S
E3: B →S
B. E1: S →aAbB, S → ε
E2: S →bAaB, S → ε
E3: S → ε
C. E1: S →aAbB, S → ε
E2: S →bAaB, S → ε
E3: B →S
D. E1: A →S, S→ ε
E2: B →S, S → ε
E3: B →S
Explaination / Solution:

Workspace
Report
Topic: Algorithms Tag: CS GATE 2012
Q.8
Consider the following C code segment:
int a, b, c = 0;
void prtFun(void);
main( )
{ static int a = 1;            /* Line 1 */
prtFun( );
a + = 1;
prtFun( )
printf(“\n %d %d “, a, b);
}
void prtFun(void)
{ static int a=2;               /* Line 2 */
int b=1;
a+=++b;
printf(“\n %d %d “, a, b);
What output will be generated by the given code segment?
A. 3 1
4 1
4 2
B. 4 2
6 1
6 1
C. 4 2
6 2
2 0
D. 3 1
5 2
5 2
Explaination / Solution:

Workspace
Report
Q.9
Consider an instance of TCP’s Additive Increase Multiplicative decrease (AIMD) algorithm where the window size at the start of the slow start phase is 2 MSS and the threshold at the start of the first transmission is 8 MSS. Assume that a timeout occurs during the fifth transmission. Find the congestion window size at the end of the tenth transmission.
A. 8MSS
B. 14MSS
C. 7MSS
D. 12MSS
Explaination / Solution:

Given, initial threshold = 8
Time = 1, during 1st transmission,Congestion window size = 2 (slow start phase)
Time = 2, congestion window size = 4 (double the no. of acknowledgments)
Time = 3, congestion window size = 8 (Threshold meet)
Time = 4, congestion window size = 9, after threshold (increase by one Additive increase)
Time = 5, transmits 10 MSS, but time out occurs congestion window size = 10
Hence threshold = (Congestion window size)/2 = 10/2 = 5
Time = 6, transmits 2
Time = 7, transmits 4
Time = 8, transmits 5 (threshold is 5)
Time = 9, transmits 6, after threshold (increase by one Additive increase)
Time = 10, transmits 7
∴ During 10th transmission, it transmits 7 segments hence at the end of the tenth transmission the size of congestion window is 7 MSS.

Workspace
Report
Q.10
Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
A. full: (REAR+1) mod n==FRONT empty: REAR ==FRONT
B. full:(REAR+1)mod n==FRONT empty: (FRONT+1)mod n==REAR
C. full: REAR==FRONT empty: (REAR+1) mod n ==FRONT
D. full:(FRONT+1)mod n==REAR empty: REAR ==FRONT
Explaination / Solution:

The counter example for the condition full : REAR = FRONT is
Initially when the Queue is empty REAR=FRONT=0 by which the above full condition is satisfied which is false
The counter example for the condition full : (FRONT+1)mod n =REAR is
Initially when the Queue is empty REAR=FRONT=0 and let n=3, so after inserting one element REAR=1 and FRONT=0, at this point the condition full above is satisfied, but still there is place for one more element in Queue, so this condition is also false
The counter example for the condition empty : (REAR+1)mod n = FRONT is
Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here
The counter example for the condition empty : (FRONT+1)mod n =REAR is
Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here

Workspace
Report