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

       Engineering-Mathematics       Combinatorics
Question 1 Explanation: 
No. of cards = 52
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

n -1
n2 - 3n + 2
n2 (n+1)/2
       Engineering-Mathematics       Linear-Algebra
Question 2 Explanation: 
Let us consider n=5 then we get

Add ith row and jth column if we zero, apply to all row and their corresponding column the total becomes zero.
Question 3

The determinant of the matrix is


       Engineering-Mathematics       Linear-Algebra
Question 3 Explanation: 
The value of the determinant is 2 * 1 * 2 * 1 = 4
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 = ɸ
       Theory-of-Computation       Regular-Expressions
Question 4 Explanation: 
If we draw DFA for language S and T it will represent same.
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
       Theory-of-Computation       Identify-Class-Language
Question 5 Explanation: 
The given grammar results that a string which contains even length excluding empty string i.e {00,000000,00000000,…….}. So which is regular but not 0+.
Question 6

The number 43 in 2’s complement representation is

       Digital-Logic-Design       Number-Systems
Question 6 Explanation: 
Positive integers are represented in its normal binary form while negative numbers are represented in its 2′s complement form. Binary representation of 43 is 00101011.
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
       Computer-Organization       Microprocessor
Question 7 Explanation: 
If ready pin is high the microprocessor will complete the operation and proceeds for the next operation. If ready pin is low the microprocessor will wait until it goes high.
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
       Computer-Organization       Pipelining
Question 8 Explanation: 
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.
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
       Computer-Organization       Microprocessor
Question 9 Explanation: 
TRAP is non maskable interrupt . TRAP is active high, level, edge triggered non maskable highest priority interrupt. When TRAP line is active microprocessor insert intervals restarts automatically at vector location of TRAP.
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  


X – 3 Y – 2 Z - 1
X – 1 Y – 3 Z - 2
X – 2 Y – 3 Z - 1
X – 3 Y – 1 Z - 2
       Computer-Organization       Match-the-Following
Question 10 Explanation: 
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
       Programming       C-Programming
Question 11 Explanation: 
The given code represents an array of s[ ], in this each element is a pointer to 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  


X – 1 Y – 3 Z – 2
X – 2 Y – 1 Z – 3
X – 3 Y – 2 Z – 1
X – 3 Y – 1 Z – 2
       Programming       Match-the-Following
Question 12 Explanation: 
X → m = NULL will results the loss of memory.
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  


X – 1 Y – 2 Z – 3
X – 3 Y – 1 Z – 2
X – 3 Y – 2 Z – 1
X – 2 Y – 3 Z – 1
       Data-Structures       Match-the-Following
Question 13 Explanation: 
Stack is used in depth first search.
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))
       Data-Structures       Binary-Trees
Question 14 Explanation: 
Option C:

(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 log2 n
n log2 n ≤ t(n) < (n/2)
t(n) = (n/2)
       Algorithms        Sorting
Question 15 Explanation: 
Since the array is sorted. Now just pick the first two minimum elements and check if their sum is less than 1000 or not. If it is less than 1000 then we found it and if not then it is not possible to get the two elements whose sum is less than 1000. Hence, it takes constant time. So, correct option is (A).
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
       Programming       Aliasing
Question 16 Explanation: 
In computer programming, aliasing refers to the situation where the same memory location can be accessed using different names.
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
       Programming       C-Programming
Question 17 Explanation: 
short [5] = 5×2 = 10
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); 


       Compiler-Design       Compilers
