GATE CSE
1. Choose an i uniformly at random fro 1..n;
2. If A[i]=x then stop else Goto 1;
Assuming that x is present A, what is the expected number of comparisons made by the algorithm before it terminates?
If n<=2 return (1) else return (A([$$\sqrt n $$])); is best described by
T(2k) = 3 T(2k-1) + 1, T (1) = 1, is:

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



(i)$$\,\,\,\,\,\,A \leftrightarrow \left( {A \vee A} \right)$$
(ii)$$\,\,\,\,\,\,\left( {A \vee B} \right) \to B$$
(iii)$$\,\,\,\,\,\,A \vee \left( {\neg \left( {A \vee B} \right)} \right)$$
(a) Give the expression for $${N_r}$$ in terms of $$n$$.
(b) Give the expression for $${N_f}$$ in terms of $$n$$.
(c) Which is larger for all possible $$n, $$ $${N_r}$$ or $${N_f}$$?
Add the minimumnumber of ordered pairs to $$S$$ to make it an $$\,\,\,\,\,$$equivalence relation. Give the modified $$S$$.
(b) Let $$S = \left\{ {a,\,\,b} \right\}\,\,\,\,$$ and let ▢ $$S$$ be the power set of $$S$$. Consider the binary relation $$'\underline \subset $$ (set inclusion)' on ▢ $$S$$. Draw the Hasse diagram corresponding to the lattice (▢$$(S)$$, $$\underline \subset $$)
(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?
(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.
$$(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 a program terminates, another program is immediately scheduled for execution.
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
$$L = \left. {\left\{ x \right.} \right|$$ length of $$x$$ is divisible by $$\left. 3 \right\}$$ has
