GATE 1996

Question 1

Let A and B be sets and let Ac and Bc denote the complements of the sets A and B. The set (A – B) ∪ (B - A) ∪ (A∩B) is equal to

A
A ∪ B
B
Ac ∪ Bc
C
A ∩ B
D
Ac ∩ Bc
       Engineering-Mathematics       Sets-And-Relation
Question 1 Explanation: 
(A – B) ∪ (B - A) ∪ (A∩B)

(A - B) = 1
(B - A) = 2
(A∩B) = 3
A∪B = (1∪2∪3)
(A – B) ∪ (B - A) ∪ (A∩B) = 1∪2∪3 = (A∪B)
Question 2

Let X = {2,3,6,12,24}, Let ≤ be the partial order defined by X ≤ Y if x divides y. Number of edge as in the Hasse diagram of (X,≤) is

A
3
B
4
C
9
D
None of the above
       Engineering-Mathematics       Sets-And-Relation
Question 2 Explanation: 

No. of edges = 4
Question 3

Suppose X and Y are sets and X Y and are their respective cardinalities. It is given that there are exactly 97 functions from X to Y. from this one can conclude that

A
|X| = 1, |Y| = 97
B
|X| = 97, |Y| = 1
C
|X| = 97, |Y| = 97
D
None of the above
       Engineering-Mathematics       Sets and Functions
Question 3 Explanation: 
From the given information we can write,
|Y||X| = 97
→ Option A only satisfies.
Question 4

Which of the following statements is false?

A
The set of rational numbers is an abelian group under addition.
B
The set of integers in an abelian group under addition.
C
The set of rational numbers form an abelian group under multiplication.
D
The set of real numbers excluding zero in an abelian group under multiplication.
       Engineering-Mathematics       Sets-And-Relation
Question 4 Explanation: 
Rational number consists of number '0'. If 0 is present in a set inverse is not possible under multiplication.
Question 5

Two dice are thrown simultaneously. The probability that at least one of them will have 6 facing up is

A
1/36
B
1/3
C
25/36
D
11/36
       Engineering-Mathematics       Probability
Question 5 Explanation: 
1 - no. 6 on both dice
1 - (5/6 × 5/6) = 1 - (25/36) = 11/36
Question 6

The formula used to compute an approximation for the second derivative of a function f at a point X0 is

A
f(x0+h) + f(x0-h)/2
B
f(x0+h) - f(x0-h)/2h
C
f(x0+h) + 2f(x0) + f(x0-h)/h2
D
f(x0+h) - 2f(x0) + f(x0-h)/h2
       Engineering-Mathematics       Calculus
Question 6 Explanation: 
The formula which is used to compute the second derivation of a function f at point X is
f(x0+h) - 2f(x0) + f(x0-h)/h2
Question 7

Let Ax = b be a system of linear equations where A is an m × n matrix and b is a m × 1 column vector and X is a n × 1 column vector of unknowns. Which of the following is false?

A
The system has a solution if and only if, both A and the augmented matrix [A b] have the same rank.
B
If m < n and b is the zero vector, then the system has infinitely many solutions.
C
If m = n and b is non-zero vector, then the system has a unique solution.
D
The system will have only a trivial solution when m = n, b is the zero vector and rank (A) = n.
       Engineering-Mathematics       Linear-Algebra
Question 7 Explanation: 
→ It belongs to linear non-homogeneous equations. So by having m=n, we can't say that it will have unique solution.
→ Solution can be depends on rank of matrix A and matrix [A B].
→ If rank[A] = rank[A B] then it can have solution otherwise no solution.
Question 8

Which two of the following four regular expressions are equivalent? (ε is the empty string).

    (i) (00)*(ε+0)
    (ii) (00)*
    (iii) 0*
    (iv) 0(00)*
A
(i) and (ii)
B
(ii) and (iii)
C
(i) and (iii)
D
(iii) and (iv)
       Theory-of-Computation       Regular-Expressions
Question 8 Explanation: 
(00)*(ε+0),0*
In these two, we have any no. of 0's as well as null.
Question 9

Which of the following statements is false?

