## GATE 2000

Question 1 |

The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from some same suit is

3 | |

8 | |

9 | |

12 |

No. of suits = 4(P)

Apply pigeon hole principal.

Then number of pigeons = n

floor [(n-1)/P] + 1 = 3

floor [(n-1)/P] = 2

floor [(n-1)] = 8

floor (n) = 8 + 1

n ≥ 9

Minimum no. of cards, n = 9

Question 2 |

An n x n array v is defined as follows:

v[i,j] = i-j for all i,j, 1 ≤ i ≤ n, 1 ≤ j ≤ n

The sum of the elements of the array v is

0 | |

n -1 | |

n ^{2} - 3n + 2 | |

n ^{2} (n+1)/2 |

Add i

^{th}row and j

^{th}column if we zero, apply to all row and their corresponding column the total becomes zero.

Question 3 |

The determinant of the matrix is

is:

4 | |

0 | |

15 | |

20 |

Question 4 |

Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

S ⊂ T | |

T ⊂ S | |

S = T | |

S ∩ T = ɸ |

Question 5 |

Let L denotes the language generated by the grammar S → 0S0/00.

Which of the following is true?

L = 0 ^{+} | |

L is regular but not 0 ^{+} | |

L is context free but not regular | |

L is not context free |

^{+}.

Question 6 |

The number 43 in 2’s complement representation is

01010101 | |

11010101 | |

00101011 | |

10101011 |

Question 7 |

To put the 8085 microprocessor in the wait state

lower the HOLD input | |

lower the READY input | |

raise the HOLD input | |

raise the READY input |

Question 8 |

Comparing the time T1 taken for a single instruction on a pipelined CPU with time T2 taken on a non-pipelined but identical CPU, we can say that

T1 ≤ T2 | |

T1 ≥ T2 | |

T1 < T2 | |

T1 is T2 plus the time taken for one instruction fetch cycle |

__PIPELINING SYSTEM__:

Pipelining is an implementation technique where multiple instructions are overlapped in execution. It has a high throughput (amount of instructions executed per unit time). In pipelining, many instructions are executed at the same time and execution is completed in fewer cycles. The pipeline is filled by the CPU scheduler from a pool of work which is waiting to occur. Each execution unit has a pipeline associated with it, so as to have work pre-planned. The efficiency of pipelining system depends upon the effectiveness of CPU scheduler.

__NON- PIPELINING SYSTEM__:

All the actions (fetching, decoding, executing of instructions and writing the results into the memory) are grouped into a single step. It has a low throughput.

Only one instruction is executed per unit time and execution process requires more number of cycles. The CPU scheduler in the case of non-pipelining system merely chooses from the pool of waiting work when an execution unit gives a signal that it is free. It is not dependent on CPU scheduler.

Question 9 |

The 8085 microprocessor responds to the present of an interrupt

as soon as the TRAP pin becomes ‘high’ | |

by checking the TRAP pin for ‘high’ status at the end of each instruction each | |

by checking the TRAP pin for ‘high’ status at the end of the execution of each instruction | |

by checking the TRAP pin for ‘high’ status at regular intervals |

Question 10 |

The most appropriate matching for the following pairs

X: Indirect addressing 1 : Loops Y: Immediate addressing 2 : Pointers Z: Auto decrement addressing 3: Constants

is

X – 3 Y – 2 Z - 1 | |

X – 1 Y – 3 Z - 2 | |

X – 2 Y – 3 Z - 1 | |

X – 3 Y – 1 Z - 2 |

__Indirect addressing__:

Indirect addressing means that the address of the data is held in an intermediate location so that the address is first 'looked up' and then used to locate the data itself.

__Immediate addressing__:

Immediate Addressing. An immediate operand has a constant value or an expression. When an instruction with two operands uses immediate addressing, the first operand may be a register or memory location, and the second operand is an immediate constant.

Auto increment or decrements can be one by using loops.

Question 11 |

The following C declarations

struct node { int i; float j; }; struct node *s[10];

define s to be

