GATE CSE 2012
Q22.
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. \varepsilon is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.S\rightarrow aAbB|bAaB|\varepsilon A\rightarrow S B\rightarrow S The FIRST and FOLLOW sets for the non-terminals A and B areQ23.
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. \varepsilon is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.S\rightarrow aAbB|bAaB|\varepsilon A\rightarrow S B\rightarrow S The appropriate entries for E1, E2, and E3 areQ24.
The bisection method is applied to compute a zero of the function f(x) = x^{4}-x^{3}-x^{2}-4 in the interval [1,9]. The method converges to a solution after _____iterations.Q26.
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal toQ27.
Suppose a fair six-sided die is rolled once. If the value on the die is 1, 2, or 3, the die is rolled a second time. What is the probability that the sum total of values that turn up is at least 6?Q28.
Consider a random variable X that takes values +1 and -1 with probability 0.5 each. The values of the cumulative distribution function F(x) at x = -1 and +1 areQ29.
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available. AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1; } ReleaseLock(L){ L = 0; } This implementationQ30.
What is the correct translation of the following statement into mathematical logic? "Some real numbers are rational"