Question 18 Explanation: 
We have six different types of tokens are available
(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
       Compiler-Design       Parsers
Question 19 Explanation: 
Top-down parser - Leftmost derivation
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
       Operating-Systems       Context-Switching
Question 20 Explanation: 
We don't need to save TLB or cache to ensure correct program resumption. They are just bonus for ensuring better performance. But PC, stack and registers must be saved as otherwise program cannot resume.
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:

Starvation, but not deadlock
None of the above
       Operating-Systems       Process-Synchronization
Question 21 Explanation: 
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
       Database-Management-System       B+-Trees
Question 22 Explanation: 
In B+ 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
       Database-Management-System       Relational-Algebra
Question 23 Explanation: 
The sum of all employee’s salaries can’t be represented by using the given six basic algebra operation. If we want to represent sum of salaries then we need to use aggregation operator.
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
       Engineering-Mathematics       Numerical-Methods
Question 24 Explanation: 
The value of K must be Either 0 or 1.
Question 25

E1 and E2 are events in a probability space satisfying the following constraints:

    • Pr(E1) = Pr(E2)
    • Pr(E1 U E2) = 1
    • E1 and E2 are independent

The value of Pr(E1), the probability of the event E1 is

       Engineering-Mathematics       Probability
Question 25 Explanation: 
Pr(E1) = Pr(E2) = a(say)
Pr(E1 ∪ E2) = 1
E1 and E2 are Independent.
P(E1 ∪ E2) = Pr(E1) + Pr(E2) - Pr(E1 ∩ E2)
1 = a + a - Pr(E1)⋅Pr(E2)
1 = a + a - a⋅a
2a - a2 = 1
a2 - 2a + 1 = 0
(a - 1)2 = 0
a = 1
Pr(E1) = 1
Answer: Option (D)
Question 26

Which of the following statements is true?

S > T
S = T
S < T and 2S > T
2S ≤ T
       Engineering-Mathematics       Calculus
Question 26 Explanation: 
S is continuously increasing function but T represent constant value so S>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

       Engineering-Mathematics       Polynomials
Question 27 Explanation: 
P(x) should be like

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
       Engineering-Mathematics       Sets-And-Relation
Question 28 Explanation: 
It is reflexive R(x+y) is even ⇒ R(x+x) is even.
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)
       Engineering-Mathematics       Sets-And-Relation
Question 29 Explanation: 
Let us consider
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

Same as the truth-value of b
Same as the truth-value of d
       Engineering-Mathematics       Propositional-Logic
Question 30 Explanation: 
a ↔ (b ∨-b) and b ↔ c
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 {an |n is odd}
L must be {an |n is even}
L must be {an|≥0}
Either L must be {an |n is odd}, or L must be {an | n is even}
       Theory-of-Computation       Finite-Automata
Question 31 Explanation: 
If first state is final, then it accepts even no. of a's. If second state is final then it accepts odd no. of a's.
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
       Theory-of-Computation       Decidability-and-Undecidability
Question 32 Explanation: 
For P1, we just need to give a run on the machine. Finite state machines always halts unlike TM.
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
       Digital-Logic-Design       Boolean-Algebra
Question 33 Explanation: 
Just put the values of each options in the equation and check it.
Question 34

Which function does NOT implement the Karnaugh map given below?

(w + x)y
xy + yw
None of the above
       Digital-Logic-Design       K-Map
Question 34 Explanation: 
Given k-map gives xy + xy + wz

⇒ 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
       Digital-Logic-Design       Sequential-Circuits
Question 35 Explanation: 
Here clocks are applied to both flip flops simultaneously.
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
       Operating-Systems       Graphics
Question 36 Explanation: 
For every option we need to calculate memory.
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 1030, B = -2.0 x 1030, 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
       Digital-Logic-Design       Number-Systems
Question 37 Explanation: 
Given: 32 bits representation. So, the maximum precision can be 32 bits (In 32-bit IEEE representation, maximum precision is 24 bits but we take best case here). This means approximately 10 digits.
A = 2.0 * 1030, C = 1.0
So, A + C should make the 31st digit to 1, which is surely outside the precision level of A (it is 31st digit and not 31st 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
       Data-Structures       Arrays
Question 38 Explanation: 
If we perform the three given open operations it will result left rotation by K positions. If we perform n time it will result the initial array.
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?

None of the above
       Data-Structures       Binary-Trees
Question 39 Explanation: 
In full Binary tree LASTIN = LASTPRE.
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))
       Algorithms        Time-Complexity
Question 40 Explanation: 
Consider n value as 210
f(n) = 3(n32) = 3*(210)32 = 3*2320
g(n) = 2320
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 emax be the edge with maximum weight and  emin the edge with minimum weight. Which of the following statements is false?

Every minimum spanning tree of G must contain emin
If emax is in a minimum spanning tree, then its removal must disconnect G
No minimum spanning tree contains emax
G has a unique minimum spanning tree
       Algorithms        Minimum-Spanning-Tree
Question 41 Explanation: 

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
       Data-Structures       Graphs
Question 42 Explanation: 

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);
   int i,j;
   for (i = 0; i <= 4; i++)
      j = incr(i);


       Programming       C-Programming
