Merge sort uses

For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of

Which of the following statements is true?
I. As the number of entries in a hash table increases, the number of collisions increases.
II. Recursive programs are efficient
III. The worst case complexity for Quicksort is O(n²)
IV. Binary search using a linear linked list is efficient.

Which of the following strings can definitely be said to be tokens without looking at the next input character while compiling a Pascal program?

I. begin
II. program
III. <>

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar.

$$\eqalign{ & S \to xxW\,\left\{ {pr{\mathop{\rm int}} \,'1'} \right\} \cr & S \to y\,\left\{ {pr{\mathop{\rm int}} \,'2'} \right\} \cr & W \to Sz\,\left\{ {pr{\mathop{\rm int}} \,'3'} \right\} \cr} $$

What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?

In some programming languages, an identifier is permitted to be a letter following by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?

A linker is given object modules for a set of programs that were compiled separately. What information need to be included in an object module?

A $$ROM$$ is used to store a truth table for a binary multiplier unit that will multiply two $$4$$ bit numbers. The size of the $$ROM$$ (number of words $$ \times $$ number of bits) that is required to accommodate the truth table is $$M$$ words $$ \times $$ $$N$$ bits. Write the values of $$M$$ and $$N$$.

A computer system has a $$4K$$ word cache organized in block set associative manner with $$4$$ blocks per set, $$64$$ words per block. The number of bits in the $$SET$$ and $$WORD$$ fields of the main memory address format is

The capacity of a memory unit is defined by the number of words multiplied by the number of bits/word. How many separate address and data lines are needed for a memory of $$4K$$ $$ \times $$ $$16?$$

In a vectored interrupt

A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is:

The postfix expression for the infix expression A + B * (C + D) / F + D * E is:

(a) Consider the relation scheme $$R(A, B, C)$$ with the following functional dependencies:
$$\eqalign{ & A,B \to C \cr & \,\,\,\,\,\,C \to A \cr} $$
Show that the scheme $$R$$ is the Third Normal Form $$(3NF)$$ but not in Boyce-Code Normal Form $$(BCNF).$$

(b) Determine the minimal keys of relation $$R.$$

$$\mathop {Lim}\limits_{x \to \infty } {{{x^3} - \cos x} \over {{x^2} + {{\left( {\sin x} \right)}^2}}} = \_\_\_\_\_\_.$$

Let $$R$$ be a symmetric and transitive relation on a set $$A$$. Then

A bag contains 10 white balls and 15 black balls. Two balls drawn in succession. The probability that one of them is black the other is white is

The number of elements in the power set $$P(S)$$ of the set $$S = \left\{ {\left\{ \phi \right\},1,\left\{ {2,3} \right\}} \right\}$$ is

If the proposition $$\neg p \Rightarrow q$$ is true, then the truth value of the proposition $$\neg p \vee \left( {p \Rightarrow q} \right)$$ where $$'\neg '$$ is negation, $$' \vee '$$ is inclusive or and $$' \Rightarrow '$$ is implication, is

Let A be the set of all nonsingular matrices over real numbers and let * be the matrix multiplication operator. Then

The rank of the following (n + 1) x (n + 1) matrix, where a is a real number is $$$\left[ {\matrix{ 1 & a & {{a^2}} & . & . & . & {{a^n}} \cr 1 & a & {{a^2}} & . & . & . & {{a^n}} \cr . & . & . & . & . & . & . \cr . & . & . & . & . & . & . \cr . & . & . & . & . & . & . \cr 1 & a & {{a^2}} & . & . & . & {{a^n}} \cr } } \right]$$$

If at every point of a certain curve, the slope of the tangent equals $${{ - 2x} \over y}$$ the curve is

Let $${G_1}$$ and $${G_2}$$ be subgroups of a group $$G$$.
(a) Show that $${G_1}\, \cap \,{G_2}$$ is also a subgroup of $$G$$.
(b) $${\rm I}$$s $${G_1}\, \cup \,{G_2}$$ always a subgroup of $$G$$?

How many minimum spanning tress does the following graph have? Draw them (Weights are assigned to the edges).

Prove that in a finite graph, the number of vertices of odd degree is always even.

