GATE CSE
89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70
into a heap with the maximum element at the root isi) 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,
T(1) = 2
T(n) = 3T(n/4) + n
has the solution, T(n) equals to
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
(i) object code generation
(ii) literals added to literal table
(iii) listing printed
(iv) address resolution of local symbols that occur in a two pass assembler respectively are



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

The exponent is in $$2’s$$ complement representation and mantissa is in the sign magnitude representation. The range of the magnitude of the normalized mantissa in this representation is
(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.

A library relational database system uses the following schema
USERS (User #, User Name, Home Town)
BOOKS (Books # Book Title, Author Name)
ISSUED (Book #, User #, Date)
Explain in one English sentence, what each of the following relational algebra queries is designed to determine.(a) $$\sigma_{ \text{User#}=6}\left(\pi_{\text{User#, Book Title}}\left(\left(\text{USERS} \bowtie \text{ISSUED}\right) \bowtie \text{BOOKS}\right)\right)$$
(b) $$\pi_{\text{Author Name}}\left(\text{BOOKS} \bowtie \sigma_{\text{Home Town=Delhi}} \left(\text{USERS} \bowtie \text{ISSUED}\right)\right)$$

(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 $${S_4},$$ identify the set of states which are not reachable.
Implement the circuit using one $$4$$ to $$1$$ Multiplexor, one $$2$$-input Exclusive $$OR$$ gate, one $$2$$-input $$AND$$ gate, one $$2$$-input $$OR$$ gate and one Inverter.

two matrices such that $$AB=1.$$
Let $$C = A\left[ {\matrix{ 1 & 0 \cr 1 & 1 \cr } } \right]$$ and $$CD=1.$$
Express the elements of $$D$$ in terms of the elements of $$B.$$
$$T\left( n \right) = 3T\left( {{n \over 4}} \right) + n$$ has the solution $$T(n)$$ equal to
$$\left[ {\matrix{ a & 0 \cr 0 & b \cr } } \right]\,$$ commute under multiplication
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:

$$\eqalign{ & \,\, \uparrow \cr & LRU\,Page \cr} $$
For each hexa decimal 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
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) 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?

List - I
(A) Activation record
(B) Location counter
(C) Reference counts
(D) Address relocation
List - II
(1) Linking loader
(2) Garbage collection
(3) Subroutine call
(4) Assembler
(i) $${\left( {00} \right)^ * }\left( {\varepsilon + 0} \right)$$
(ii) $${\left( {00} \right)^ * }$$
(iii) $${0^ * }$$
(iv) $$0\,\,{\left( {00} \right)^ * }$$
$$\eqalign{ & S \to ABAC\,\,\,\,\,\,\,\,\,S \to aA{\mkern 1mu} \left| \varepsilon \right. \cr & S \to bB{\mkern 1mu} \left| \varepsilon \right.\,\,\,\,\,\,\,\,\,\,\,\,\,\,C \to d \cr} $$
($$\varepsilon $$ denotes the null string). Transform the given grammar $$G$$ to an equivalent context- free grammar $${G^1}$$ that has no $$\varepsilon $$ productions ($$A$$ unit production is of the from $$x \to y,\,x$$ and $$y$$ are non terminals).