A
The Halting problem of Turing machines is undecidable.
B
Determining whether a context-free grammar is ambiguous is undecidbale.
C
Given two arbitrary context-free grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
D
Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
       Theory-of-Computation       Decidability-and-Undecidability
Question 9 Explanation: 
Equivalence of regular languages is decidable under
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1st for CSL and REC.
→ None for RE.
Question 10

Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?

A
L = {x|x has an equal number of a's and b's } is regular
B
L = {anbn|n≥1} is regular
C
L = {x|x has more a's and b's} is regular
D
L = {ambn|m ≥ 1, n ≥ 1} is regular
       Theory-of-Computation       Identify-Class-Language
Question 10 Explanation: 
L = {ambn|m ≥ 1, n ≥ 1}
Here, m and n are independent.
So 'L' Is Regular.
Question 11

Which of the following is false?

A
B
C
D
       Algorithms        Time-Complexity
Question 11 Explanation: 
Question 12

Consider the following statements:

    (i) First-in-first out types of computations are efficiently supported by STACKS.
    (ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
    (iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
    (iv) Last-in-first-out type of computations are efficiently supported by QUEUES.

Which of the following is correct?

A
(ii) and (iii) are true
B
(i) and (ii) are true
C
(iii) and (iv) are true
D
(ii) and (iv) are true
       Data-Structures       Stack-and-Queue
Question 12 Explanation: 
(i) FIFO computation efficiently supported by queues.
(iv) LIFO computation efficiently supported by stacks.
Then given (i) and (iv) are false.
Answer:- A
Question 13

An advantage of chained hash table (external hashing) over the open addressing scheme is

A
Worst case complexity of search operations is less?
B
Space used is less
C
Deletion is easier
D
None of the above
       Data-Structures       Hashing
Question 13 Explanation: 
In chained hash tables have advantages over open addressed hash tables in that the removal operation is simple and resizing can be postponed for longer time.
Question 14

In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?

A
1
B
3
C
7
D
8
       Data-Structures       Binary-Trees
Question 14 Explanation: 

a, b, c are going to unbalance.
Question 15

Which of the following sequences denotes the post order traversal sequence of the tree of question 14?

A
f e g c d b a
B
g c b d a f e
C
g c d b f e a
D
f e d g c b a
       Data-Structures       Binary-Trees
Question 15 Explanation: 
Postorder:-
Left → Right → Root
g c d b f e a
Question 16

Relative mode of addressing is most relevant to writing

A
coroutines
B
position – independent code
C
shareable code
D
interrupt handlers
       Computer-Organization       Addressing-Modes
Question 16 Explanation: 
The main advantage of PC- relative addressing is that code may be position independent, i.e., it can be loaded anywhere in memory without the need to adjust any address.
Question 17

The pass number for each of the following activities

    1. Object code generation
    2. Literals added to literal table
    3. Listing printed
    4. Address resolution of local symbols

That occur in a two pass assembler respectively are

A
1, 2, 1, 2
B
2, 1, 2, 1
C
2, 1, 1, 2
D
1, 2, 2, 2
       Compiler-Design       Assembler
Question 17 Explanation: 
The functionalities from pass 1 and pass 2 are:
Pass 1:
1) Assign addresses to all statements in the program.
2) Save the values assigned to all labels for use in pass 2.
3) Perform some processing of assembler directives.
Pass 2:
1) Assemble instructions.
2) Generate data values defined by BYTE, WORD etc.
3) Perform processing of assembler directives not done during pass 1.
4) Write the program and assembling listing.
Question 18

The process state transition diagram in below figure is representative of

A
a batch operating system
B
an operating system with a preemptive scheduler
C
an operating system with a non-preemptive scheduler
D
a uni-programmed operating system
       Operating-Systems       Process-Scheduling
Question 18 Explanation: 
Transaction from running → ready present.
So this is preemptive.
Question 19

A critical section is a program segment

A
which should run in a certain specified amount of time
B
which avoids deadlocks
C
where shared resources are accessed
D
which must be enclosed by a pair of semaphore operations, P and V
       Operating-Systems       Process-Synchronization
Question 19 Explanation: 
In CS, share resources are accessed.
Question 20