An array, each element of which is a pointer to a structure of type node | |

A structure of 2 fields, each field being a pointer to an array of 10 elements | |

A structure of 3 fields: an integer, a float, and an array of 10 elements | |

An array, each element of which is a structure of type node |

Question 12 |

The most appropriate matching for the following pairs

X: m=malloc(5); m= NULL; 1: using dangling pointers Y: free(n); n->value=5; 2: using uninitialized pointers Z: char *p; *p = ’a’; 3. lost memory

is:

X – 1 Y – 3 Z – 2 | |

X – 2 Y – 1 Z – 3 | |

X – 3 Y – 2 Z – 1 | |

X – 3 Y – 1 Z – 2 |

Y → n is pointer to invalid memory, a making it as a dangling pointer.

Z → p is not initialized.

p = malloc (size of(char))p = malloc (size of(char)); should have been used before assigning 'aa' to ∗p.

Question 13 |

The most appropriate matching for the following pairs

X: depth first search 1: heap Y: breadth-first search 2: queue Z: sorting 3: stack

is

X – 1 Y – 2 Z – 3 | |

X – 3 Y – 1 Z – 2 | |

X – 3 Y – 2 Z – 1 | |

X – 2 Y – 3 Z – 1 |

Queue is used in breadth-first search.

Heap is used in heap.

Question 14 |

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

(1 2 (4 5 6 7)) | |

(1 (2 3 4) 5 6) 7) | |

(1 (2 3 4) (5 6 7)) | |

(1 (2 3 NULL) (4 5)) |

(Proper Representation)

Question 15 |

Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. Which of the following statements is true?

t(n) is O(1) | |

n ≤ t(n) ≤ n log _{2} n | |

n log _{2} n ≤ t(n) < (n/2) | |

t(n) = (n/2) |

Question 16 |

Aliasing in the context of programming languages refers to

multiple variables having the same memory location | |

multiple variables having the same value | |

multiple variables having the same identifier | |

multiple uses of the same variable |

Question 17 |

Consider the following C declaration

struct { short s [5] union { float y; long z; } u; } t;

Assume that objects of the type short, float and long occupy 2 bytes, 4 bytes and 8 bytes, respectively. The memory requirement for variable t, ignoring alignment considerations, is

22 bytes | |

14 bytes | |

18 bytes | |

10 bytes |

max[float, long] = max [4, 8] = 8

Total = short[5] + max[float,long] = 10 + 8 = 18

Question 18 |

The number of tokens in the following C statement.

printf("i = %d, &i = %x", i, &i);

is

3 | |

26 | |

10 | |

21 |

(i) Keyword

(ii) Identifier

(iii) Constant

(iv) Variable

(v) String

(vi) Operator

Print = Token 1

( = Token 2

"i=%d%x" = Token 3 [Anything inside " " is one Token]

, = Token 4

i = Token 5

, = Token 6

& = Token 7

i = Token 8

) = Token 9

; = Token 10

Here, totally 10 Tokens are present in the equation.

Question 19 |

Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.

Leftmost derivation | |

Leftmost derivation traced out in reverse | |

Rightmost derivation | |

Rightmost derivation traced out in reverse |

Bottom-Up parser - Reverse of rightmost derivation

Question 20 |

Which of the following need not necessarily be saved on a context switch between processes?

General purpose registers | |

Translation look-aside buffer | |

Program counter | |

All of the above |

Question 21 |

Let m[0] … m[4] be mutexes (binary semaphores) and P[0] … P[4] be processes. Suppose each process P[i] executes the following:

wait (m[i]); wait(m[(i+1) mode 4]); ------ release (m[i]); release (m[(i+1)mod 4]);

This could cause:

Thrashing | |

Deadlock | |

Starvation, but not deadlock | |

None of the above |

Question 22 |

B^{+}-trees are preferred to binary trees in databases because

Disk capacities are greater than memory capacities | |

Disk access is much slower than memory access | |

Disk data transfer rates are much less than memory data transfer rates | |

Disks are more reliable than memory |