Question 43 Explanation: 
At i=0; count=0
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 *
       Compiler-Design       Grammar
Question 44 Explanation: 
The operator which is in low level that can have high preference.
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
       Operating-Systems       Virtual Memory
Question 45 Explanation: 
Average memory access time = (P*t1) + [(1-P)t2]
= (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
       Operating-Systems       Deadlock
Question 46 Explanation: 
Given statement is wrong. We can request a resource after releasing any resource.
Question 47

Given the following relation instance.

          x  y  z
          1  4  2
          1  5  3
          1  6  3
          3  2  2  

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
       Database-Management-System       Functional-Dependency
Question 47 Explanation: 
A functional dependency A→B is said to hold if for two tuples t1 and t2.
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
       Database-Management-System       SQL
Question 48 Explanation: 
r has no duplicate, if r can have duplicates it can be remove in the final state. s in non-empty if s is empty then r*s becomes empty.
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
       Database-Management-System       SQL
Question 49 Explanation: 
For all values less than five, x<5 is true and if x=5 then it is false.
Question 50

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

Theory Explanation is given below.
       Engineering-Mathematics       Sets-And-Relation
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.
       Engineering-Mathematics       Sets-And-Relation
Question 51 Explanation: 
(a) No. of multiset of size 4 that can be constructed from n distinct elements so that atleast one element occurs exactly twice:
= 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.
       Engineering-Mathematics       Sets-And-Relation
Question 52 Explanation: 

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 2n 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 R1 and R2 is defined as (R1/R2)∪(R2/R1)
(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.
       Engineering-Mathematics       Graph-Theory
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 aibj 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.
       Theory-of-Computation       Descriptive
Question 54 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.
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 qo to q0 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
{x2xR|x ∈ {0,1}*, xR denotes reverse of x}, by empty stack.
(b) Describe a non-deterministic pda with three states in the above notation that accept the language {0n1m| n ≤ m ≤ 2n} by empty stack

Theory Explanation is given below.
       Theory-of-Computation       Descriptive
Question 55 Explanation: 

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 I1, I2, …. With I1 as the least significant bit. Label the output bits R1, R2, …. With R1 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.
       Digital-Logic-Design       Descriptive
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.
       Computer-Organization       Descriptive
Question 57 Explanation: 
Note: Out of syllabus.
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
 S2: JC      S3 
     MOV     E, A
     MVI     A, 99H
     SUB     E
     MOV     E, A
     JZ      S4
     MVI     D, FFH
     JMP     S4
 S3: INC     A
     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.
       Computer-Organization       Descriptive
Question 58 Explanation: 
Note: Out of syllabus.
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.
       Computer-Organization       Descriptive
Question 59 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
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.
       Data-Structures       Descriptive
Question 60 Explanation: 
(a) Enqueue → push
Dequeue → reverse, pop, reverse
(b) (i) After evaluating 5 2 * 3 4 +
7(3+4) 10(5*2)
(ii) After evaluating 5 2 * 3 4 + 5 2
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.
       Engineering-Mathematics       Descriptive
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.
       Data Structures        Descriptive
Question 62 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 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);
        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.
       Algorithms        Descriptive
Question 63 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).
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.
       Algorithms        Descriptive
Question 64 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)

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);
          z: z + x;
    procedure P (y:integer);
          var x: integer;
          x: y + 2;

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.
       Programming       Descriptive
Question 65 Explanation: 
Note: Out of syllabus.
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 → E1 * T {E.val = E1.val * T.val}
 E → T {E.val = T.val}
 T → F – T1{T.val = F.val – T1.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, the number of reductions performed while reducing an input to E.

Theory Explanation is given below.
       Compiler-Design       Descriptive
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; 
     else {
                goto L1;
                …./* do the read */
                wait (mutex)
                R = R – 1;
                signal (mutex);
          Writer () {
 L2:            wait(mutex);
                If (▭) {______(3)
                    signal (mutex);
                    goto L2;
                signal (mutex);
                …./*do the write*/
                W = 0;
                signal (mutex); 

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

Theory Explanation is given below.
       Operating-Systems       Process-Synchronization
Question 67 Explanation: 
(a) (i) Signal (mutex)
(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.
       Database-Management-System       B+-Trees
Question 68 Explanation: 


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,, 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.
       Database-Management-System       SQL
There are 69 questions to complete.