# CS GATE 2013 (Test 1)

Tag: cs gate 2013
Q.1
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
Explaination / Solution:

Nadir in the lowest point on a curve

Workspace
Report
Topic: Arithmetic Tag: CS GATE 2013
Q.2
What will be the maximum sum of 44, 42, 40, ... ?
A. 502
B. 504
C. 506
D. 500
Explaination / Solution:

The maximum sum is the sum of 44, 42,- - - - -2.
The sum of ‘n’ terms of an AP
= n/2 [2a+(n-1)d]
In this case, n = 22, a = 2 and d = 2
∴ Sum = 11[4+21×2] = 11×46 = 506

Workspace
Report
Q.3
In an IPv4 datagram, the M bit is 0, the value of HLEN is 10, the value of total length is 400 and the fragment offset value is 300. The position of the datagram, the sequence numbers of the first and the last bytes of the payload, respectively are
A. Last fragment, 2400 and 2789
B. First fragment, 2400 and 2759
C. Last fragment, 2400 and 2759
D. Middle fragment, 300 and 689
Explaination / Solution:

M= 0 – Means there is no fragment after this, i.e. Last fragment
HLEN=10 - So header length is 4×10=40, as 4 is constant scale factor
Fragment Offset = 300, that means 300×8 Byte = 2400 bytes are before this last fragment
So the position of datagram is last fragment
Sequence number of First Byte of Payload = 2400 (as 0 to 2399 Sequence no are used)
Sequence number of Last Byte of Payload = 2400+360-1=2759

Workspace
Report
Topic: Databases Tag: CS GATE 2013
Q.4
Consider the following relational schema.
Students(rollno: integer, sname: string)
Courses(courseno: integer, cname: string)
Registration(rollno: integer, courseno; integer, percent: real)
Which of the following queries are equivalent to this query in English?
“Find the distinct names of all students who score more than 90% in the course numbered 107”
(I)  SELECT DISTINCT S.sname FROM Students as S, Registration as R WHERE R.rollno=S.rollno AND R.Courseno=107 AND R.percent>90
(II)
(III) {T | ∃S∈ Students, ∃R∈ Registration (S.rollno = R.rollno ∧ R.courseno = 107 ∧ R.percent > 90 ∧ T.sname = S.name)}
(IV)
A. I, II, III and IV
B. I, II and III only
C. I, II and IV only
D. II, III and IV only
Explaination / Solution:

Four queries given in SQL, RA, TRC and DRC in four statements respectively retrieve the required information.

Workspace
Report
Q.5
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have almost two source operands and one destination operand.
Assume that all variables are dead after this code segment
c = a + b;
d = c * a;
e = c + a;
x = c *c;
if (x > a) {
y = a * a;
}
else {
d = d * d;
e = e * e;
}
Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?
A. 0
B. 1
C. 2
D. 3
Explaination / Solution:

After applying the code motion optimization the statement d=c*a; and e=c+a; can be moved down to else block as d and e are not used anywhere before that and also value of a and c is not changing.

In the above code total number of spills to memory is 1

Workspace
Report
Q.6
Which of the following is/are undecidable?
1. G is a CFG. Is L (G) = Φ?
2. G is a CFG. IS L (G) =  Σ*?
3. M is a Turning machine. Is L(M) regular?
4. A is a DFA and N is a NFA. Is L (A) = L (N) ?
A. 3 only
B. 3 and 4 only
C. 1, 2 and 3 only
D. 2 and 3 only
Explaination / Solution:

There is an algorithm to check whether the given CFG is empty, finite or infinite and also to convert NFA to DFA hence 1 and 4 are decidable

Workspace
Report
Topic: Algorithms Tag: CS GATE 2013
Q.7
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
Explaination / Solution:

The given scheduling definition takes two parameters, one is dynamically assigned process priority and the other is ‘T’ time unit to re-evaluate the process priorities. This dynamically assigned priority will be deciding processes order in ready queue of round robin algorithm whose time quantum is same as ‘T’ time units. As all the processes are arriving at the same time, they will be given same priority but soon after first ‘T’ time burst remaining processes will get higher priorities

Workspace
Report
Q.8
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(n2
Explaination / Solution:
No Explaination.

Workspace
Report
Q.9
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.
Pr ocess X;                                              Pr ocess Y;
private i;                                                   private i;
for(i = 0; i<n; i++){                                      for(i = 0; i<n; i++){
a[i] = f(i);                                                      EntryY(R, S);
ExitX(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 (S);
P (R);
}
C. ExitX (R, S) {
P (S);
V (R);
EntryY (R, S) {
V (S);
P (R);
}
D. ExitX (R, S) {
V (R);
P (S);
EntryY (R, S) {
V (S);
P (R);
}
Explaination / Solution:

For computing both the array a[] and b[], first element a[i] should be computed using which b[i] can be computed. So process X and Y should run in strict alteration manner, starting with X. This requirement meets with implementation of ExitX and EntryY given in option C.

Workspace
Report
Q.10
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"
If array A is made to hold the string “abcde”, which of the above four test cases will be successful in exposing the flaw in this procedure?
A. None
B. 2 only
C. 3 and 4 only
D. 4 only