GATE 2002

Question 1

The rank of the matrix is

A
4
B
2
C
1
D
0
       Engineering-Mathematics       Linear-Algebra
Question 1 Explanation: 
Number of non-zero rows is the rank of the matrix.
Question 2

The trapezoidal rule for integration give exact result when the integrand is a polynomial of degree:

A
0 but not 1
B
1 but not 0
C
0 or 1
D
2
       Engineering-Mathematics       Trapezoidal Rule
Question 2 Explanation: 
If curve is of function of degree 1, then curve will be a straight line, and in that case also, all trapezoids will fit completely. So there is no error in degree 1.
Question 3

The solution to the recurrence equation T(2k) = 3 T(2k-1) + 1, T(1)=1, is:

A
B
C
D
       Algorithms        Recurrence
Question 3 Explanation: 
T(2k) = 3T(2k-1) + 1
T(1)=1
k=0; T(1) = 3T(2-1)+1
k=1; T(2) = 3T(20)+1 = 3(1)+1 = 4
k=2; T(4) = 3T(21)+1 = 3(4)+1 = 13
k=3; T(8) = 3T(22)+1 = 3(13)+1 = 40
k=4; T(16) = 3T(23)+1 = 3(40)+1 = 121
Simply go through the options.
Option B:
k=4 ⇒ (34+1-1)/2
⇒ (243-1)/2
⇒ 121
Question 4

The minimum number of colours required to colour the vertices of a cycle with η nodes in such a way that no two adjacent nodes have the same colour is

A
2
B
3
C
4
D
n - 2[n/2] + 2
       Engineering-Mathematics       Graph-Theory
Question 4 Explanation: 
We need 2 colours to colour even cycle and 3 colours to colour odd cycle.
Question 5
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
A
log n
B
n/2
C
(log2)n - 1
D
n
       Data-Structures       Linked-List
Question 5 Explanation: 
Worst case time complexity of singly linked list is O(n). So we need n number of comparisons needed to search a singly linked list of length n.
Question 6

Which of the following is true?

A
The set of all rational negative numbers forms a group under multiplication.
B
The set of all non-singular matrices forms a group under multiplication.
C
The set of all matrices forms a group under multiplication.
D
Both B and C are true.
       Engineering-Mathematics       Sets-And-Relation
Question 6 Explanation: 
A group G should follow 4 properties:
a. Closure: result of a * b must be in group G.
b. There must be an identity element i.e. e * a = a * e = a
c. There must be an inverse element b for every element a such that a * b = b * a = e
d. Associativity i.e. (a * b) * c = a * (b * c)
Rational negative numbers don't form a group under multiplication, as multiplying two negative numbers results into a positive number, so closure property is not satisfied.
Set of non-singular matrices forms a group under multiplication.
The set of all matrices doesn't form a group under multiplication, since there may not be an inverse for a matrix (in particular, for singular matrices).
Question 7

The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as

A
Context free
B
Regular
C
Deterministic Context free
D
Recursive
       Theory-of-Computation       Identify-Class-Language
Question 7 Explanation: 
Push down automata accept context free grammars but here the value of stack is limited 10 then it accepts regular languages.
Question 8

“If X then Y unless Z” is represented by which of the following formulas in prepositional logic? (“¬“, is negation, “∧” is conjunction, and “→” is implication)

A
(X∧¬Z)→Y
B
(X∧Y)→¬Z
C
X→(Y∧¬Z)
D
(X→Y)∧¬Z
       Engineering-Mathematics       Propositional-Logic
Question 8 Explanation: 
"If X then Y unless Z" ⇒ ¬Z → (X→Y)
⇒ Z ∨ ¬X ∨ Y
⇒ ¬X ∨ Z ∨ Y
Option A:
(X ∧ ¬Z) → Y = ¬(X ∧ ¬Z ) ∨ Y = ¬X ∨ Z ∨ Y Hence, option (A) is correct.
Question 9

A device employing INTR line for device interrupt puts the CALL instruction on the data bus while

A
B
HOLD is active
C
READY is active
D
None of the above
       Computer-Organization       Microprocessor
Question 9 Explanation: 
INTR is a signal which if enabled then microprocessor has interrupt enabled it receives high INR signal & activates INTA signal, so another request can’t be accepted till CPU is busy in servicing interrupt.
Question 10

In 8085 which of the following modifies the program counter?

A
Only PCHL instruction
B
Only ADD instructions
C
Only JMP and CALL instructions
D
All instructions
       Computer-Organization       Microprocessor
Question 10 Explanation: 
PCHL Instruction: Which can copy the content from H& L to PC.
ADD Instruction: increments the program counter.
JMP & CALL: Change the values of PC.
Question 11

In serial data transmission, every byte of data is padded with a ‘0’ in the beginning and one or two ‘1’s at the end of byte because

A
Receiver is to be synchronized for byte reception
B
Receiver recovers lost ‘0’s and ‘1’s from these padded bits
C
Padded bits are useful in parity computation
D
None of the above
       Computer-Organization       Serial-Communication