^{+}trees it is easy to reduce the number of last level access from the disk when the disk size is too large.

Question 23 |

Given the relations

employee (name, salary, deptno) and department (deptno, deptname, address)

Which of the following queries cannot be expressed using the basic relational algebra operations (σ, π, ×, ⋈, ∪, ∩, -)?

Department address of every employee | |

Employees whose name is the same as their department name | |

The sum of all employees’ salaries | |

All employees of a given department |

Question 24 |

X, Y and Z are closed intervals of unit length on the real line. The overlap of X and Y is half a unit. The overlap of Y and Z is also half a unit. Let the overlap of X and Z be k units. Which of the following is true?

k must be 1 | |

k must be 0 | |

k can take any value between 0 and 1 | |

None of the above |

Question 25 |

E_{1} and E_{2} are events in a probability space satisfying the following constraints:

- • Pr(E

_{1}) = Pr(E

_{2})

• Pr(E

_{1}U E

_{2}) = 1

• E

_{1}and E

_{2}are independent

The value of Pr(E_{1}), the probability of the event E_{1} is

0 | |

1/4 | |

1/2 | |

1 |

_{1}) = Pr(E

_{2}) = a(say)

Pr(E

_{1}∪ E

_{2}) = 1

E

_{1}and E

_{2}are Independent.

P(E

_{1}∪ E

_{2}) = Pr(E

_{1}) + Pr(E

_{2}) - Pr(E

_{1}∩ E

_{2})

1 = a + a - Pr(E

_{1})⋅Pr(E

_{2})

1 = a + a - a⋅a

2a - a

^{2}= 1

a

^{2}- 2a + 1 = 0

(a - 1)

^{2}= 0

a = 1

Pr(E

_{1}) = 1

Answer: Option (D)

Question 26 |

Which of the following statements is true?

S > T | |

S = T | |

S < T and 2S > T | |

2S ≤ T |

Question 27 |

A polynomial p(x) satisfies the following:

p(1) = p(3) = p(5) = 1 p(2) = p(4) = -1

The minimum degree of such a polynomial is

1 | |

2 | |

3 | |

4 |

Minimum degree of P(x) = 4

Maximum degree of P(x) = 5

Question 28 |

A relation R is defined on the set of integers as xRy iff (x+y) is even. Which of the following statements is true?

R is not an equivalence relation | |

R is an equivalence relation having 1 equivalence class | |

R is an equivalence relation having 2 equivalence classes | |

R is an equivalence relation having 3 equivalence classes |

It is symmetric R(x+y) is even ⇒ R(x+y) is even then R(y+x) is also v.

It is transitive R(x+y) is even ⇒ R((x+y)+z)) is even then R(x+(y+z)) is also even.

This given relation is equivalence.

Sum of two even numbers are even. Same sum of two odd numbers are even but one even, one odd is odd. It can have two equivalent classes.

Question 29 |

Let P(S) denotes the powerset of set S. Which of the following is always true?

P(P(S)) = P(S) | |

P(S) ∩ P(P(S)) = {ɸ} | |

P(S) ∩ S = P(S) | |

S ∉ P(S) |

S={1}

P(S)=[{ }, {1}]

P(P(S)) = [{ }, {1}, {{ }, 1}, {1, { }}]

Option A: P(P(S)) ≠ P(S) (wrong)

Option B: P(S) ∩ P(P(S)) ≠ ɸ (wrong)

Option C: P(S) ∩ S ≠ P(S) (wrong)

Option D: S ∈ P(S) (wrong)

None of the given is correct.

Question 30 |

Let a, b, c, d be propositions. Assume that the equivalence a ↔ (b ∨ -b) and b ↔ c hold. Then the truth-value of the formula (a ∧ b) → (a ∧ c) ∨ d is always

True | |

False | |

Same as the truth-value of b | |

Same as the truth-value of d |

Given ⇒ (a∧b) → (a∧c) ∨d

⇒ (a∧b) → (a∧c) ∨d (b⇔c)

⇒ T∨d

