CS and IT Gate 2016 Set-1 Questions with Answer

Given:
Proposed code for process P_i:
<code>c[i]=1; t[i] = pmax(t[0],...,t[n-1])+1; c[i]=0;</code>
<code>for every j != i in {0,...,n-1} {</code>
<code> while (c[j]);</code>
<code> while (t[j] != 0 && t[j] <= t[i]);</code>
<code>}</code>
<code>Critical Section;</code>
<code>t[i]=0;</code>
<code>Remainder Section;</code>
To find:
Which statement among the given options is TRUE.
Solution:
Let me first understand what happens when multiple processes try to enter the critical section.
Notice the condition in the second while loop: <code>while (t[j] != 0 && t[j] <= t[i]);</code>.
In Lamport's Bakery algorithm, ties are broken using process IDs: <code>(t[j] < t[i]) || (t[j] == t[i] && j < i)</code>.
Here, there is no tie-breaking mechanism with process ID; it just checks <code>t[j] <= t[i]</code>.
Let me test if a deadlock can occur.
Suppose P₀ and P₁ try to enter the critical section concurrently when all tickets are 0.
Both can compute <code>pmax</code> at the same time and get <code>t[0] = 1</code> and <code>t[1] = 1</code>.
Both then set <code>c[0] = 0</code> and <code>c[1] = 0</code>.
Now P₀ executes the loop for j = 1:
<code>c[1]</code> is 0, so the first while loop terminates.
Then it checks <code>while (t[1] != 0 && t[1] <= t[0]);</code>.
Since t[1] = 1 and t[0] = 1, the condition <code>1 <= 1</code> is true, so P₀ gets stuck in the loop.
Similarly, P₁ executes the loop for j = 0:
<code>c[0]</code> is 0, so the first while loop terminates.
It checks <code>while (t[0] != 0 && t[0] <= t[1]);</code>.
Since t[0] = 1 and t[1] = 1, the condition <code>1 <= 1</code> is also true, so P₁ gets stuck in the loop.
Both processes are waiting for each other forever, causing a deadlock.
Since a deadlock is possible:
- Option D ("It cannot cause a deadlock") is FALSE.
- Option C ("The progress condition is satisfied") is FALSE, because a deadlock violates progress.
- Option B ("The bounded wait condition is satisfied") is FALSE, because processes can wait indefinitely due to deadlock.
Now let me verify if Mutual Exclusion holds (Option A).
Suppose two processes P_i and P_k enter the critical section at the same time.
For P_i to enter, it must have passed the check for j = k.
Since P_k has entered or is trying to enter, it sets <code>c[k] = 1</code> while picking its ticket.
P_i waits for <code>c[k] == 0</code> before checking <code>t[k]</code>, so P_i only reads a fully updated <code>t[k]</code>.
For P_i to exit the loop for j = k, it must observe <code>t[k] > t[i]</code>.
By symmetric reasoning, for P_k to exit the loop for j = i, it must observe <code>t[i] > t[k]</code>.
The conditions <code>t[k] > t[i]</code> and <code>t[i] > t[k]</code> cannot both be true at the same time.
Thus, two processes can never be in the critical section simultaneously.
Hence, mutual exclusion is satisfied, meaning at most one process can be in the critical section at any time.
Answer:
(A) At most one process can be in the critical section at any time

Given:
- Initial global variable: a = 3
- Parameter passing: Call by reference
- Scoping rule: Dynamic scoping
- Functions:
void n(x) { x = x * a; print(x); }
void m(y) { a = 1; a = y - a; n(a); print(a); }
void main() { m(a); }
To find:
- The output of the pseudo-code.
Solution:
Okay, let's trace the execution step by step starting from main().
First, main() calls m(a) with the global variable a (which is 3) passed by reference to parameter y.
So, y inside m is an alias/reference to the global variable a (value = 3).
Now entering function m(y):
The first statement is a = 1, which defines a local variable a in m initialized to 1.
Next, evaluating a = y - a:
Since y refers to global a = 3 and local a = 1, we get:
a = 3 - 1 = 2.
So, local a in m now has the value 2.
Now, m calls n(a), passing its local variable a by reference to x.
So, x inside n is an alias/reference to m's local variable a.
Now entering function n(x):
Because dynamic scoping is used, any free variable is resolved by looking back up the calling sequence (call stack).
The caller of n is m, so the identifier a resolves to the local variable a of m, which has the value 2.
The parameter x is also referencing that very same local variable a of m, so x = 2.
Now executing the statement x = x × a:
x = 2 × 2 = 4.
Because x is passed by reference, updating x directly updates the local variable a in m to 4.
Now, printing x gives:
print(x) → 4.
Function n finishes and control returns to m.
Back in m, the next statement is print(a):
Since a was modified by n via reference parameter x, the value of a is now 4.
print(a) → 4.
Therefore, the outputs are 4 and 4.
Answer:
D) 4, 4