Question 11 Explanation: 
‘0’ is added at the beginning which can represent receiver about arrival of data and ‘1’ is added at the end which represent receiver state of new arrival of data.
Question 12

Minimum sum of product expression for f(w,x,y,z) shown in Karnaugh-map below is

A
xz+y'z
B
xz'+zx'
C
x'y+zx'
D
None of the above
       Digital-Logic-Design       K-Map
Question 12 Explanation: 

⇒ xz' + zx'
Question 13

Which of the following is not a form of memory?

A
instruction cache
B
instruction register
C
instruction opcode
D
translation look-a-side buffer
       Computer-Organization       Instruction-Execution
Question 13 Explanation: 
Opcode is the portion of a machine language instruction that specifies the operation to be performed.
Question 14

The decimal value 0.25

A
is equivalent to the binary value 0.1
B
is equivalent to the binary value 0.01
C
is equivalent to the binary value 0.00111…
D
cannot be represented precisely in binary
       Digital-Logic-Design       Number-Systems
Question 14 Explanation: 
1st Multiplication iteration:
Multiply 0.25 by 2.
0.25×2 = 0.50 (product)
Fractional part = 0.50
Carry = 0
2nd Multiplication iteration:
Multiply 0.50 by 2.
0.50×2 = 1.00 (product)
Fractional part = 0.00
Carry = 1
The fractional part in the 2nd iteration becomes zero and so we stop the multiplication iteration.
Carry from 1st multiplication iteration becomes MSB and carry from 2nd iteration becomes LSB. So the result is 0.01.
Question 15

The 2’s complement representation of the decimal value -15 is

A
1111
B
11111
C
111111
D
10001
       Digital-Logic-Design       Number-Systems
Question 15 Explanation: 
15 = 1111
-15 = 11111
1's complement = 10000
2's complement = 10001
Question 16

Sign extension is a step in

A
floating point multiplication
B
signed 16 bit integer addition
C
arithmetic left shift
D
converting a signed integer from one size to another
       Digital-Logic-Design       Number-Systems
Question 16 Explanation: 
Sign extension is a step in converting a signed integer from on size to another.
Question 17

In the C language

A
At most one activation record exists between the current activation record and the activation record for the main
B
The number of activation records between the current activation record and the activation record for the main depends on the actual function calling sequence.
C
The visibility of global variables depends on the actual function calling sequence.
D
Recursion requires the activation record for the recursive function to be saved on a different stack before the recursive fraction can be called.
       Programming       C-Programming
Question 17 Explanation: 
In C Language a function can create activation record from the created function stack.
Question 18

The results returned by function under value-result and reference parameter passing conventions

A
Do not differ
B
Differ in the presence of loops
C
Differ in all cases
D
May differ in the presence of exception
       Data-Structures       Parameter-Passing
Question 18 Explanation: 
The result return by the function under value-result and reference parameter passing conventions may differ in presence of exception because in value-result the updated value can be returned to the original variable. But in case of reface parameter the value can change immediately.
Question 19

Relation R with an associated set of functional dependencies, F, is decomposed into BCNF. The redundancy (arising out of functional dependencies) in the resulting set of relations is

A
Zero
B
More than zero but less than that of an equivalent 3NF decomposition
C
Proportional to the size of F+
D
Indetermine
       Database-Management-System       Normalization
Question 19 Explanation: 
If a relation is in BCNF then there is no functional dependencies.
Question 20

With regard to the expressive power of the formal relational query languages, which of the following statements is true?

A
Relational algebra is more powerful than relational calculus.
B
Relational algebra has the same power as relational calculus.
C
Relational algebra has the same power as safe relational calculus.
D
None of the above.
       Database-Management-System       Relational-Algebra
Question 20 Explanation: 
Relational algebra has the same power as safe relational calculus.
A query can be formulated in safe Relational Calculus if and only if it can be formulated in Relational Algebra.
Question 21

In 2’s complement addition, overflow

A
is flagged whenever there is carry from sign bit addition
B
cannot occur when a positive value is added to a negative value
C
is flagged when the carries from sign bit and previous bit match
D
None of the above
       Digital-Logic-Design       Number-Systems
Question 21 Explanation: 
The left most bit of positive value is zero. And left most bit for negative value is one. The value of 0+1 becomes 1. Then overflow never occurs.
Question 22

Which of the following scheduling algorithms is non-preemptive?

A
Round Robin
B
First-In First-Out
C
Multilevel Queue Scheduling
D
Multilevel Queue Scheduling with Feedback
       Operating-Systems       Process-Scheduling
Question 22 Explanation: 
First-in first-out scheduling algorithm is non-preemptive. In this whichever the process enter into ready queue first that will be served first.
Question 23

The optimal page replacement algorithm will select the page that