Which of the following is an example of spooled device?

A
A line printer used to print the output of a number of jobs.
B
A terminal used to enter input data to a running program.
C
A secondary storage device in a virtual memory system.
D
A graphic display device.
       Operating-Systems       Deadlock-Prevention
Question 20 Explanation: 
Example of spooled device is a line printer used to print the output of a number of jobs.
Question 21

A ROM is sued to store the table for multiplication of two 8-bit unsigned integers. The size of ROM required is

A
256 × 16
B
64 K × 8
C
4 K × 16
D
64 K × 16
       Digital-Logic-Design       ROM
Question 21 Explanation: 
When we multiply the two 8 bit numbers result will reach upto 16 bits. So we require 16 bits for each multiplication output.
No. of results possible = 28 × 28 = 216 = 64K
Then total size of ROM = 64K × 16
Question 22

Number of machine cycles required for RET instruction in 8085 microprocessor is

A
1
B
2
C
3
D
5
       Computer-Organization       Microprocessor
Question 22 Explanation: 
1 for instruction fetch.
2 for stack operation.
Total no. of cycles = 2+1 = 3
Question 23

Both’s algorithm for integer multiplication gives worst performance when the multiplier pattern is

A
101010 …..1010
B
100000 …..0001
C
111111 …..1111
D
011111 …..1110
       Digital-Logic-Design       Booth\'s-Algorithm
Question 23 Explanation: 
When the pairs 01 (or) 10 occur frequently in the multiplier. In that case Booth multiplication gives worst performance.
Question 24

For the daisy chain scheme of connecting I/O devices, which of the following statements is true?

A
It gives non-uniform priority to various devices.
B
It gives uniform priority to all devices
C
It is only useful for connecting slow devices to a processor device.
D
It requires a separate interrupt pin on the processor for each device.
       Computer-Organization       Interrupt
Question 24 Explanation: 
Daisy chaining technique tells the processor in which order the interrupt should be handle by providing priority devices.
→ In this all devices connected serially.
→ High priority devices placed first, followed by low priority devices.
Question 25

Consider the following floating point number representation

The exponent is in 2's complement representation and mantissa is in the sign magnitude representation. The range of the magnitude of the normalized numbers in this representation is

A
0 to 1
B
0.5 to 1
C
2-23 to 0.5
D
0.5 to (1-2-23)
       Digital-Logic-Design       Number-Systems
Question 25 Explanation: 
Maximum value of mantissa will be 23, is where a decimal point is assumed before first 1. So the value is 1 - 2-23.
Question 26

Let R denotes the set of real numbers. Let f: R×R → R×R be a bijective function defined by f(x,y) = (x+y,x-y), The inverse function of f is given by

A
B
C
D
       Engineering-Mathematics       Sets and Functions
Question 26 Explanation: 
Question 27

Let R be a non-empty relation on a collection of sets defined by A R B if and only if A ∩ B = ф. Then, (pick the true statement)

A
R is reflexive and transitive
B
R is symmetric and not transitive
C
R is an equivalence relation
D
R is not reflexive and not symmetric
       Engineering-Mathematics       Sets-And-Relation
Question 27 Explanation: 
Let A = {1, 2, 3} and B = {4, 5} and C = {1, 6, 7}
Now,
A ∩ B = ф
& B ∩ C = ф
But A ∩ B ≠ ф
So, R is not transitive.
A ∩ B = A, so R is not reflexive.
If A ∩ B = ф
then definitely B ∩ A = ф.
Hence, R is symmetric.
So, option (B) is true.
Question 28

Which of the following is false? Read ∧ as AND, ∨ as OR, ~ as NOT, → as one way implication and ↔ as two way implication.

