# Recent activity by krishn.jh

1
In a computer system where the best-fit' algorithm is used for allocating jobs' to memory partitions', the following situation was encountered:$\begin{array}{|l|l|} \hline \textbf{Partitions size in$KB$} & \textbf{$4K \ 8K \ 20K \ 2K$} \\\hline \textbf{Job sizes in$KB$} & \text{$2K ... $} \\\hline \end{array}$When will the $20K$ job complete?
2
Consider two cache organizations. First one is $32$ $kB$ $2$-way set associative with $32$ $byte$ block size, the second is of same size but direct mapped. The size of an address is $32$ $bits$ in both cases . A $2$-to-$1$ multiplexer has latency of $0.6 ns$ while a $k-$bit comparator has ... while that of direct mapped is $h_2$. The value of $h_2$ is: $2.4$ $ns$ $2.3$ $ns$ $1.8$ $ns$ $1.7$ $ns$
3
Consider two cache organizations. First one is $32 \hspace{0.2cm} KB$ $2-way$ set associative with $32 \hspace{0.2cm} byte$ block size, the second is of same size but direct mapped. The size of an address is $32 \hspace{0.2cm} bits$ in both cases . A $2-to-1$ ... $h_1$ is: $2.4 \text{ ns}$ $2.3 \text{ ns}$ $1.8 \text{ ns}$ $1.7 \text{ ns}$
4
The three way handshake for TCP connection establishment is shown below. Which of the following statements are TRUE? $S1:$ Loss of $SYN + ACK$ from the server will not establish a connection $S2:$ Loss of $ACK$ from the client cannot establish the connection $S3:$ ... machine on no packet loss $S2$ and $S3$ only $S1$ and $S4$ only $S1$ and $S3$ only $S2$ and $S4$ only
5
The following is a code with two threads, producer and consumer, that can run in parallel. Further, $S$ and $Q$ are binary semaphores quipped with the standard $P$ and $V$ operations. semaphore S = 1, Q = 0; integer x; producer: consumer: while (true) ... producer may be lost Values generated and stored in '$x$' by the producer will always be consumed before the producer can generate a new value
6
The following is an incomplete Pascal function to convert a given decimal integer (in the range $-8$ to $+7$) into a binary integer in $2's$ complement representation. Determine the expressions $A, B, C$ that complete program. function TWOSCOMP (N:integer):integer; var REM, ... <>0 do begin REM:=N mod 2; BIANRY:=BINARY + B*EXPONENT; EXPONENT:=EXPONENT*10; N:=C end TWOSCOMP:=BINARY end end;
7
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? $8$ $16$ $32$ $64$ None of the above
8
Consider a $5-$stage pipeline - IF (Instruction Fetch), ID (Instruction Decode and register read), EX (Execute), MEM (memory), and WB (Write Back). All (memory or register) reads take place in the second phase of a clock cycle and all writes occur ... Show all data dependencies between the four instructions. Identify the data hazards. Can all hazards be avoided by forwarding in this case.
9
Consider the following program: int f (int * p, int n) { if (n <= 1) return 0; else return max (f (p+1, n-1), p[0] - p[1]); } int main () { int a[] = {3, 5, 2, 6, 4}; print f(" %d", f(a, 5)); } Note: $max (x, y)$ returns the maximum of $x$ and $y$. The value printed by this program is ________.
10
A computer system has a three-level memory hierarchy, with access time and hit ratios as shown below: $\overset{ \text {Level$1$(Cache memory)} \\ \text{Access time =$ ... access time of less than $100 nsec$? What is the average access time achieved using the chosen sizes of level $1$ and level $2$ memories?
11
Consider the following languages: $L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$ $L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$ Which one of the following is TRUE? Both $L_{1}$ and $L_{2}$ are context-free. $L_{1}$ is context-free while $L_{2}$ is not context-free. $L_{2}$ is context-free while $L_{1}$ is not context-free. Neither $L_{1}$ nor $L_{2}$ is context-free.
12
Consider a simple connected graph $G$ with $n$ vertices and $n$ edges $(n > 2)$. Then, which of the following statements are true? $G$ has no cycles The graph obtained by removing any edge from $G$ is not connected $G$ has at least one cycle The graph obtained by removing any two edges from $G$ is not connected None of the above
13
Assume that a CPU has only two registers $R_1$ and $R_2$ and that only the following instruction is available $XOR \: R_i, R_j;\{R_j \leftarrow R_i \oplus R_j, \text{ for } i, j =1, 2\}$ Using this XOR instruction, find an instruction sequence in order to ... registers $R_1$ and $R_2$ The line p of the circuit shown in figure has stuck at 1 fault. Determine an input test to detect the fault.
14
Let $L$ be a regular language. Consider the constructions on $L$ below: repeat $(L) = \{ww \mid w \in L\}$ prefix $(L) = \{u \mid ∃v : uv \in L\}$ suffix $(L) = \{v \mid ∃u : uv \in L\}$ half $(L) = \{u \mid ∃v : | v | = | u | \text{ and } uv \in L\}$ Which of the constructions could lead to a non-regular language? Both I and IV Only I Only IV Both II and III
15
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Which of the following is the strongest correct statement about a finite language over some finite alphabet $\Sigma$ ? It could be undecidable It is Turing-machine recognizable It is a context sensitive language. It is a regular language. None of the above,
16
Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$ $\epsilon + 0\left(10^*1+00\right)^*0$ $\epsilon + 0\left(10^*1+10\right)^*1$ $\epsilon + 0\left(10^*1+10\right)^*10^*$ $P-2, Q-1, R-3, S-4$ $P-1, Q-3, R-2, S-4$ $P-1, Q-2, R-3, S-4$ $P-3, Q-2, R-1, S-4$
17
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ indicates a final state) $\overset{Y}{\begin{array}{|l|l|l|}\hline \text{} & \textbf{a} & \textbf{b} \\\hline \text{$\rightarrow1$} & \text{1} & \text{2} \\\hline \text{$ ...
18
State True or False with one line explanation A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).
19
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be $\Sigma_{0 \leq i < n} 2^{n-1-i}.a_i$ Let $\Sigma = \{(0, 0),(0, 1),(1, 0),(1, 1)\}$. Construct a finite automaton that accepts the set of all strings $(a_0, b_0)(a_1, b_1) \dots (a_{n−1}, b_{n−1}) \in \: \Sigma^*$ such that $val(b_0b_1 \dots b_{n−1}) = 2 · val(a_0a_1 \dots a_{n−1})$.
20
Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers. If a language $L$ is accepted by an NFA with $n$ states then there is a DFA with no more than $2^n$ states accepting $L$.
21
A simple and reliable data transfer can be accomplished by using the 'handshake protocol'. It accomplishes reliable data transfer because for every data item sent by the transmitter _____.
22
In a vectored interrupt: The branch address is assigned to a fixed location in memory The interrupting source supplies the branch information to the processor through an interrupt vector The branch address is obtained from a register in the processor None of the above
23
A priority encoder accepts three input signals $\text{(A, B and C)}$ and produces a two-bit output $(X_1, X_0 )$ corresponding to the highest priority active input signal. Assume $A$ has the highest priority followed by $B$ and $C$ has the lowest priority. If none of the inputs are active the output should be $00$, design the priority encoder using $4:1$ multiplexers as the main components.
24
Amar and Akbar both tell the truth with probability $\dfrac{3 } {4}$ and lie with probability $\dfrac{1}{4}$. Amar watches a test match and talks to Akbar about the outcome. Akbar, in turn, tells Anthony, "Amar told me that India won". What probability should Anthony assign to India's ... $\left(\dfrac{6 }{16}\right)$ $\left(\dfrac{7}{16}\right)$ $\left(\dfrac{10}{16}\right)$ None of the above
25
A cube whose faces are colored is split into $1000$ small cubes of equal size. The cubes thus obtained are mixed thoroughly. The probability that a cube drawn at random will have exactly two colored faces is: $0.096$ $0.12$ $0.104$ $0.24$ None of the above
26
Design a logic circuit to convert a single digit BCD number to the number modulo six as follows (Do not detect illegal input): Write the truth table for all bits. Label the input bits $I_1, I_2, \ldots$ with $I_1$ as the least significant bit. Label the output bits ... truth. Draw one circuit for each output bit using, altogether, two two-input AND gates, one two-input OR gate and two NOT gates.
For each positive integer $n$ consider the set $S_n$ defined as follows: $S_1 = \{1\},\:S_2 = \{2, 3\},\:S_3 = \{4,5,6\}, \: \dots$ and in general, $S_{n+1}$ consists of $n+1$ consecutive integers the smallest of which is one more than the largest integer in $S_n$. Then the sum of all the integers in $S_{21}$ equals to $1113$ $53361$ $5082$ $4641$
In how many ways can $b$ blue balls and $r$ red balls be distributed in $n$ distinct boxes? $\frac{(n+b-1)!\,(n+r-1)!}{(n-1)!\,b!\,(n-1)!\,r!}$ $\frac{(n+(b+r)-1)!}{(n-1)!\,(n-1)!\,(b+r)!}$ $\frac{n!}{b!\,r!}$ $\frac{(n + (b + r) - 1)!} {n!\,(b + r - 1)}$
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $(i,j)$ then it can move to either $(i + 1, j)$ or $(i,j + 1)$ ... $^{20}\mathrm{C}_{10} - ^{8}\mathrm{C}_{4}\times ^{11}\mathrm{C}_{5}$