A
Has not been used for the longest time in the past.
B
Will not be used for the longest time in the future.
C
Has been used least number of times.
D
Has been used most number of times.
       Operating-Systems       Page-Replacement
Question 23 Explanation: 
The optimal page replacement algorithm will select the page which will not been used for the longest time in the future.
Question 24

In the absolute addressing mode

A
the operand is inside the instruction
B
the address of the operand is inside the instruction
C
the register containing the address of the operand is specified inside the instruction
D
the location of the operand is implicit
       Computer-Organization       Addressing-Modes
Question 24 Explanation: 
The operand is inside the instruction---Immediate addressing.
The operand is inside the instruction --- absolute addressing.
The register containing the address of the operand is specified inside the instruction --- Register addressing.
The location of the operand is implicit --- Implicit addressing.
Question 25

Maximum number of edges in a n-node undirected graph without self loops is

A
n2
B
n(n-1)/2
C
n-1
D
(n+1)(n)/2
       Engineering-Mathematics       Graph-Theory
Question 25 Explanation: 
The set of vertices has size n, the number of such subsets is given by the binomial coefficient C(n, 2)⋅ C(n, 2) = n(n-1)/2.
Question 26

Consider the following logic circuit whose inputs are functions f1, f2, f3 and output is f.

Given that

f1(x,y,z) = ∑(0,1,3,5),
f2(x,y,z) = ∑(6,7) and
f(x,y,z) = ∑(1,4,5),

f3 is:

A
Σ(1,4,5)
B
Σ(6,7)
C
Σ(0,1,3,5)
D
None of the above
       Digital-Logic-Design       Logic-Circuit
