The maximum gate delay for any output to appear in an array multiplier for multiplying two n bit number is

Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is

The number of articulation points of the following graph is

A sorting technique is called stable if:

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order of these elements after the second pass of the algorithm is:

If T₁ = O(1), give the correct matching for the following pairs:

List - I

(M) T_n = T_{n - 1} + n
(N) T_n = T_n/2 + n
(O) T_n = T_n/2 + nlog n
(P) T_n = T_{n - 1} + log n

List - II

(U) T_n= O(n)
(V) T_n = O(nlogn)
(W) T_n = O(n²)
(X) T_n = O(log²n)

The number of tokens in the Fortran statement DO 10 I = 1.25 is

The main memory of a computer has $$2$$ $$cm$$ blocks while the cache has $$2$$ $$c$$ blocks. If the cache uses the set associative mapping scheme with $$2$$ blocks per set, then block $$k$$ of the main memory maps to the set:

An instruction pipeline consists of $$4$$ stages: Fetch (F), Decode field (D), Execute (E), and Result-Write (W). The $$5$$ instructions in a certain instruction sequence need these stages for the different number of clock cycles as shown by the table below.

Find the number of clock cycles needed to perform the $$5$$ instructions

Booth’s coding in $$8$$ bits for the decimal number –$$57$$ is:

The main difference (s) between a $$CISC$$ and a $$RISC$$ processor is/are that a $$RISC$$ processor typically:

RAID configurations of disks are used to provide

The number of full and half-adders required to add 16-bit numbers is:

Let $$R=(A,B,C,D,E,F)$$ be a relation scheme with the following dependencies: $$C \to F,\,E \to A,\,EC \to D,\,A \to B.$$ Which of the following is a key for $$R?$$

Consider the schema $$R = \left( {S\,\,T\,\,U\,\,V} \right)$$ and the dependencies $$S \to T,\,\,T \to U,\,\,U \to V$$ and $$V \to S$$ let $$R =$$ $$(R1$$ and $$R2)$$ be a decomposition such that $$R1 \cap R2 \ne \phi .$$ The decomposition is:

Which of the following is/are correct?

Consider the set of relations

EMP (Employee-no, Dept-no, Employee-name, Salary)
DEPT (Dept-no, Dept-name, Location)

Write an SQL query to:

(a) Find all employee names who work in departments located at "Calcutta" and whose salary is greater than Rs.50,000.

(b) Calculate, for each department number, the number of employees with a salary greater than Rs.1,00,000.

Consider the join of a relation R with a relation S. If R has m tuples and S has n tuples then the maximum and minimum sizes of the join respectively are

The relational algebra expression equivalent to the following tuple calculus expression:

$$\left\{ {t|t \in r \wedge \left( {t\left[ A \right] = 10 \wedge t\left[ B \right] = 20} \right)} \right\}$$ is:

For the schedule given below, which of the following is correct:

Which of the following is correct?

Zero has two representations in:

Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function?

Which of the following functions implements the Karnaugh map shown below?

Suppose that the expectation of a random variable X is 5. Which of the following statements is true?

Let X and Y be two exponentially distributed and independent random variables with mean $$\alpha $$ and $$\beta $$, respectively. If Z = min (X, Y), then the mean of Z is given by

