# GATE Computer Science and Information Technology Solved Paper 2013 - Part 4

31.       Consider the following function:
int unknown int n {
int i, j, k=0;
for(i=n/2; i≤n; i++)
for(j=2; j≤n; j=j*2)
k=k+n/2;
return (k);
}
The return value of the function is
(A) Θ(n2)            (B) Θ(n2logn)
(C) Θ(n3)            (D) Θ(n3logn)
32.       Consider the following languages.
L1={0p1q0r|p,q,r≥0}
L2={0p1q0r|p,q,r≥0,pr}
Which one of the following statements is FALSE?
(A) L2 is context–free
(B) L1∩L2 is context–free
(C) Complement of L2 is recursive
(D) Complement of L1 is context–free but not regular
33.       Consider the DFA A given below.
Which of the following are FALSE?
1. Complement of L(A) is context–free
2. L(A)=L((11*0+0)(0+1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.
(A) 1 and 3 only           (B) 2 and 4 only
(C) 2 and 3 only           (D) 3 and 4 only
34.       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
35.       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) ∏snamecourseno=107percent>90(RegistrationStudents))
(III) {T|S ϵ Students, R ϵ Registration(S.rollno=R.rollno
R.courseno=107R.percent>90T.sname=S.name)}
(IV) {<SN>|SRRP(<SR,SN>ϵStudents<SR,107,RP>ϵRegistrationRP>90)}
(A) I, II, III and IV           (B) I, II and III only
(C) I, II and IV only       (D) II, III and IV only

36.       Determine the maximum length of cable (in km) for transmitting data at a rate of 500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal speed in the cable to be 2,00,000 km/s
(A) 1       (B) 2    (C) 2.5           (D) 5
37.       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
38.       The following figure represents access graphs of two modules M1 and M2. The filled circles represent methods and the unfilled circles represent attributes. If method m is moved to module M2 keeping the attributes where they are, what can we say about the average cohesion and coupling between modules in the system of two modules?
(A) There is no change.
(B) Average cohesion goes up but coupling is reduced
(C) Average cohesion goes down and coupling also reduces
(D) Average cohesion and coupling increase
39.       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;                                Process 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(R);
P(S);
}
(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);
}
40.    Consider the following two sets of LR(1) items of an LR(1) grammar
X→c.X, c/d    X→c.X, \$
X→.cX, c/d    X→.cX, \$
X→.d, c/d       X→.d, \$
Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different
2. Can be merged but will result in S–R conflict
3. Can be merged but will result in R–R conflict
4. Cannot be merged since goto on c will lead to two different sets
(A) 1 only                      (B) 2 only
(C) 1 and 4 only           (D) 1, 2, 3 and 4