Question 26 Explanation: 
f(x,y,z) = (f1', (x,y,z) ⋅ f2'(x,y,z) + f3'(x,y,z))
= (Σ(0,1,3,5) ⋅ Σ(6,7) + Σ(1,4,5))
[Σ(0,1,3,5) and Σ(6,7) ⇒ No common terms]
= (Σ(1,4,5))
Question 27

Consider the following multiplexor where 10, 11, 12, 13 are four data input lines selected by two address line combinations A1A0 = 00,01,10,11 respectively and f is "the output of the multiplexor. EN is the enable input.

The function f(x,y,z) implemented by the above circuit is:

A
xyz'
B
xy+z
C
x+y
D
None of the above
       Digital-Logic-Design       Multiplexer
Question 27 Explanation: 
F = (A'A0'10 + A'A0'11 + A'A0'12 + A1A013) EN
F = (xyz' + xyz + y'zy + zy')z'
= (xyz' + xyz + y'z(y+1))z'
= (xyz' + xyz + y'z)z'
= (xy(z+z') + y'z)z'
= (xy + y'z)z'
= (xyz' + y'zz')
= (xyz')
Question 28

Let f(A,B) = A' + B. Simplified expression for function f(f(x + y, y)z) is:

A
x'+z
B
xyz
C
xy'+z
D
None of the above
       Digital-Logic-Design       Boolean-Expressions
Question 28 Explanation: 
f(A,B) = A' + B
⇒ f(f((x+y), y), z)
⇒ f(((x+y)' + y), z)
⇒ f(((x'⋅y') + y), z)
⇒ f((x'⋅y') + y), z)
⇒ ((x'⋅y') + y)' + z
⇒ (x'⋅y')⋅y' + z
⇒ (x+y)⋅y' + z
⇒ (xy'+yy') + z
⇒ xy' + z
Question 29

What are the states of the Auxiliary Carry (AC) and Carry Flag (dCY) after executing the following 8085 program?

   MVI H, 5DH
   MVI L, 6BH
   MOV A, H
   ADD L 
A
AC = 0 and CY = 0
B
AC = 1 and CY = 1
C
AC = 1 and CY = 0
D
AC = 0 and CY = 1
       Computer-Organization       Microprocessor
Question 29 Explanation: 
MOV H, 5DH
⇒ H = 0101 1101
MOV L, 6BH
⇒ L = 0110 1011
MOV A, H
A = 0101 1101
ADD L ⇒ A+L =

Here, AC=1; CY=0
Question 30

The Finite state machine described by the following state diagram with A as starting state, where an arc label is x/y and x stands for 1-bit input and y stands for 2- bit output

A
Outputs the sum of the present and the previous bits of the input.
B
Outputs 01 whenever the input sequence contains 11
C
Outputs 00 whenever the input sequence contains 10
D
None of the above
       Theory-of-Computation       Finite-Automata
Question 30 Explanation: 
Let us consider a string 100111
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,0) = (A, 01)
Previous input + Present input = 1+0 = 01
(A,0) = (A, 00)
Previous input + Present input = 0+0 = 00
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,1) = (C, 10)
Previous input + Present input = 1+1 = 10
(C,1) = (C, 10)
Previous input + Present input = 1+1 = 10
Question 31

The performance of a pipelined processor suffers if

A
the pipeline stages have different delays
B
consecutive instructions are dependent on each other
C
the pipeline stages share hardware resources
D
All of the above
       Computer-Organization       Pipelining
Question 31 Explanation: 
To speedup from pipelining equals the number of pipe stages are involve. Usually, however, the stages will not be perfectly balanced; besides, the pipelining itself involves some overhead.
If pipeline stages can’t have different delays, no dependency among consecutive instructions and sharing of hardware resources should not be there.
Question 32

Horizontal microprogramming

A
does not require use of signal decoders
B
results in larger sized microinstructions than vertical microprogramming
C
uses one bit for each control signal
D
all of the above
       Computer-Organization       Microprogramming
Question 32 Explanation: 
In horizontal microprogramming the instruction size is less as compared to vertical microprogramming. So, there is no need for decoding. But, one bit is used for all control signals to execute the microinstruction. If the bit is set to ‘1’ the control signal field is activated. If the bit is set to ‘0’ the control signal field is deactivated.
Question 33

Consider the following declaration of a two dimensional array in C:

          char a[100][100];    

Assuming that the main memory is byte-addressable and that the array is stored starting from memory address 0, the address of a [40][50] is:

A
4040
B
4050
C
5040
D
5050
       Data-Structures       Arrays
Question 33 Explanation: 
Address for a[40][50] = BaseAddress + [40 * 100 * element size] + [50 * element size]
= 0 + [40 * 100 * 1] + [50 * 1]
= 4000 + 50
= 4050
Question 34

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

A
n/2
B
(n-1)/3
C
(n-1)/2
D
(2n+1)/3
       Data-Structures       Tree
Question 34 Explanation: 

Question 35

Consider the following algorithm for searching for a given number x in an unsorted array A[1...n] having n distinct values:

        1. Choose an i uniformly at random from 1...n;
        2. If A[i]=x then Stop else Goto 1; 

Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?

A
n
B
n-1
C
2n
D
n/2
       Algorithms        Searching
Question 35 Explanation: 
Question 36

The running time of the following algorithm

  Procedure A(n)
  If n <= 2 return(1) else return (A(⌈√n⌉)); 

is best described by:

A
O(n)
B
O(log n)
C
O(log log n)
D
O(1)
       Algorithms        Time-Complexity
Question 36 Explanation: 
T(n) = T(√n)+1
Let n=2m
So, T(2m) = T(2m/2)+1
We substitute T(2m) = S(m),
So now the equation becomes,
S(m) = S(m/2)+1
Now after applying master's theorem,
S(m) = O(log m)
T(n) = O(log log n)
Question 37

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left subtree is at least half and at most twice the number of nodes in the right subtree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

A
log2n
B
log4/3n
C
log3n
D
log3/2n
       Data-Structures       Tree
Question 37 Explanation: 
Number of nodes in the left subtree is atleast half and atmost the num begin right sub tree.
No. of nodes in left sub tree = 2 right sub tree
No. of nodes in left sub tree = (n-1/3)
No. of nodes in right sub tree = 2(n-1/3)

Height of the tree = log3/2 n
Question 38

The smallest finite automaton which accepts the language {x|length of x is divisible by 3} has

A
2 states
B
3 states
C
4 states
D
5 states
       Theory-of-Computation       Finite-Automata
Question 38 Explanation: 
{x | length of x divisible by 3} for this constructing a finite Automata that implies

Minimum no. of states that we require is "3".
Question 39

Which of the following is true?

A
The complement of a recursive language is recursive.
B
The complement of a recursively enumerable language is recursively enumerable.
C
The complement of a recursive language is either recursive or recursively enumerable.
D
The complement of a context-free language is context-free.
       Theory-of-Computation       Properties-of-Languages
Question 39 Explanation: 
Recursive languages are closed under complementation.
Question 40

The Newton-Raphson iteration Xn+1 = (Xn/2) + 3/(2Xn) can be used to solve the equation

A
X2 = 3
B
X3 = 3
C
X2 = 2
D
X3 = 2
       Engineering-Mathematics       Newton-Raphson-Method
Question 40 Explanation: 
Newton Raphson formula,
Xn+1 = Xn+1 - f(Xn)/f'(Xn)
Option A:
X2 = 3 ⇒ X2 - 3 = 0
f(X) = X2 - 3; f'(X) = 2X
Xn+1 = Xn - (Xn2-3)/(2Xn)
Xn+1 = (Xn/2) + 3/(2Xn)
Question 41

Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is

A
1/16
B
1/8
C
7/8
D
15/16
       Engineering-Mathematics       Probability
Question 41 Explanation: 
Total possibilities = 42 = 16
Atleast one head = 1/16
Atleast one tail = 1/16
Probability of getting one head and one tail is = 1 - 1/16 - 1/16 = 16 - 1 - 1/16 = 14/16 = 7/8
Question 42

The binary relation S = ɸ (empty set) on set A = {1,2,3} is

A
Neither reflexive nor symmetric
B
Symmetric and reflexive
C
Transitive and reflexive
D
Transitive and symmetric
       Engineering-Mathematics       Sets-And-Relation
Question 42 Explanation: 
S = ɸ; A = {1,2,3}
A×S = {(ɸ,1), (ɸ,2), (ɸ,3), (1,ɸ), (2,ɸ), (3,ɸ)}
Not reflexive = (1,1), (2,2), (3,3) not there
Symmetric: if (a,b) is present then (b,a) is also present
Transitive: True; if (x,y), (y,z) then (z,x) is also present
Question 43

The C language is:

A
A context free language
B
A context sensitive language
C
A regular language
D
Parsable fully only by a Turing machine
       Theory-of-Computation       Identify-Class-Language
Question 43 Explanation: 
C and C++ are context sensitive languages.
Question 44

To evaluate an expression without any embedded function calls

A
One stack is enough
B
Two stacks are needed
C
As many stacks as the height of the expression tree are needed
D
A Turning machine is needed in the general case
       Data-Structures       Stacks
Question 44 Explanation: 
To evaluate an expression or converting prefix to postfix, postfix to prefix only one stack is enough.
Question 45

Dynamic linking can cause security concerns because

A
Security is dynamic
B
The path for searching dynamic libraries is not known till runtime
C
Linking is insecure
D
Cryptographic procedures are not available for dynamic linking
       Operating-Systems       Linker
Question 45 Explanation: 
Because dynamic linking the path for searching dynamic libraries is not known till runtime.
Question 46

Which combination of the following features will suffice to characterize an OS as a multi-programmed OS?

    (a) More than one program may be loaded into main memory at the same time for execution.
    (b) If a program waits for certain events such as I/O, another program is immediately scheduled for execution.
    (c) If the execution of program terminates, another program is immediately scheduled for execution.
A
A
B
A and B
C
A and C
D
A, B and C
       Operating-Systems       Multi-Programming
Question 46 Explanation: 
Statement C can be done in both multi programmed OS and as well as uni programmed OS.
Question 47

In the index allocation scheme of blocks to a file, the maximum possible size of the file depends on

A
the size of the blocks, and the size of the address of the blocks.
B
the number of blocks used for the index, and the size of the blocks.
C
the size of the blocks, the number of blocks used for the index, and the size of the address of the blocks.
D
None of the above
       Operating-Systems       File-System
Question 47 Explanation: 
No. of addressable blocks using one Index block (A) = Size of block/Size of block address.
No. of block addresses available for addressing one file(B) = No. of Maximum blocks we can use for the Index * No. of addressable blocks using one Index block(A)
Size of File = B * Size of Block
Question 48

A B+- tree index is to be built on the Name attribute of the relation STUDENT. Assume that all student names are of length 8 bytes, disk blocks are of size 512 bytes, and index pointers are of size 4 bytes. Given this scenario, what would be the best choice of the degree (i.e. the number of pointers per node) of the B+-tree?

A
16
B
42
C
43
D
44
       Database-Management-System       B+-Trees
Question 48 Explanation: 
Let P be the degree of the nodes.
Then,
8(P-1) + 4P ≤ 512
12P - 8 ≤ 512
12P ≤ 520
P ≤ 43.33
P = 43
Question 49

Relation R is decomposed using a set of functional dependencies, F, and relation S is decomposed using another set of functional dependencies, G. One decomposition is definitely BCNF, the other is definitely 3NF, but it is not known which is which. To make a quaranteed identification, which one of the following tests should be used on the decompositions? (Assume that the closures of F and G are available).

A
Dependency-preservation
B
Lossless-join
C
BCNF definition
D
3NF definition
       Database-Management-System       Normalizati
Question 49 Explanation: 
If it is BCNF then it is 3NF. But the relation is in 3NF then it is need not to be in BCNF.
Question 50

From the following instance of a relation scheme R(A,B,C), we can conclude that:

A
A functionally determines B and B functionally determines C
B
A functionally determines B and B does not functionally determines C
C
B does not functionally determines C
D
A does not functionally determines B and B does not functionally determines C
       Database-Management-System       Functional-Dependency
Question 50 Explanation: 
From the given instance of relation it can be seen that A functionally determines B, but we cannot conclude this for the entire relation.
But for the given instance it can be seen that B does not functionally determines C, and it can be concluded for entire relation.
Question 51

Let A be a set of n(>0) elements. Let Nr be the number of binary relations on A and let Nf be the number of functions from A to A.

    (a) Give the expression for Nr in terms of n.
    (b) Give the expression for Nf in terms of n.
    (c) Which is larger for all possible n, Nr or Nf?
A
Theory Explanation is given below.
       Engineering-Mathematics       Functions
Question 52

(a) S = {〈1,2〉,〈2,1〉} is binary relation on set A = {1,2,3}. Is it irreflexive? Add the minimum number of ordered pairs to S to make it an equivalence relation. Give the modified S.

(b) Let S = {a,b} and let (S) be the powerset of S. Consider the binary relation ‘⊆ (set inclusion)’ on (S). Draw the Hasse diagram corresponding to the lattice ((S),⊆).

A
Theory explanation is given below.
       Engineering-Mathematics       Sets-And-Relation
Question 52 Explanation: 
(a) S = {(1,2), (2,1)}; A = {1,2,3}
The given relation S is irreflexive because no diagonal elements are present in the relation i.e., (x,x)∉R, ∀x∈A
If a relation is equivalence then it is
Reflexive
Symmetric
Transitive
Given relation S is not Reflexive & Transitive.
Reflexive closure on S = {(1,1), (2,2), (3,3), (1,2), (2,1)}
Transitive closure on S is does not change after performing reflexive closure on S.
S = {(1,1), (2,2), (3,3), (1,2), (2,1)}
(b) Given S = {a,b}
Powerset of S i.e., P(S) = {(ɸ), (a), (b), (a,b)}
Hasse diagram:
Question 53

(a) Obtain the eigen values of the matrix

(b) Determine whether each of the following is a tautology, a contradiction, or neither (“∨” is disjunction, “∧” is conjunction, “→” is implication, “¬” in negation, and “↔” is biconditional (if and only if).

   (i) A ↔ (A ∨ A)
   (ii) (A ∨ B) → B
   (iii) A ∧(¬(A ∨ B)
A
Theory Explanation is given below.
       Engineering-Mathematics       Linear-Algebra-and-Propositional-Logic
Question 53 Explanation: 
(a)
Eigen value of upper/ lower triangular matrix are the diagonal elements of matrix.

(b) (i) A↔(A∨A): This can tells that if A then (A or A)and if (A or A) then A. It represents result as a tautology.
(ii) (A∨B)→B: This is neither tautology nor contradiction.
(iii) A∧(¬(A∨B)): here when A is true then (¬(A∨B)) is false, then it results contradiction.
Question 54

Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.

A
Theory Explanation is given below.
       Data-Structures       Binary-Trees
Question 54 Explanation: 

Total 5 binary trees are possible with the preorder C, B, A.
Question 55

(a) Express the function f(x,y,z) = xy' + yz' with only one complement operation and one or more AND/OR operations. Draw the logic circuit implementing the expression obtained, using a single NOT gate and one or more AND/OR gates.

(b) Transform the following logic circuit (without expressing its switching function) into an equivalent logic circuit that employs only 6 NAND gates each with 2-inputs.

A
Theory Explanation is given below.
       Digital-Logic-Design       Boolean-Expression-and-Logic-Gates
Question 55 Explanation: 

(A) f(x,y,z) = xy' +yz'
It is not possible to express only one NOT gate.
Question 56

Consider the following circuit. A = a2a1a0 and B = b2b1b0 are three bit binary numbers input to the circuit. The output is Z = z3z2z1z0. R0, R1 and R2 are registers with loading clock shown. The registers are loaded with their input data with the falling edge of a clock pulse (signal CLOCK shown) and appears as shown. The bits of input number A, B and the full adders are as shown in the circuit. Assume Clock period is greater than the settling time of all circuits.

(a) For 8 clocks pulses on the CLOCK terminal and the inputs A, B as shown, obtain the output Z (sequence of 4-bit values of Z). Assume initial contents of R0, R1 and R2 as all zeros.

A=          110 011 111 101 000 000 000 000
B=          101 101 011 110 000 000 000 000
Clock No     1   2   3   4   5   6   7   8 

(b) What does the circuit implement?

A
Theory Explanation is given below.
       Digital-Logic-Design       Clock-Pulse
Question 57

Consider the following 32-bit floating-point representation scheme as shown in the formal below. A value is specified by 3 fields, a one bit sign field (with 0 for positive and 1 for negative values), a 24 bit fraction field (with the binary point being at the left end of the fraction bits), and a 7 bit exponent field (in excess-64 signed integer representation, with 16 being the base of exponentiation). The sign bit is the most significant bit.

(a) It is required to represent the decimal value –7.5 as a normalized floating point number in the given format. Derive the values of the various fields. Express your final answer in the hexadecimal.

(b) What is the largest values that can be represented using this format? Express your answer as the nearest power of 10.

A
Theory of Explanation is given below.
       Digital-Logic-Design       Number-Systems
Question 58

In a C program, an array is declared as float A[2048]. Each array element is 4 Bytes in size, and the starting address of the array is 0×00000000. This program is run on a computer that has a direct mapped data cache of size 8 Kbytes, with block (line) size of 16 Bytes.

(a) Which elements of the array conflict with element A[0] in the data cache? Justify your answer briefly.

(b) If the program accesses the elements of this array one by one in reverse order i.e., starting with the last element and ending with the first element, how many data cache misses would occur? Justify your answer briefly. Assume that the data cache is initially empty and that no other data or instruction accesses are to be considered.

A
Theory Explanation is given below.
       Computer-Organization       Cache
Question 59

The following recursive function in C is a solution to the Towers of Hanoi problem.

 Void move (int n, char A, char B, char C)
 {
     if (…………………………………) {
         move (…………………………………);
         printf(“Move disk %d from pole %c to pole %c\n”, n,A,C);
         move (………………………………….); 

Fill in the dotted parts of the solution.

A
Theory Explanation is given below.
       Data-Structures       Recursion
Question 59 Explanation: 
move (disk-1, source, aux, dest) //Step-1
move disk from source to dest //Step-2
move (disk-1, aux, dest, source) //Step-3
Recurrence: 2T(n - 1) + 1
T(n) = 2T (n - 1) + 1
= 2[2T(n - 2) + 1] + 1
= 22T(n - 2) + 3

2k T(n - k) + (2k - 1)
= 2n-1T(1) + (2n-1 - 1)
= 2n-1 + 2n-1 - 1
= 2n - 1
≅ O(2n)
void move (int n, char A, char B, char C) {
if (n>0)
move(n-1, A, C, B);
printf("Move disk%d from pole%c to pole%c\n", n,A,C);
move(n-1, B, A, C);
}
}
Question 60

Fill in the blanks in the following template of an algorithm to compute all pairs shortest path lengths in a directed graph G with n*n adjacency matrix A. A[i,j]equals if there is an edge in G from i to j, and 0 otherwise. Your aim in filling in the blanks is to ensure that the algorithm is correct.

 INITIALIZATION: For i = 1 … n
                      {For j = 1 … n
                          { if A[i,j]=0 then P[i,j] = _______ else P[i,j] =____;}
 ALGORITHM: For i = 1 …n
           { For j = 1 …n
                    {For k = 1 …n
                         {P[__,___]=min{_______,_______};}
                    }
           } 
    (a) Copy the complete line containing the blanks in the Initialization step and fill in the blanks.
    (b) Copy the complete line containing the blanks in the Algorithm step and fill in the blanks.
    (c) Fill in the blank: The running time of the Algorithm is O(____).
A
Theory Explanation is given below.
       Algorithms        Fill-in-the-Blanks
Question 60 Explanation: 
(a) INITIALIZATION: For i = 1 ... n
{ for j = 1 ... n
{ if a[i,j] = 0 then P[i,j] = infinite;
else P[i,j] = a[i,j];
}
}
(b) ALGORITHM: For i = 1 ... n
{ for j = 1 ... n;
{ for k = 1 ... n
{
P[i,j] = min (P[i,j], P[i,k]+P[k,j])
}
}
}
(c) Actual graph:

MST: There are 2 possible MST's

Question 61

(a) In how many ways can a given positive integer n ≥ 2 be expressed as the sum of 2 positive integers (which are not necessarily distinct). For example, for n = 3, the number of ways is 2, i.e., 1+2, 2+1. Give only the answer without any explanation.

(b) In how many ways can a given positive integer n ≥ 3 be expressed as the sum of 3 positive integers (which are not necessarily distinct). For example, for n = 4, the number of ways is 3, i.e., 1+2+1, 2+1+1. Give only the answer without any explanation.

(c) In how many ways can a given positive integer n ≥ k be expressed as the sum of k positive integers (which are not necessarily distinct)? Give only the answer without explanation.

A
Theory Explanation is given below.
       Engineering-Mathematics       Combinatorics
Question 62

The aim of the following question is to prove that the language {M| M is the code of a Turing Machine which, irrespective of the input, halts and outputs a 1}, is undecidable. This is to be done by reducing form the language {M',x| M' halts on x}, which is known to be undecidable. In parts (a) and (b) describe the 2 main steps in the construction of M. in part (c) describe the key property which relates the behaviour of M on its input w to the behaviour of M′ on x.

    (a) On input w, what is the first step that M must make?
    (b) On input w, based on the outcome of the first step, what is the second step that M must make?
    (c) What key property relates the behaviour of M on w to the behaviour of M′ on x?
A
Theory Explanation is given below.
       Theory-of-Computation       Turing Machine
Question 63

A university placement center maintains a relational database of companies that interview students on campus and make job offers to those successful in the interview. The schema of the database is given below:

  COMPANY (cname, clocation)     STUDENT (scrollno, sname, sdegree)
   INTERVIEW (cname, srollno, idate)  OFFER (cname,srollno, osalary) 

The COMPANY relation gives the name and location of the company. The STUDENT relation gives the student’s roll number, name and the degree program for which the student is registered in the university. The INTERVIEW relation gives the date on which a students is interviewed by a company. The OFFER relation gives the salary offered to a student who is successful in a company’s interview. The key for each relation is indicated by the underlined attributes.

(a) Write relational algebra expressions (using only the operator ⨝,σ,π,∪,−) for the following queries:

    (i) List the rollnumbers and names of those students who attended at least one interview but did not receive any job offer.
    (ii) List the rollnumbers and names of students who went for interviews and received job offers from every company with which they interviewed.

(b) Write an SQL query to list, for each degree program in which more than five students were offered jobs, the name of the degree and the average offered salary of students in this degree program.

A
Theory Explanation is given below.
       Database-Management-System       Relational-Algebra-and-SQL
Question 64

For relation R = (L, M, N , O, P), the following dependencies hold:

   M → O NO → P P → L and L → MN 

R is decomposed into R1 = (L, M, N , P) and R2 = (M, O).

    (a) Is the above decomposition a lossless-join decomposition? Explain.
    (b) Is the above decomposition dependency-preserving? If not, list all the dependencies that are not preserved.
    (c) What is the highest normal form satisfied by the above decomposition?
A
Theory Explanation is given below.
       Database-Management-System       Normalization
Question 65

(a) The following table refers to search times for a key in B-trees and B+-trees.

A successful search means that the key exists in the database and unsuccessful means that it is not present in the database. Each of the entries X1, X2, X3 and X4 can have a value of either Constant or Variable. Constant means that the search time is the same, independent of the specific key value, where Variable means that it is dependent on the specific key value chosen for the search.

Give the correct values for the entries X1, X2, X3 and X4 (for example X1 = Constant, X2 = Constant, X3 = Constant, X4 = Constant).

(b) Relation R(A,B) has the following view defined on it:

 CREATE VIEW V AS
 (SELECT R1.A, R2.B
 FROM R AS R1, R AS R2
 WHERE R1.B = R2.A)

(i) The current contents of relation R are shown below. What are the contents of the view V?

(ii) The tuples (2,11) and (11,6) are now inserted into R. What are the additional tuples that are inserted in V?

A
Theory Explanation is given below.
       Database-Management-System       Descriptive
Question 66

(a) Draw the process state transition diagram of an OS in which (i) each process is in one of the five states: created, ready, running, blocked (i.e. sleep or wait), or terminated, and (ii) only non-preemptive scheduling is used by the OS. Label the transitions appropriately.

(b) The functionality of atomic TEST-AND-SET assembly language instruction is given by the following C function.

 int TEST-AND-SET (int *x)
 {
    int y;
    A1:y=*x;
    A2:*x=1;
    A3:return y;
 } 

(i) Complete the following C functions for implementing code for entering and leaving critical sections based on the above TEST-AND-SET instruction.

 int mutex=0;
 void enter-cs()
 {
 while (…………………………………);
 }
void leave-cs()
 {
 …………………………………..;
 } 

(ii) Is the above solution to the critical section problem deadlock free and starvation-free?

(iii) For the above solution, show by an example that mutual exclusion is not ensured if TEST-AND-SET instruction is not atomic.

A
Theory Explanation is given below.
       Operating-Systems       Descriptive
Question 67

A computer system uses 32-bit virtual address, and 32-bit physical address. The physical memory is byte addressable, and the page size is 4 kbytes. It is decided to use two level page tables to translate from virtual address to physical address. Equal number of bits should be used for indexing first level and second level page table, and the size of each page table entry is 4 bytes.

    (a) Give a diagram showing how a virtual address would be translated to a physical address.
    (b) What is the number of page table entries that can be contained in each page?
    (c) How many bits are available for storing protection and other information in each page table entry?
A
Theory Explanation is given below.
       Operating-Systems       Descriptive
Question 68

The following solution to the single producer single consumer problem uses semaphores for synchronization.

 #define BUFFSIZE 100
 buffer buf[BUFFSIZE];
 int first=last=0;
 semaphore b_full=0;
 semaphore b_empty=BUFFSIZE;
 
void producer()
 {
 while (1) {
     produce an item;
     p1: …………………..;
     put the item into buff (first);
     first=(first+1)%BUFFSIZE;
     p2: …………………..;
        }
 }
 void consumer()
 { 
while (1) {
             c1:……………………..
             take the item from buf[last];
             last=(last+1)%BUFFSIZE;
             c2: ……………………..;
             consume the item;
          }
 } 
    (a) Complete the dotted part of the above solution.
    (b) Using another semaphore variable, insert one line statement each immediately after p1, immediately before p2, immediately after c1, and immediately before c2 so that the program works correctly for multiple procedures and consumers.
A
Theory Explanation is given below.
       Operating-Systems       Descriptive
Question 69

We require a four state automaton to recognize the regular expression (a|b)*abb.

    (a) Give an NFA for this purpose.
    (b) Give a DFA for this purpose.
A
Theory Explanation is given below.
       Theory-of-Computation       Finite-Automata
Question 70

(a) Construct all the parse trees corresponding to i + j * k for the grammar

      E → E+E
      E → E*E
      E → id  
    (b) In this grammar, what is the precedence of the two operators * and +?
    (c) If only one parse tree is desired for any string in the same language, what changes are to be made so that the resulting LALR(1) grammar is non-ambiguous?
A
Theory Explanation is given below.
       Compiler-Design       Descriptive
There are 70 questions to complete.