Consider two events $${{E_1}}$$ and $${{E_2}}$$ such that probability of $${{E_1}}$$, Pr [$${{E_1}}$$] = 1/2, probability of $${{E_2}}$$, Pr[$${{E_2}}$$ = 1/3, and probability of $${{E_1}}$$ and $${{E_2}}$$, $$\left[ {{E_1}\,\,or\,\,{E_2}} \right]$$ = 1/5. Which of the following statements is /are true?

Let $$\left( {\left\{ {p,\,q} \right\},\, * } \right)$$ be a semi group where $$p * p = q$$. Show that: (a) $$p * q = q * p,$$, and (b) $$q * q = q$$

(a) Show that the formula $$\left[ {\left( { \sim p \vee Q} \right) \Rightarrow \left( {q \Rightarrow p} \right)} \right]$$ is not a tautology.

(b) Let $$A$$ be a tautology and $$B$$ be any other formula. Prove that $$\left( {A \vee B} \right)$$ is a tautology.

The number of binary relations on a set with $$n$$ elements is:

The number of binary strings of $$n$$ zeros and $$k$$ ones such that no two ones are adjacent is:

(a) Mr. X claims the following:
If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof.

"From xRy, using symmetry we get yRx. Now because R is transitive, xRy and yRx togethrer imply xRx. Therefore, R is reflextive."

Briefly point out the flaw in Mr. X' proof.

(b) Give an example of a relation R which is symmetric and transitive but not reflexive.

Two girls have picked 10 roses, 15 sunflowers and 14 daffodils. What is the number of ways they can divide the flowers among themselves?

Let $$G$$ be a connected, undirected graph. A $$cut$$ in $$G$$ is a set of edges whose removal results in $$G$$ being broken into two or more components which are not connected with each other. The size of a cut is called its $$cardinality$$. A $$min-cut$$ of $$G$$ is a cut in $$G$$ of minimum cardinality. Consider the following graph.

(a) Which of the following sets of edges is a cut?
$$\,\,\,\,$$(i)$$\,\,\,\,\left\{ {\left( {A,\,B} \right),\left( {E,\,F} \right),\left( {B,\,D} \right),\left( {A,\,E} \right),\left( {A,\,D} \right)} \right\}$$
$$\,\,\,\,$$(ii)$$\,\,\,\,\left\{ {\left( {B,\,D} \right),\left( {C,\,F} \right),\left( {A,\,B} \right)} \right\}$$

(b) What is the cardinality of a min-cut in this graph?

(c) Prove that if a connected undirected graph $$G$$ with $$n$$ vertices has a min-cut of cardinality $$k$$, then $$G$$ has at least $$(nk/2)$$ edges.

Suppose that the expectation of a random variable X is 5. Which of the following statements is true?

Which of the following disk scheduling strategies is likely to give the best throughput?

Which of the following is/are advantage of virtual memory?

A certain computer system has the segmented paging architecture for virtual memory. The memory is byte addressable. Both virtual and physical address spaces contain $${2^{16}}$$ bytes each. The virtual address space is divided into $$8$$ non-overlapping equal size segments. The memory management unit $$(MMU)$$ has a hardware segment table, each entry of which contains the physical address of the page table for the segment. Page table are stored in the main memory and consists of $$2$$ byte page table entries.

(a)$$\,\,\,\,\,$$ What is the minimum page size in bytes so that the page table for a segment requires at most one page to store it? Assume that the page size can only be a power of $$2.$$

(b)$$\,\,\,\,\,$$ Now suppose that the pages size is $$512$$ bytes. It is proposed to provide a $$TLB$$ (Translation look-aside buffer) for speeding up address translation. The proposed $$TLB$$ will be capable of storing page table entries for $$16$$ recently referenced virtual pages, in a fast cache that will use the direct mapping scheme. What is the number of tag bits that will need to be associated with each cache entry

(c)$$\,\,\,\,\,$$ Assume that each page table entry contains (besides other information) $$1$$ valid bit, $$3$$ bits for page protection and $$1$$ dirty bit. How many bits are available in page table entry for storing the aging information for the page? Assume that the page size is $$512$$ bytes.

Listed below are some operating system abstractions (in the left column) and the hardware components. Which matching pairs is correct?

$$\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$List-$${\rm I}$$
(a) Thread $$\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$(b) Virtual Address space
(c) File System $$\,\,\,\,\,\,\,\,\,\,$$(d) Signal

$$\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$List-$${\rm II}$$
(1) Interrupt $$\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$(2) Memory
(3) $$CPU$$ $$\,\,\,\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$(4) Disk

A multi-user, multi-processing operating system cannot be implemented on hardware that does not support:

System calls are usually invoked by using:

Which of the following actions is/are typically not performed by the operating system when switching context from process $$A$$ to process $$B$$ ?

Consider the following C function definition

int Trial (int a, int b, int c)
{
       if ((a > = b) && (c < b)) return b;
       else if (a > = b) return Trial (a,c,b);
       else return Trial (b,a,c);
}

The function Trial:

Given the programming constructs:

(i) assignment
(ii) for loops where the loop parameter cannot be changed within the loop
(iii) if-then-else
(iv) forward go to
(v) arbitrary go to
(vi) non-recursive procedure call
(vii) recursive procedure/function call
(viii) repeat loop,

which constructs will you not include in a programming language such that it should be possible to program the terminates (i.e., halting) function in the same programming language.

Consider the following program in a language that has dynamic scooping:

var x: real;
procedure show;
         begin print(x); end;
procedure small;
         var x: real;
             begin x: = 0.125; show; end;
begin x:=0.25;
         show; small
         end;

Then the output of the program is:

A certain processor supports only the immediate and the direct addressing modes. Which of the following programming language features cannot be implemented on this processor?

Consider the regular expression $$(0+1)(0+1).......n$$ times. The minimum state finite automation that recognizes the language represented by this regular expression contains:

Context free languages are closed under:

Let $${L_D}$$ be the set of all languages accepted by a $$PDA$$ by final state and $${L_E}$$ the set of all languages accepted by empty stack. Which of the following is true?

If $${L_1}$$ is a context free language and $${L_2}$$ is a regular which of the following is/are false?