The rank of the following (n + 1) x (n + 1) matrix, where a is a real number is $$$\left[ {\matrix{ 1 & a & {{a^2}} & . & . & . & {{a^n}} \cr 1 & a & {{a^2}} & . & . & . & {{a^n}} \cr . & . & . & . & . & . & . \cr . & . & . & . & . & . & . \cr . & . & . & . & . & . & . \cr 1 & a & {{a^2}} & . & . & . & {{a^n}} \cr } } \right]$$$

The probability that a number selected at random between $$100$$ and $$999$$ (both inclusive ) will not contain the digit $$7$$ is

In a paged segmented scheme of memory management, the segment table itself must have a page table because:

The principle of locality justifies the use of

The address sequence generated by tracing a particular program executing in a pure demand paging system with $$100$$ records per page with $$1$$ free main memory frame is recorded as follows. What is the number of page faults?

$$0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370 $$

A linker is given object modules for a set of programs that were compiled separately. What information need to be included in an object module?

A computer installation has 1000K of main memory. The jobs arrive and finish in the following sequence.
Job 1 requiring 200k arrives
Job 2 requiring 350k arrives
Job 3 requiring 300k arrives
Job 1 finishes
Job 4 requiring 120k arrives
Job 5 requiring 150k arrives
Job 6 requiring 80k arrives

(a) Draw the memory allocation table using Best Fit and First fit algorithm.
(b) Which algorithm performs better for this sequence?

In a virtual memory system the address space specified by the address lines of the $$CPU$$ must be __________ than the physical memory size and _______ than the secondary storage size.

The capacity of a memory unit is defined by the number of words multiplied by the number of bits/word. How many separate address and data lines are needed for a memory of $$4K\,\, \times \,\,16?$$

If the disk in (a) is rotating at $$3600$$ rpm, determine the effective data transfer rate which is defined as the number of bytes transferred per second between disk and memory.

If the overhead for formatting a disk is $$96$$ bytes for $$40000$$ bytes sector, Compute the unformatted capacity of the disk of the following parameters:
Number of surface: $$8$$
Outer diameter of the disk : $$12cm$$
Inner diameter of the disk: $$4cm$$
Inter track space: $$0.1mm$$
Number of sectors per track: $$20$$

The head of a moving head disk with $$100$$ tracks numbered $$0$$ to $$99$$ is currently serving a request at tract $$55.$$ If the queue of requests kept in $$FIFO$$ order is $$10, 70, 75, 23, 65$$ Which of the two disk scheduling algorithms $$FCFS$$ (First Come First Served) and $$SSTF$$ (Shortest Seek Time First) will require less head movement? Find the head movement for each of the algorithms.

The sequence $$.........$$ is an optimal non-preemptive scheduling sequence for the following jobs which leaves the $$CPU$$ idle for $$..........$$ Unit (s) of time

Which scheduling policy is most suitable for a time-shared operating systems?

What are x and y in the following macro definition?

macro Add x,y
Load y
Mul x
Store y
end macro

What is the value of X printed by the following program?

program COMPUTE (input, output);
var
    X:integer;
procedure FIND (X:real);
    begin
    X:=sqrt(X);
    end;
begin
   X:=2
   Find(X)
   Writeln(X)
end

A finite state machine with the following state table has a single input $$X$$ and a single out $$Z$$.

If the initial state is unknown, then the shortest input sequence to reach the final state $$C$$ is here, since initial make unknown $$m$$ $$10$$ input we can each final state $$C$$ with shortest path.

Which of the following definitions below generates the same language as $$L$$
Where $$L = {\left\{ x \right.^n}{y^n}\left| {n \ge \left. 1 \right\}} \right.$$
i) $$\,\,E \to xEy\left| {xy} \right.$$
ii) $$\,\,xy\left| {\left( {{x^ + }xy{y^ + }} \right)} \right.$$
iii) $${\,\,{x^ + }{y^ + }}$$
$$L = \left\{ {xn\,{y^n}\left| {n \ge 1} \right.} \right\} - $$ generates string where equal no. of $$x$$ and equal no. of $$y's.$$
$$E \to XBy\left| {xy\,abo} \right.$$ generators tips same.

Consider the grammar with the following productions.
$$S \to a\,\alpha \,\,b\left| {\,\,b\,\alpha } \right.\,c\,\left| {aB} \right.$$
$$S \to \alpha S\,\left| b \right.$$
$$S \to \alpha \,bb\,\left| {ab} \right.$$
$$S\alpha \to bdb\,\left| b \right.$$
the above grammar is