A
((x → y) ∧ x) → y
B
((x → y) ∧ (x ∧ y)) → x
C
(x → (x ∨ ψ))
D
((x ∨ y) ↔ (x → y)
       Engineering-Mathematics       Propositional-Logic
Question 28 Explanation: 
When x = F and y = F
then option (D) will be False.
Question 29

Which one of the following is false?

A
The set of all bijective functions on a finite set forms a group under function composition.
B
The set {1, 2, ……., p–1} forms a group under multiplication mod p where p is a prime number.
C
The set of all strings over a finite alphabet forms a group under concatenation.
D
A subset s ≠ ф of G is a subgroup of the group if and only if for any pair of elements a, b ∈ s, a* b-1 ∈ s.
       Engineering-Mathematics       Sets-And-Relation
Question 29 Explanation: 
Option (C) is False because string concatenation operation is monoid (doesn't have inverse to become a group).
Question 30

Newton-Raphson iteration formula for finding 3√c, where c > 0 is,

A
B
C
D
       Engineering-Mathematics       Newton-Raphson-Method
Question 30 Explanation: 
Note: Out of syllabus.
Question 31

The matrices and commute under multiplication

A
if a = b or θ = nπ, is an integer
B
always
C
never
D
if a cos θ ≠ b sin θ
       Engineering-Mathematics       Linear-Algebra
Question 31 Explanation: 
Question 32

The probability that top and bottom cards of a randomly shuffled deck are both aces in

A
4/52×4/52
B
4/52×3/52
C
4/52×3/51
D
4/52×4/51
       Engineering-Mathematics       Probability
Question 32 Explanation: 
E1 : First card being ace
E2 : Last card being ace
Note that E1 and E2 are dependent events, i.e., probability of last card being ace if first is ace will be lesser than the probability of last card being ace if first card is not ace.
So, probability of first card being ace = 4/52
Probability of last card being ace given that first card is ace is,
P(E2 / E1) = 3/51
∴ P(E1 and E2) = P(E1) ⋅ P(E2 / E1) = 4/52 × 3/51
Question 33

If L1 and L2 are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?

A
L1, L2
B
L1 ∩ L2
C
L1 ∩ R
D
L1 ∪ L2
       Theory-of-Computation       Identify-Class-Language
Question 33 Explanation: 
Context free languages are not closed under intersection.
Question 34

Define for a context free language L ⊆ {0,1}*, init(L) = {u ∣ uv ∈ L for some v in {0,1}∗} (in other words, init(L) is the set of prefixes of L)
Let L = {w ∣ w is nonempty and has an equal number of 0’s and 1’s}
Then init(L) is

A
the set of all binary strings with unequal number of 0’s and 1’s
B
the set of all binary strings including the null string
C
the set of all binary strings with exactly one more 0’s than the number of 1’s or one more 1 than the number of 0’s
D
None of the above
       Theory-of-Computation       Context-Free-Language
Question 34 Explanation: 
(B) is the answer. Because for any binary string of 0's and 1's we can append another string to make it contain equal no. of 0's and 1's, i.e., any string over {0,1} is a prefix of a string in L.
Question 35

The grammar whose productions are

  → if id then 
  → if id then   else 
  → id := id 

is ambiguous because

A
the sentence
if a then if b then c:=d
B
the left most and right most derivations of the sentence
if a then if b then c:=d
give rise top different parse trees
C
the sentence
if a then if b then c:=d else c:=f
has more than two parse trees
D
the sentence
if a then if then c:=d else c:=f
has two parse trees
       Theory-of-Computation       Context-Free-Language
Question 35 Explanation: 
We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:

Parse tree 2:
Question 36

The minimum number of interchanges needed to convert the array

 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70  

into a heap with the maximum element at the root is

A
0
B
1
C
2
D
3
       Data-Structures       Heap-Tree
Question 36 Explanation: 
Lets draw first heap from given sequence,

Question 37

The recurrence relation

 T(1) = 2
 T(n) = 3T(n/4)+n 

has the solution, T(n) equals to

A
O(n)
B
O(log n)
C
O(n3/4)
D
None of the above
       Algorithms        Time-Complexity
Question 37 Explanation: 
Apply Master's theorem.
Question 38

The average number of key comparisons done on a successful sequential search in list of length n is

A
log n
B
n-1/2
C
n/2
D
n+1/2
       Algorithms        Time-Complexity
Question 38 Explanation: 
Total comparisons required
= No. of comparisons if element present in 1st position + No. of comparisons if element present in 2nd position + ............. + No. of comparisons if element present in nth position
= 1 + 2 + 3 + ... + n
= n(n+1)/2
Since there are n elements in the list, so average no. of comparisons
= Total comparisons/Total no. of elements
= (n(n+1)/2)/n
= n+1/2
Question 39

A binary search tree is generated by inserting in order the following integers:

 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24  

The number of nodes in the left subtree and right subtree of the root respectively is

A
(4, 7)
B
(7, 4)
C
(8, 3)
D
(3, 8)
       Data-Structures       Binary-Trees
Question 39 Explanation: 
50 is the root node in BST.
So greater than 50 will be in right subtree of 50 and less than 50 in left subtree.
So, answer will be (7, 4).
Question 40

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot,

(i) 1,2,3,...,n
(ii) n,n-1,n-2,...,2,1 

Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

A
C1 < C2
B
C1 > C2
C
C1 = C2
D
we cannot say anything for arbitrary n.
       Algorithms        Time-Complexity
Question 40 Explanation: 
Both are the worst cases of Quick sort, i.e., either the elements are already in increasing order or the elements are already in decreasing order.
So, option is (C) is correct.
Question 41

Which of the following macros can put a micro assembler into an infinite loop?

(i)  .MACRO M1 X
     .IF EQ, X      ;if X=0 then
      M1 X + 1
     .ENDC
     .IF NE X       ;IF X≠0 then
     .WORD X        ;address (X) is stored here
     .ENDC
     .ENDM
(ii) .MACRO M2 X
     .IF EQ X
      M2 X
     .ENDC
     .IF NE, X
     .WORD X+1
     .ENDC
     .ENDM 
A
(ii) only
B
(i) only
C
both (i) and (ii)
D
None of the above
       Compiler-Design       Macros
Question 41 Explanation: 
If M2 macro is called with X=0, then it will go into an infinite loop.
Question 42

The correct matching for the following pairs is

         A. Activation record	   1. Linking loader
         B. Location counter	   2. Garbage collection
         C. Reference counts	   3. Subroutine call
         D. Address relocation	   4. Assembler 
A
A – 3 B – 4 C – 1 D – 2
B
A – 4 B – 3 C – 1 D – 2
C
A – 4 B – 3 C – 2 D – 1
D
A – 3 B – 4 C – 2 D – 1
       Operating-Systems       Match-the-Following
Question 42 Explanation: 
Each time a subroutine is called its activation record is created.
An assembler uses location counter value to give address to each instruction which is needed for relative addressing as well as for jump labels.
Reference count is used by garbage collector to clear the memory whose reference count be comes 0.
Linker loader is a loader which can load several compiled codes and link them together into a single executable. Thus it needs to do relocation of the object codes.
Question 43

A 1000 Kbyte memory is managed using variable partitions but to compaction. It currently has two partitions of sizes 200 Kbytes and 260 Kbytes respectively. The smallest allocation request in Kbytes that could be denied is for

A
151
B
181
C
231
D
541
       Operating-Systems       Virtual Memory
Question 43 Explanation: 
200 and 260 are already hold by some other processes. Now we have to model the partition in such a way so that smallest allocation request could be denied. So, we can do the division as,

So, smallest allocation request which can be denied is 181 KB.
Question 44

A solution to the Dining Philosophers Problem which avoids deadlock is

A
ensure that all philosophers pick up the left fork before the right fork
B
ensure that all philosophers pick up the right fork before the left fork
C
ensure that one particular philosopher picks up the left fork before the right fork, and that all other philosophers pick up the right fork before the left fork
D
None of the above
       Operating-Systems       Deadlock
Question 44 Explanation: 
In the Dining philosopher problem, each philosopher needs exactly two chopsticks to eat food but the problem is: each philosopher is going to take one chopstick at a time, which is placed at its right-hand side or at its left-hand side, but remember all should choose in the same manner like if first one chooses in a clockwise manner then each one should choose in clockwise, this type of picking cause, a circular waiting loop because each one is depending on other. This is also called as circular waiting and it leads to deadlock.
To avoid this, atleast one philosopher should choose its first chopstick in different way so that circular loop is not formed.
Question 45

Four jobs to be executed on a single processor system arrive at time 0+ in the order A, B, C, D. their burst CPU time requirements are 4, 1, 8, 1 time units respectively. The completion time of A under round robin scheduling with time slice of one time unit is

A
10
B
4
C
8
D
9
       Operating-Systems       Process-Scheduling
Question 45 Explanation: 
Time quantum is 1 unit.

∴ Completion time of A is 9 unit.
Question 46

Consider the circuit given below which has a four bit binary number b3b2b1b0 as input and a five bit binary number d4d3d2d1d0 as output. The circuit implements:

A
Binary of Hex conversion
B
Binary to BCD conversion
C
Binary to grey code conversion
D
Binary to radix-12 conversion
       Digital-Logic-Design       Adder
Question 46 Explanation: 
Here ф means 0.
Whenever, b2 = b3 = 1, then only 0100, i.e., 4 is added to the given binary number. Lets write all possibilities for b.

Note that the last 4 combinations leads to b3 and b2 as 1. So, in these combinations only 0010 will be added.
1100 is 12
1101 is 13
1110 is 14
1111 is 15
in binary unsigned number system.
1100 + 0100 = 10000
1101 + 0100 = 10001, and so on.
This is conversion to radix 12.
Question 47

Consider the circuit in below figure. f implements

A
B
A + B + C
C
A ⊕ B ⊕ C
D
AB + BC + CA
       Digital-Logic-Design       Multiplexer
Question 47 Explanation: 
Question 48

Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be

A
4
B
3
C
2
D
1
       Theory-of-Computation       Finite-Automata
Question 48 Explanation: 
3 states are required in the minimized machine states B and C can be combined as follows:
Question 49

What is the equivalent Boolean expression in product-of-sums form for the Karnaugh map given below.

A
B
C
D
E
None of the above
       Digital-Logic-Design       K-Map
Question 49 Explanation: 
Correct option is

Question 50

A micro program control unit is required to generate a total of 25 control signals. Assume that during any microinstruction, at most two control signals are active. Minimum number of bits required in the control word to generate the required control signals will be

A
2
B
2.5
C
10
D
12
       Computer-Organization       Control-Signals
Question 50 Explanation: 
To generate 1 out of 25 different control signals we need 5 bits. But at any time atmost 2 signals can be active. So control word length
= 5+5
= 10 bits
Question 51

Let f be a function defined by

Find the values for the constants a, b, c and d so that f is continuous and differentiable every where on the real line.

A
Theory Explanation.
Question 52

A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain.

A
61 52 14 17 40 43
B
2 3 50 40 60 43
C
10 65 31 48 37 43
D
81 61 52 14 41 43
E
17 77 27 66 18 43
Question 53

A logic network has two data inputs A and B, and two control inputs C0 and C1. It implements the function F according to the following table.

Implement the circuit using one 4 to 1 Multiplexer, one 2-input Exclusive OR gate, one 2-input AND gate, one 2-input OR gate and one Inverter.

A
Theory Explanation.
Question 54

An 8052 based system has an output port with address 00H. Consider the following assembly language program.

     ORG    0100H
     MVI    A, 00H
     LXI    H, 0105H
     OUT    00H
     INR    A
     PCHL
     HLT   

(a) What does the program do with respect to the output port 00H?
(b) Show the wave forms at the three least significant bits of the port 00H.

A
Theory Explanation.
Question 55

A demand paged virtual memory system uses 16 bit virtual address, page size of 256 bytes, and has 1 Kbyte of main memory. LRU page replacement is implemented using a list whose current status (page number in decimal) is

For each hexadecimal address in the address sequence given below

 00FF, 010D, 10FF, 11B0

indicate
(i) the new status of the list
(ii) page faults, if any, and
(iii) page replacements, if any

A
Theory Explanation.
Question 56

Let F be the collection of all functions f: {1,2,3} → {1,2,3}. If f and g ∈ F, define an equivalence relation ~ by f ~ g if and only if f(3) = g(3).
a) Find the number of equivalence classes defined by ~.
b) Find the number of elements in each equivalence class.