⇒ T

Question 31 |

What can be said about a regular language L over {a} whose minimal finite state automation has two states?

L must be {a ^{n} |n is odd} | |

L must be {a ^{n} |n is even} | |

L must be {a ^{n}|≥0} | |

Either L must be {a ^{n} |n is odd}, or L must be {a^{n} | n is even} |

Question 32 |

Consider the following decision problems:

- (P1) Does a given finite state machine accept a given string

(P2) Does a given context free grammar generate an infinite number of stings

Which of the following statements is true?

Both (P1) and (P2) are decidable | |

Neither (P1) nor (P2) are decidable | |

Only (P1) is decidable | |

Only (P2) is decidable |

For P2, check if the CFG generates any string of length between n and 2n−1, where n is the pumping lemma constant. If So, L (CFG) is infinite, else finite. Finding the pumping lemma constant is not trivial. So both P1, P2 are decidable.

Question 33 |

The simultaneous equations on the Boolean variables x, y, z and w,

x + y + z = 1 xy = 0 xz + w = 1 xy + = 0

have the following solution for x, y, z and w, respectively.

0 1 0 0 | |

1 1 0 1 | |

1 0 1 1 | |

1 0 0 0 |

Question 34 |

Which function does NOT implement the Karnaugh map given below?

(w + x)y | |

xy + yw | |

None of the above |

⇒ wy + wz + xy

Question 35 |

The following arrangement of master-slave flip flops

has the initial state of P, Q as 0, 1 (respectively). After three clock cycles the output state P, Q is (respectively),

1, 0 | |

1, 1 | |

0, 0 | |

0, 1 |

When 11 is applied to Jk flip flop it toggles the value of P so op at P will be 1.

Input to D flip flop will be 0(initial value of P) so op at Q will be 0.

Question 36 |

A graphics card has on board memory of 1MB. Which of the following modes can the card not support?

1600 × 400 resolution with 256 colours on a 17 inch monitor | |

1600 × 400 resolution with 16 million colours on a 14 inch monitor | |

800 × 400 resolution with 16 million colours on a 17 inch monitor | |

800 × 800 resolution with 256 colours on a 14 inch monitor |

Option A:

1600×400 = 64000 = 640 KB

256 colours 8 bits = 1 Byte

⇒ 640×1 = 640KB (we have 1MB)

Option B:

1600×400 = 640KB

16 million = 24 bits = 3 bytes

⇒ 640×3 = 1920KB (Not enough)

Option C:

800×400 = 320 KB

16 millions = 3 bytes ⇒ 320×3 = 960 KB (we have 1MB)

Option D:

800×400 = 320 KB

256 colours = 1 Byte ⇒ 320×1 = 320 (we have 1MB)

Question 37 |

Consider the values A = 2.0 x 10^{30}, B = -2.0 x 10^{30}, C = 1.0, and the sequence

X: = A + B Y: = A + C X: = X + C Y: = Y + B

executed on a computer where floating-point numbers are represented with 32 bits. The values for X and Y will be

X = 1.0, Y = 1.0 | |

X = 1.0, Y = 0.0 | |

X = 0.0, Y = 1.0 | |

X = 0.0, Y = 0.0 |

A = 2.0 * 10

^{30}, C = 1.0

So, A + C should make the 31

^{st}digit to 1, which is surely outside the precision level of A (it is 31

^{st}digit and not 31

^{st}bit). So, this addition will just return the value of A which will be assigned to Y.

So, Y + B will return 0.0 while X + C will return 1.0.

Question 38 |