Given:
A C function to find the maximum value in an integer array p[] of size n (where n ≥ 1):
Initial indices: a = 0, b = n - 1.
Inside the loop, if p[a] ≤ p[b], we do a = a + 1; otherwise, b = b - 1.
Finally, it returns p[a].
To find:
The missing loop condition.
Solution:
Let me understand what the algorithm is doing here.
We have two pointers, a at the start (index 0) and b at the end (index n - 1).
In each iteration, we compare p[a] and p[b].
If p[a] ≤ p[b], the element at a cannot be the strictly unique maximum, so we can safely eliminate it by incrementing a.
If p[a] > p[b], the element at b is definitely not the maximum, so we eliminate it by decrementing b.
So, in every iteration, the search window [a, b] shrinks by 1.
The maximum element will always remain inside the subarray from index a to b.
We need to stop when the search window contains exactly one element, that is, when a = b.
Once a = b, that single remaining element p[a] is our maximum value.
Therefore, the loop must continue as long as there is more than one element left, which means while a ≠ b (or b != a).
Let's check with an example: n = 1.
Initially a = 0, b = 0.
If the condition is b != a, 0 != 0 is false, the loop doesn't execute at all, and it directly returns p[0], which is correct for a single-element array.
Hence, the correct loop condition is b != a.
Answer:
(D) b != a

Given:
Function prototype: void f(int, short);
Variables declared: int i = 100; short s = 12; short *p = &s;
To find:
The expression that will NOT cause a type checking error when placed in the blank.
Solution:
Let me look at the function declaration first.
The function f takes two arguments: the first of type int, and the second of type short.
It returns void, so it cannot be assigned to any variable.
Now let me check the given variables:
i is of type int.
s is of type short.
p is of type pointer to short (short *).
Let me test each option one by one:
Checking Option A: f(s, *s)
Here, s is an integer type (short), not a pointer. Applying the indirection operator * on s (*s) is invalid and causes a type error.
Checking Option B: i = f(i, s)
The function f returns void. We cannot assign a void expression to an int variable i. This will cause a type error.
Checking Option C: f(i, *s)
Again, s is not a pointer, so *s is an invalid operation.
Checking Option D: f(i, *p)
Here, i is of type int, which matches the first parameter.
p is of type short*, so dereferencing it as *p gives a value of type short, which matches the second parameter.
The function call does not attempt to assign the void return value to anything.
So, this call is completely valid and does not produce any type checking error.
Answer: (D)

Given:
SDTS rules:
S → aA { print 1 }
S → a { print 2 }
A → Sb { print 3 }
Input string: aab
To find:
The output printed by a bottom-up parser.
Solution:
First, let me write down the parse tree that derives the string "aab":
S → a A
A → S b
S → a
Let me trace the shift-reduce steps of the bottom-up parser live on the input "aab$":
Start with an empty stack.
Shift the first 'a'. Stack = [a], Remaining input = ab$
If I reduce this first 'a' to S, the stack becomes [S], but no production rule starts with "S a", so the parser won't reduce here.
Shift the second 'a'. Stack = [a, a], Remaining input = b$
Now, the handle at the top of the stack is the second 'a', which reduces using S → a.
So, reduction 1: S → a. Stack becomes [a, S].
This executes the semantic action: print 2.
Now shifting the next symbol 'b'.
Stack = [a, S, b], Remaining input = $
The handle "Sb" matches the production rule A → Sb.
So, reduction 2: A → Sb. Stack becomes [a, A].
This executes the semantic action: print 3.
Now the handle "aA" matches the production rule S → aA.
So, reduction 3: S → aA. Stack becomes [S].
This executes the semantic action: print 1.
The start symbol S is reached and input is fully consumed, so the parser accepts.
Writing the outputs in sequence: 2 3 1.
Answer: (C) 2 3 1