A
Theory Explanation.
Question 57

The Fibonacci sequence {f1,f2,f3,...,fn} is defined by the following recurrence:

   fn+2 = fn+1 + fn, n ≥ 1; f2=1 : f1=1 

Prove by induction that every third element of the sequence is even.

A
Theory Explanation.
Question 58

Let and be two matrices such that AB = I. Let and CD = 1. Express the elements of D in terms of the elements of B.

A
Theory Explanation.
Question 59

Let G be a context-free grammar where G = ({S, A, B, C},{a,b,d},P,S) with the productions in P given below.

   S → ABAC
   A → aA ∣ ε
   B → bB ∣ ε
   C → d  

(ε denotes null string). Transform the grammar G to an equivalent context-free grammar G' that has no ε productions and no unit productions. (A unit production is of the form x → y, and x and y are non terminals.)

A
Theory Explanation.
Question 60

Given below are the transition diagrams for two finite state machine M1 and M2 recognizing languages L1 and L2 respectively.
(a) Display the transition diagram for a machine that recognizes L1.L2, obtained from transition diagrams for M1 and M2 by adding only ε transitions and no new states.
(b) Modify the transition diagram obtained in part(a) obtain a transition diagram for a machine that recognizes (L1.L2)∗ by adding only ε transitions and no new states. (Final states are enclosed in double circles).