Suppose you are given an array s[1...n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence do, where 1 ≤ k ≤ n:

reverse(s, 1, k) ; reverse(s, k + 1, n); reverse(s, l, n);

Rotates s left by k positions | |

Leaves s unchanged | |

Reverses all elements of s | |

None of the above |

Question 39 |

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

LASTIN = LASTPOST | |

LASTIN = LASTPRE | |

LASTPRE = LASTPOST | |

None of the above |

But in case of complete binary last level need not to be full in that case LASTPRE is not equal to LASTIN.

Question 40 |

Consider the following functions

Which of the following is true?

h(n) is O (f(n)) | |

h(n) is O (g(n)) | |

g(n) is not O (f(n)) | |

f(n) is O(g(n)) |

^{10}

Then

f(n) = 3(n

^{32}) = 3*(2

^{10})

^{32}= 3*2

^{320}

g(n) = 2

^{320}

h(n) = 1024!

So relation between the functions can be:

f(n) and g(n) are of same order, so f(n) is O(g(n)) and g(n) = O(f(n)). Option C is wrong.

h(n) is n! Which is of higher order than f(n) and g(n). So options A and B are wrong.

Question 41 |

Let G be an undirected connected graph with distinct edge weight. Let e_{max} be the edge with maximum weight and e_{min} the edge with minimum weight. Which of the following statements is false?

Every minimum spanning tree of G must contain e _{min} | |

If e _{max} is in a minimum spanning tree, then its removal must disconnect G | |

No minimum spanning tree contains e _{max} | |

G has a unique minimum spanning tree |

Minimum Spanning Tree:

Question 42 |

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let ν be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

{u, v} must be an edge in G, and u is a descendant of v in T | |

{u, v} must be an edge in G, and v is a descendant of u in T | |

If {u, v} is not an edge in G then u is a leaf in T | |

If {u, v} is not an edge in G then u and v must have the same parent in T |

In DFS after visiting u, there is no child node then back tracking is happen and then visit the node v. There is no need of (u,v) be an edge.

Question 43 |

The value of j at the end of the execution of the following C program.

int incr(int i) { static int count = 0; count = count + i; return (count); } main() { int i,j; for (i = 0; i <= 4; i++) j = incr(i); }

is

10 | |

4 | |

6 | |

7 |

i=1; count=1

i=2; count=3

i=3; count=6

i=4; count=10

It return count value is 10.

Question 44 |

Given the following expression grammar:

E → E * F | F + E | F F → F - F | id

which of the following is true?

* has higher precedence than + | |

- has higher precedence than * | |

+ and – have same precedence | |

+ has higher precedence than * |

Order of precedence is *, +, -.

Here * and + have equal preference, '-' can have higher precedence than + and *.

Question 45 |

Suppose the time to service a page fault is on the average 10 milliseconds, while a memory access takes 1 microsecond. Then a 99.99% hit ratio results in average memory access time of

1.9999 milliseconds | |

1 millisecond | |

9.999 microseconds | |

1.9999 microseconds |

_{1}) + [(1-P)t

_{2}]

= (0.9999*1) + [(1-0.9999) *10000]

= (0.9999) + (0.0001 * 10000)

= 0.9999 + 1

= 1.9999 microseconds

Question 46 |

Which of the following is NOT a valid deadlock prevention scheme?

Release all resources before requesting a new resource | |

Number the resources uniquely and never request a lower numbered resource than the last one requested | |

Never request a resource after releasing any resource | |

Request and all required resources be allocated before execution |

Question 47 |

Given the following relation instance.

1 4 2 1 5 3 1 6 3 3 2 2xyz

Which of the following functional dependencies are satisfied by the instance?

XY → Z and Z → Y | |

YZ → X and Y → Z | |

YZ → X and X → Z | |

XZ → Y and Y → X |

If for t1[A] = t2[A] then t1[Y] = t2[Y].

Question 48 |

Given relations r(w, x) and s(y, z), the result of

select distinct w, x from r, s

is guaranteed to be same as r, provided

r has no duplicates and s is non-empty | |

r and s have no duplicates | |

s has no duplicates and r is non-empty | |

r and s have the same number of tuples |

Question 49 |

In SQL, relations can contain null values, and comparisons with null values are treated as unknown. Suppose all comparisons with a null value are treated as false. Which of the following pairs is not equivalent?

