## Descriptive

Question 6 |

Theory Explanation is given below. |

Question 6 Explanation:

(a) From the question based on possibilities:

L = (0+1)* - (0+1)* (00+11) (0+1)*

(b) i≤j as S→aSAb

There will be always for one a in left and minimum one b in right and A→bA|X can generate any no. of b's including Null, if A is X then i=j and if A is generate any b then j>i. So the condition i≤j is true.

L = (0+1)* - (0+1)* (00+11) (0+1)*

(b) i≤j as S→aSAb

There will be always for one a in left and minimum one b in right and A→bA|X can generate any no. of b's including Null, if A is X then i=j and if A is generate any b then j>i. So the condition i≤j is true.

Question 7 |

Theory Explanation is given below. |

Question 7 Explanation:

(a)

(b)

(b)

Question 9 |

Theory Explanation is given below. |

Question 9 Explanation:

Note: Out of syllabus.

Question 10 |

Theory Explanation is given below. |

Question 10 Explanation:

Note: Out of syllabus.

Question 11 |

Theory Explanation is given below. |

Question 11 Explanation:

(a) Enqueue → push

Dequeue → reverse, pop, reverse

(b) (i) After evaluating 5 2 * 3 4 +

Sol:

7(3+4) 10(5*2)

(ii) After evaluating 5 2 * 3 4 + 5 2

Sol:

25(5*5) 7(3+4) 10(5*2)

(iii) At the end of evaluation

Sol: 80

Dequeue → reverse, pop, reverse

(b) (i) After evaluating 5 2 * 3 4 +

Sol:

7(3+4) 10(5*2)

(ii) After evaluating 5 2 * 3 4 + 5 2

Sol:

25(5*5) 7(3+4) 10(5*2)

(iii) At the end of evaluation

Sol: 80

Question 13 |

Theory Explanation is given below. |

Question 13 Explanation:

(a) (1) f[n-2] != 0

(2) f[n-2];

(3) f[n-2] = +;

(b) The time complexity of the resulting program when computing fib(n) is Θ(n).

(2) f[n-2];

(3) f[n-2] = +;

(b) The time complexity of the resulting program when computing fib(n) is Θ(n).

Question 14 |

Theory Explanation is given below. |

Question 14 Explanation:

Note: Out of syllabus.

Question 15 |

Theory Explanation is given below. |

Question 15 Explanation:

(a) Since it is said that the instruction after branch is not fetched till the branch instruction is completed. So CPI for branch instruction is 5. And for normal instruction CPI is 1.

So total execution time

= (0.2×5 + 0.8×1) × 2ns

= 3.6 ns

(b) Total branch instructions are 20% as given in previous part. In which 80% are conditional and in which 50% of the conditional branch is taken. So total conditional branch instruction which is taken is

50% of 80% of 20%

0.5×0.8×0.2 = 0.08

And 20% of total branch instruction are not conditional means for that branch is necessarily taken. So total unconditional branch instruction is,

0.2×0.2 = 0.04

Hence, total branch instruction which is taken is,

0.08+0.04 = 0.12

Now lets calculate total execution time,

= (0.12×5 + 0.88×1) × 2ns

= 2.96 ns

So total execution time

= (0.2×5 + 0.8×1) × 2ns

= 3.6 ns

(b) Total branch instructions are 20% as given in previous part. In which 80% are conditional and in which 50% of the conditional branch is taken. So total conditional branch instruction which is taken is

50% of 80% of 20%

0.5×0.8×0.2 = 0.08

And 20% of total branch instruction are not conditional means for that branch is necessarily taken. So total unconditional branch instruction is,

0.2×0.2 = 0.04

Hence, total branch instruction which is taken is,

0.08+0.04 = 0.12

Now lets calculate total execution time,

= (0.12×5 + 0.88×1) × 2ns

= 2.96 ns

Question 16 |

Theory Explanation is given below. |

Question 16 Explanation:

(a) At set(7) ⇒ count = 1

then q[1] = 7; p[7] = 1

At set(3) ⇒ count = 2

then q[2] = 3; p[3] = 2

At set[9] ⇒ count = 3

then q[3] = 9; p[9] = 3;

(b) "The first count elements of

(c) If set(i) has not been celled for some i, then regardless of what p[i] contains, when we call is set(i) then

if (q[p[i]] ≠ i)

return false;

Will always execute, because if set(i) is not called then p[i]≠count(any) and for then same count q[count]≠i.

So if statement will be true and will return false.

then q[1] = 7; p[7] = 1

At set(3) ⇒ count = 2

then q[2] = 3; p[3] = 2

At set[9] ⇒ count = 3

then q[3] = 9; p[9] = 3;

(b) "The first count elements of

__array q__contains value i such that set (i) has been called".(c) If set(i) has not been celled for some i, then regardless of what p[i] contains, when we call is set(i) then

if (q[p[i]] ≠ i)

return false;

Will always execute, because if set(i) is not called then p[i]≠count(any) and for then same count q[count]≠i.

So if statement will be true and will return false.

Question 17 |

Theory Explanation is given below. |

Question 17 Explanation:

(a) Since swaps are done between adjacent elements only. So this is nothing but Bubble sort.

In Bubble sort maximum no. of swap is done when the elements are in non-increasing order, i.e.,

{2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0}

Pass 1 - 9 swaps

Pass 2 - 9 swaps

Pass 3 - 9 swaps

Pass 4 - 4 swaps

Pass 5 - 4 swaps

Pass 6 - 4 swaps

Pass 7 - 4 swaps

Pass 8 - 4 swaps

Pass 9 - 0 swaps

Pass 10 - 0 swaps

Pass 11 - 0 swaps

Total swaps = 47

(b) Same as part (a)

(a)

While traversing the tree we will get value,

E.val = 12

(b) While traversing the parse tree we will get 10 Reductions.

In Bubble sort maximum no. of swap is done when the elements are in non-increasing order, i.e.,

{2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0}

Pass 1 - 9 swaps

Pass 2 - 9 swaps

Pass 3 - 9 swaps

Pass 4 - 4 swaps

Pass 5 - 4 swaps

Pass 6 - 4 swaps

Pass 7 - 4 swaps

Pass 8 - 4 swaps

Pass 9 - 0 swaps

Pass 10 - 0 swaps

Pass 11 - 0 swaps

Total swaps = 47

(b) Same as part (a)

(a)

While traversing the tree we will get value,

E.val = 12

(b) While traversing the parse tree we will get 10 Reductions.

Question 20 |

Theory Explanation is given below. |

Question 20 Explanation:

(a)

The function is self dual because

→ There is no mutually exclusive pair.

→ No. of minterms = No. of maxterms

(b)

Write Minimal POS.

The function is self dual because

→ There is no mutually exclusive pair.

→ No. of minterms = No. of maxterms

(b)

Write Minimal POS.

There are 22 questions to complete.