A
Theory Explanation.
Question 61

Let Q = ({q1,q2}, {a,b}, {a,b,Z}, δ, Z, ϕ) be a pushdown automaton accepting by empty stack for the language which is the set of all non empty even palindromes over the set {a,b}. Below is an incomplete specification of the transitions δ. Complete the specification. The top of the stack is assumed to be at the right end of the string representing stack contents.

(1) δ(q1,a,Z) = {(q1,Za)}
(2) δ(q1,b,Z) = {(q1,Zb)}
(3) δ(q1,a,a) = {(.....,.....)}
(4) δ(q1,b,b) = {(.....,.....)}
(5) δ(q2,a,a) = {(q2,ϵ)}
(6) δ(q2,b,b) = {(q2,ϵ)}
(7) δ(q2,ϵ,Z) = {(q2,ϵ)} 
A
Theory Explanation.
Question 62

A two dimensional array A[1...n][1...n] of integers is partially sorted if

    ∀i, j ∈ [1...n−1],   A[i][j] < A[i][j+1] and 
                           A[i][j] < A[i+1][j] 

Fill in the blanks:
(a) The smallest item in the array is at A[i][j] where i=............and j=..............
(b) The smallest item is deleted. Complete the following O(n) procedure to insert item x (which is guaranteed to be smaller than any item in the last row or column) still keeping A partially sorted.