x = 5 not AND (not (x = 5) | |

x = 5 AND x > 4 and x < 6, where x is an integer | |

x ≠ 5 AND not (x = 5) | |

None of the above |

Question 50 |

Consider the following sequence: s_{1} : s_{2} = 1 and s_{1} = 1 + mine {s_{i-1}, s_{i-2}} for i > 2. Prove by induction on a n that s_{n} = [n/2].

Theory Explanation is given below. |

Question 51 |

Let S = {0, 1, 2, 3, 4, 5, 6, 7} and ⊗ denote multiplication modulo 8, that is, x⊗y = (xy) mod 8

(a) Prove that ({0,1}, ⊗) is not a group.

(b) Write 3 distinct groups (G, ⊗) where G ⊂ S and G has 2 elements.

Theory Explanation is given below. |

= multiset of size 4 with exactly one element occurs exactly twice + multiset of size 4 with exactly two element occurs exactly twice.

(b) Infinite, because size of multiset is not given.

Question 52 |

A multiset is an unordered collection of elements where elements may repeat any number of times. The size of a multiset is the number of elements in it counting repetitions.

(a) What is the number of multisets of size 4 that can be constructed from n
distinct elements so that at least one element occurs exactly twice?

(b) How many multisets can be consctructed from n distinct elements?

Theory Explanation is given below. |

A1 is the identity element here. Inverse is does not exist for zero then it is not a group.

Question 53 |

Let S be a set of n elements {1, 2, …., n} and G a graph with 2^{n} vertices, each vertex corresponding to a distinct subset of S. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly 2 elements. Note: The symmetric difference of two sets R^{1} and R^{2} is defined as (R^{1}/R^{2})∪(R^{2}/R^{1})

(a) Every vertex in G has the same degree. What is the degree of a vertex in G?

(b) How many connected components does G have?

Theory Explanation is given below. |

Question 54 |

(a) Construct as minimal finite state machine that accepts the language, over {0,1}, of all strings that contain neither the substring 00 nor the substring 11.

(b) Consider the grammar

S → aS Ab S → ε A → bA A → ε

Where S, A are non-terminal symbols with S being the start symbol; a,b are terminal symbols and ε is the empty string. This grammar generates strings of the form a^{i}b^{j} for some i,j ≥ 0, where i and j satisfy some condition. What is the condition on the values of i and j?

Theory Explanation is given below. |

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 55 |

A pushdown automaton (pda) is given in the following extended notation of finite state diagrams:

The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the form d, s where d is the input symbol read and s, s' are the stack contents before and after the move. For example the edge labeled 1, s/1.s denotes the move from state to q_{o} to q_{0} in which the input symbol 1 is read and pushed to the stack.

(a) Introduce two edges with appropriate labels in the above diagram so that the resulting pda accepts the language

{x2x^{R}|x ∈ {0,1}*, x^{R} denotes reverse of x}, by empty stack.

(b) Describe a non-deterministic pda with three states in the above notation that
accept the language {0^{n}1^{m}| n ≤ m ≤ 2n} by empty stack

Theory Explanation is given below. |

(b)

Question 56 |

Design a logic circuit to convert a single digit BCD number to the number modulo six as follows (Do not detect illegal input):

(a) Write the truth table for all bits. Label the input bits I_{1}, I_{2}, …. With I_{1} as the least significant bit. Label the output bits R_{1}, R_{2}, …. With R_{1} as the least significant bit. Use 1 to signify truth.

(b) Draw one circuit for each output bit using, altogether, two two-input AND gates, one two-input gate and two NOT gates.

Theory Explanation is given below. |

Question 57 |

Consider the 8085 instruction IN 09H stored as follows:

And the following incomplete timing diagram for the instruction:

(a) Write the contents of the boxes, A, B, C and D in hexadecimal in your answer sheet. Do not draw any pictures.

(b) Write the state of both ALE and pins at time units T1, T2, T3 and T4.

(c) How do you generate the signal that tells the peripheral to put the data on the bus? Answer by completing the following statement in your answer book:

By combining signals …………….

Theory Explanation is given below. |

Question 58 |

Consider the following 8085 program segment, where registers B and C contain BCD values:

S1: MVI A, 99H MVI D, 00H SUB C ADD B DAA S2: JC S3 MOV E, A MVI A, 99H SUB E MOV E, A JZ S4 MVI D, FFH JMP S4 S3: INC A DAA MOV E, A S4: …………

(a) For the two pairs (B = 44, C = 25) and (B = 33, C = 46) at S1,

(i) Find the values in register A when control reaches S2.

(ii) Find the values in registers D and E when control reaches S4.

(b) What, in general, is the value of D and E as a function of B and C when control reaches S4.

Theory Explanation is given below. |

Question 59 |

An instruction pipeline has five stages where each stage takes 2 nanoseconds and all instructions use all five stages. Branch instructions are not overlapped, i.e., the instruction after the branch is not fetched till the branch instruction is completed. Under ideal conditions.

(a) Calculate the average instruction execution time assuming that 20% of all instruction executed are branch instructions. Ignore the fact that some branch instructions may be conditional.

(b) If a branch instruction is a conditional branch instruction, the branch need not be taken. If the branch is not taken, the following instructions can be overlapped. When 80% of all branch instructions are conditional branch instructions, and 50% of the conditional branch instructions are such that the branch is taken, calculate the average instruction execution time.

Theory Explanation is given below. |

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 60 |

Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, which reverses the order of the elements on the stack.

(a) To implement a queue using the above stack implementation, show how to implement ENQUEUE using a single operation and DEQUEUE using a sequence of 3 operations.

(b) The following postfix expression, containing single digit operands and arithmetic operators + and *, is evaluated using a stack.

5 2 * 3 4 + 5 2 * * +

Show the contents of the stack.

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

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

(iii) At the end of evaluation.

Theory Explanation is given below. |

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 61 |

Consider the line y = n/m x, where n and m are positive integers.

(a) If mq – np < 0, then is the point (p,q) above the line, below the line, or on the line?

(b) Complete the following function, that returns true if the line segment with
endpoints (p,q) and (r,s) intersects the line y = n/m x, by writing the line number and the content of each box in your answer book.

1: function clash (m, n, p, q, r, s: integer): Boolean; 2: begin 3: clash = false; 4: if (m*q – n * p) ▭ 0 then clash := true; 5: If (m*s – n * r) ▭ 0 then clash := true; 6: if (m*q – n * p) ▭ 0 and (m*s – n * r) ▭ 0 then clash : = true; 7: if (m*q – n * p) ▭ 0 and (m*s – n * r) ▭ 0 then clash : = true; 8: end;

Theory Explanation is given below. |

Question 62 |

Suppose you are given arrays p[1…..N] and q[1…….N] both uninitialized that is, each location may contain an arbitrary value), and a variable count, initialized to 0. Consider the following procedures set and iset:

