# Questions by Arjun

1
A direct mapped cache memory of $1$ MB has a block size of $256$ bytes. The cache has an access time of $3$ ns and a hit rate of $94 \%$. During a cache miss, it takes $2$0 ns to bring the first word of a block from the main memory, while each subsequent word takes $5$ ns. The word size is $64$ bits. The average memory access time in ns (round off to $1$ decimal place) is______.
2
Consider the following C program. #include <stdio.h> int main () { int a[4] [5] = {{1, 2, 3, 4, 5}, {6, 7,8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17,18, 19, 20}}; printf(“%d\n”, *(*(a+**a+2)+3)); return(0); } The output of the program is _______.
3
Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Assume that the table size is $23$. Then the address returned by probe $1$ in the probe sequence (assume that the probe sequence begins at probe $0$) for key value $k=90$ is_____________.
4
Consider the following grammar. $S \rightarrow aSB \mid d$ $B \rightarrow b$ The number of reduction steps taken by a bottom-up parser while accepting the string $aaadbbb$ is___________.
5
Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send HTTP requests in non-persistent mode. The web page contains text and five very small images.The minimum number of TCP connections required to display the web page completely in your browser is__________.
6
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only
7
Let $A$ and $B$ be two $n \times n$ matrices over real numbers. Let rank($M$) and $\text{det}(M)$ denote the rank and determinant of a matrix $M$, respectively. Consider the following statements. $\text{rank}(AB) = \text{rank }(A) \text{rank }(B)$ ... Which of the above statements are TRUE? I and II only I and IV only II and III only III and IV only
8
Consider the Boolean function $z(a,b,c)$. Which one of the following minterm lists represents the circuit given above? $z=\sum (0,1,3,7)$ $z=\sum (1,4,5,6,7)$ $z=\sum (2,4,5,6,7)$ $z=\sum (2,3,5)$
9
Consider three registers $R1$, $R2$, and $R3$ that store numbers in $IEEE-754$ single precision floating point format. Assume that $R1$ and $R2$ contain the values (in hexadecimal notation) $0x42200000$ and $0xC1200000$, respectively. If $R3=\frac{R1}{R2}$, what is the value stored in $R3$? $0x40800000$ $0xC0800000$ $0x83400000$ $0xC8500000$
10
A computer system with a word length of $32$ bits has a $16$ MB byte- addressable main memory and a $64$ KB, $4$-way set associative cache memory with a block size of $256$ bytes. Consider the following four physical addresses represented in hexadecimal notation. $A1= 0x42C8A4$ ... same cache set. $A3$ and $A4$ are mapped to the same cache set. $A1$ and $A3$ are mapped to the same cache set.
11
Let $G = (V, G)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST of the resultant graph ... $\Theta (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$
12
Consider the following languages. $\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$ Which one of the following is TRUE? $L_1$ ... $L_1$ context- free but not regular and $L_2$ is context-free. Neither $L_1$ nor $L_2$ is context- free. $L_1$ context- free but $L_2$ is not context-free.
13
Consider the productions $A \rightarrow PQ$ and $A \rightarrow XY$. Each of the five non-terminals $A, P, Q, X$, and $Y$ has two attributes: $s$ is a synthesized attribute, and $i$ is an inherited attribute. Consider the following rules. Rule $1$ ... $1$ is $L$-attributed. Only Rule $2$ is $L$-attributed. Neither Rule $1$ nor Rule $2$ is $L$-attributed.
14
Each of a set of $n$ processes executes the following code using two semaphores $a$ and $b$ initialized to $1$ and $0$, respectively. Assume that $\text{count}$ is a shared variable initialized to $0$ ... ensures that all processes execute CODE SECTION P mutually exclusively. It ensures that at most $n-1$ processes are in CODE SECTION P at any time.
15
Consider the following five disk five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time. $(P, 155), (Q,85), (R,110),(S, 30), (T,115)$ Assume the head is positioned at cylinder $100$. The ... $S$,but before $T$. The head reverses its direction of movement between servicing of $Q$ and $P$. $R$ is serviced before $P$.
16
Consider a relational table $R$ that is in $3NF$, but not in BCNF. Which one of the following statements is TRUE? $R$ has a nontrivial functional dependency $X \rightarrow A$, where $X$ is not a superkey and $A$ is a prime attribute. $R$ has a nontrivial functional dependency ... $X$ is a proper subset of some key A cell in $R$ holds a set instead of an atomic value.
17
Consider a schedule of transactions $T_1$ and $T_2$: $\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 & RA & & & RC & & WD & & WB & \text{Commit} & \\ \hline T_2 & & RB & WB & & RD & & WC & & & \text{Commit} \\ \hline \end{array}$ Here, RX stands for Read(X) and WX ...
18
An organization requires a range of IP address to assign one to each of its $1500$ computers. The organization has approached an Internet Service Provider (ISP) for this task. The ISP uses CIDR and serves the requests from the available IP address space $202.61.0.0/17$. The ISP wants to assign an ... $202.61.64.0/21$ $202.61.144.0/21$ I and II only II and III only III and IV only I and IV only
19
Which one of the following predicate formulae is NOT logically valid? Note that $W$ is a predicate formula without any free occurrence of $x$. $\forall x (p(x) \vee W) \equiv \forall x \: ( px) \vee W$ $\exists x(p(x) \wedge W) \equiv \exists x \: p(x) \wedge W$ ... $\exists x(p(x) \rightarrow W) \equiv \forall x \: p(x) \rightarrow W$
Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$. Which one of the options completes the ... distance from $s$ to $u$ in the graph obtained by adding a new vertex $s$ to $G$ and edges of zero weight from $s$ to every vertex of $G$