procedure  insert (x: integer);
var        i,j: integer;
begin
(1) i:=1; j:=1, A[i][j]:=x;
(2) while (x > ...... or x > ......) do
(3) if A[i+1][j] < A[i][j] ......... then begin
(4) A[i][j]:=A[i+1][j]; i:=i+1;
(5) end
(6) else begin
(7) ............
(8) end
(9) A[i][j]:= .............
    end  
A
Theory Explanation.
Question 63

Insert the characters of the string K R P C S N Y T J M into a hash table of size 10.
Use the hash function

 h(x) = (ord(x) – ord("a") + 1) mod10 

and linear probing to resolve collisions.
(a) Which insertions cause collisions?
(b) Display the final hash table.

A
Theory Explanation.
Question 64

A complete, undirected, weighted graph G is given on the vertex {0, 1,...., n−1} for any fixed ‘n’. Draw the minimum spanning tree of G if
(a) the weight of the edge (u,v) is ∣u − v∣
(b) the weight of the edge (u,v) is u + v

A
Theory Explanation.
Question 65

Let G be the directed, weighted graph shown in below figure.

We are interested in the shortest paths from A.
(a) Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node A.
(b) Write down sequence of vertices in the shortest path from A to E.
(c) What is the cost of the shortest path from A to E?

A
Theory Explanation.
Question 66