set (i) { count = count + 1; q [count] = i; p[i] = count; } is_set(i) { if (p[i] ≤ 0 or p[i] > count) return false; if (q[p[i]] ≠i) return false; return true; }

(a) Suppose we make the following sequence of calls:
set (7); set (3); set(9);

After these quence of calls, what is the value of count, and what do q[1], q[2], q[3], p[7], p[3] and p[9] contain?

(b) Complete the following statement “The first count elements of _______ contain values i such that set (__________) has been called”.

(c) Show that if set (i) has not been called for some i, then regardless of what p[i] contains, is_set (i) will return false.

Theory Explanation is given below. |

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 63 |

A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array f[0…..m] with all elements initialized to 0.

fib(n) { if (n > M) error (); if (n == 0) return 1; if (n == 1) return 1; if (▭) _________________(1) return ▭ ____________(2) t = fib(n – 1) + fib (n – 2); ▭__________(3) return t; }

(a) Fill in the boxes with expressions/statements to make fib() store and reuse computed Fibonacci values. Write the box number and the corresponding contents in your answer book.

(b) What is the time complexity of the resulting program when computing fib(n)?

Theory Explanation is given below. |

(2) f[n-2];

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

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

Question 64 |

An array contains four occurrences of 0, five occurrences of 1, and three occurrences of 2 in any order. The array is to be sorted using swap operations (elements that are swapped need to be adjacent).