Consider the following program that attempts to locate an element x in a sorted array a[] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?

      var          i,j,k: integer; x: integer;
                   a:= array; [1...N] of integer;
      begin	   i:= 1; j:= N;
      repeat	   k:(i+j) div 2;
                   if a[k] < x then i:= k 
                   else j:= k 
      until (a[k] = x) or (i >= j);
      if (a[k] = x) then
      writeln ('x is in the array')
      else
      writeln ('x is not in the array')
      end; 
A
Theory Explanation.
Question 67

Consider the following program in pseudo-pascal syntax. What is printed by the program if parameter a in procedure test 1 is passed as
(i) call-by-reference parameter
(ii) call-by-value-result parameter

     program Example (input, output)
     var b: integer;
     procedure test2:
     begin b:=10; end
    procedure test1 (a:integer):
     begin 	a:=5;
                writeln ('point 1: ', a, b);
                test2;
                writeln ('point 2: ', a, b);
     end
     begin(*Example*)
     b:=3; test1(b);
     writeln('point3:', b);
     end 
A
Theory Explanation.
Question 68

Consider the syntax-directed translation schema (SDTS) shown below:

    E → E + E  {print “+”}
    E → E ∗ E  {print “.”}
    E → id     {print id.name}
    E → (E) 

An LR-parser executes the actions associated with the productions immediately after a reduction by the corresponding production. Draw the parse tree and write the translation for the sentence.

(a+b)∗(c+d), using the SDTS given above. 
A
Theory Explanation.
Question 69

The concurrent programming constructs fork and join are as below:
fork

   N = 2
   M = 2
   fork L3
   fork L4
   S1
L1:join N
   S3
L2:join M
   S5
L3:S2
   goto L1
L4:S4
   goto L2
next: 
A
Theory Explanation.
Question 70

A computer system uses the Banker’s Algorithm to deal with deadlocks. Its current state is shown in the table below, where P0, P1, P2 are processes, and R0, R1, R2 are resources types.

(a) Show that the system can be in this state.
(b) What will the system do on a request by process P0 for one unit of resource type R1?

A
Theory Explanation.
Question 71

A file system with a one-level directory structure is implemented on a disk with disk block size of 4K bytes. The disk is used as follows:

 Disk-block 0: File Allocation Table, consisting of one 8-bit entry per date block, 
               representing the data block address of the next date block in the file
 Disk block 1: Directory, with one 32 bit entry per file:
 Disk block 2: Data block 1;
 Disk block 3: Data block 2; etc. 

(a) What is the maximum possible number of files?
(b) What is the maximum possible file size in blocks?

A
Theory Explanation.
Question 72

Consider the synchronous sequential circuit in the below figure.

(a) Draw a state diagram, which is implemented by the circuit. Use the following names for the states corresponding to the values of flip-flops as given below.

(b) Given that the initial state of the circuit is S4, identify the set of states, which are not reachable.

A
Theory Explanation.
Question 73

A hard disk is connected to a 50 MHz processor through a DMA controller. Assume that the initial set-up of a DMA transfer takes 1000 clock cycles for the processor, and assume that the handling of the interrupt at DMA completion requires 500 clock cycles for the processor. The hard disk has a transfer rate of 2000 Kbytes/sec and average block transferred is 4 K bytes. What fraction of the processor time is consumed by the disk, if the disk is actively transferring 100% of the time?

A
Theory Explanation.
Question 74

A computer system has a three level memory hierarchy, with access time and hit ratios as shown below:

(a) What should be the minimum sizes of level 1 and 2 memories to achieve an average access time of less than 100 nsec?
(b) What is the average access time achieved using the chosen sizes of level 1 and level 2 memories?

A
Theory Explanation.
Question 75

A library relational database system uses the following schema

USERS (User#, UserName, HomeTown)
BOOKS (Book#, BookTitle, AuthorName)
ISSUED (Book#, User#, Date) 

Explain in one English sentence, what each of the following relational algebra queries is designed to determine

(a) σ User #=6 (11 User #, Book Title ((USERS ISSUED) BOOKS))
(b) σ Author Name (BOOKS (σ Home Town) = Delhi (USERS ISSUED))) 
A
Theory Explanation.
There are 75 questions to complete.