(a) What is the minimum number of swaps needed to sort such an array in the worst case?

(b) Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the array is maximum.

Theory Explanation is given below. |

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 65 |

Consider the following program is pseudo-Pascal syntax.

program main; var x: integer; procedure Q [z:integer); begin z: z + x; writeln(z) end; procedure P (y:integer); var x: integer; begin x: y + 2; Q(x); writeln(x) end; begin x:=5; P(x); Q(x); writeln(x) end.

What is the output of the program, when

(a) The parameter passing mechanism is call-by-value and the scope rule is static scooping?

(b) The parameter passing mechanism is call-by-reference and the scope rule is dynamic scooping?

Theory Explanation is given below. |

Question 66 |

Consider the syntax directed translation scheme (SDTS) given in the following.

Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction.

E → E_{1}* T {E.val = E_{1}.val * T.val} E → T {E.val = T.val} T → F – T_{1}{T.val = F.val – T_{1}.val} T → F {T.val = F.val} F → 2 {F.val = 2} F → 4 {F.val = 4}

(a) Using this SDTS, construct a parse tree for the expression

4 – 2 – 4 * 2

and also compute its E.val.

(b) It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the SDTS given, without changing the grammar, to find E.red, the number of reductions performed while reducing an input to E.

Theory Explanation is given below. |

Question 67 |

(a) Fill in the boxes below to get a solution for the readers-writers problem, using a single binary semaphore, mutex (initialized to 1) and busy waiting. Write the box numbers (1, 2 and 3), and their contents in your answer book.

int R = 0, W = 0; Reader () { L1: wait (mutex); If (W ==0) { R = R +1; ▭______(1) } else { ▭______(2) goto L1; } …./* do the read */ wait (mutex) R = R – 1; signal (mutex); } Writer () { L2: wait(mutex); If (▭) {______(3) signal (mutex); goto L2; } W=1; signal (mutex); …./*do the write*/ wait(mutex) W = 0; signal (mutex);

(b) Can the above solution lead to starvation of writers?

Theory Explanation is given below. |

(ii) Signal (mutex)

(iii) R ⇒ 1 (or) W == 1

(b) In CS, atleast one of the reader is always present. That means writer can't be enter into the critical section.

This leads to readers-writers problem may occur in the queue.

Question 68 |

(a) Suppose you are given an empty B^{+}-tree where each node (leaf and internal) can store up to 5 key values. Suppose values 1,2,….. 10 are inserted, in order, into the tree, Show the tree pictorially

(i) After 6 insertions, and

(ii) After all 10 insertions

Do NOT show intermediate stages.

(b) Suppose instead of splitting a node when it is full, we try to move a value to the left sibling. If there is no left sibling, or the left sibling is full, we split the node. Show the tree after values, 1, 2,….., 9 have been inserted. Assume, as in (a) that each node can hold up to 5 keys.

(c) In general, suppose a B^{+}-tree node can hold a maximum of m keys, and you insert a long sequence of keys in increasing order. Then what approximately is the average number of keys in each leaf level node.

(i) In the normal case, and

(ii) With the insertion as in (b).

Theory Explanation is given below. |

(i)

(ii)

(b)

Question 69 |

Consider a bank database with only one relation

transaction (transno, acctno, date, amount)

The amount attribute value is positive for deposits and negative for withdrawals.

(a) Define an SQL view TP containing the information.

(acctno, T1.date, T2.amount)

for every pair of transactions T1, T2 such that T1 and T2 are transaction on the same account and the date of T2 is ≤ the date of T1.

(b) Using only the above view TP, write a query to find for each account the minimum balance it ever reached (not including the 0 balance when the account is created). Assume there is at most one transaction per day on each account, and each account has had atleast one transaction since it was created. To simply your query, break it up into 2 steps by defining an intermediate view V.

Theory Explanation is given below. |