Log In

Recent activity by Nikhil_dhama

3 answers
For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers: $T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$ Which one of the following options is correct about the recurrence $T(n)$? If $f(n)$ is $n \log_2(n)$, then $T(n)$ ... $\Theta(n^{\log_b(a)})$ If $f(n)$ is $\Theta(n^{\log_b(a)})$, then $T(n)$ is $\Theta(n^{\log_b(a)})$
commented 1 day ago in Algorithms 625 views
3 answers
Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive? $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is ... $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$
commented 5 days ago in Theory of Computation 521 views
2 answers
A circular sheet of paper is folded along the lines in the direction shown. The paper, after being punched in the final folded state as shown and unfolded in the reverse order of folding, will look like _______.
answered 6 days ago in Spatial Aptitude 329 views
5 answers
Consider the following recurrence relation. $T\left ( n \right )=\left\{\begin{array} {lcl} T(n/2)+T(2n/5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$ Which one of the following options is correct? $T(n)=\Theta (n^{5/2})$ $T(n)=\Theta (n\log n)$ $T(n)=\Theta (n)$ $T(n)=\Theta ((\log n)^{5/2})$
commented 6 days ago in Algorithms 1.2k views
1 answer
Consider the following greedy algorithm for colouring an $n$-vertex undirected graph $G$ with colours $c_{1}, c_{2}, \dots:$ consider the vertices of $G$ in any sequence and assign the chosen vertex the first colour that has not already been assigned to any of its neighbours. Let $m(n, r)$ be the minimum ... $m\left ( n, r \right ) = nr$ $m\left ( n, r \right ) = n\binom{r}{2}$
answered Apr 4 in Others 25 views
1 answer
Let $A$ be a $3 \times 6$ matrix with real-valued entries. Matrix $A$ has rank $3$. We construct a graph with $6$ vertices where each vertex represents distinct column in $A$, and there is an edge between two vertices if the two columns represented by the vertices are ... The graph is connected. There is a clique of size $3$. The graph has a cycle of length $4$. The graph is $3$-colourable.
answered Apr 4 in Others 29 views
1 answer
Let $G$ be an undirected graph. For any two vertices $u, v$ in $G$, let $\textrm{cut} (u, v)$ be the minimum number of edges that should be deleted from $G$ so that there is no path between $u$ and $v$ in the resulting graph. Let $a, b, c, d$ be $4$ vertices in $G$. Which of the following ... $\textrm{cut} (c,d) = 2$ $\textrm{cut} (b,d) = 2$, $\textrm{cut} (b,c) = 2$ and $\textrm{cut} (c,d) = 1$
answered Apr 4 in Others 28 views
1 answer
Let $G$ be a connected bipartite simple graph (i.e., no parallel edges) with distinct edge weights. Which of the following statements on $\text{MST}$ (minimum spanning tree) need $\text{NOT}$ be true? $G$ hasa unique $\text{MST}$. Every $\text{MST}$ in $G$ ... second lightest edge. Every $\text{MST}$ in $G$ contains the third lightest edge. No $\text{MST}$ in $G$ contains the heaviest edge.
answered Apr 4 in Others 21 views
1 answer
Consider the following statements about propositional formulas. $\left ( p\wedge q \right )\rightarrow r$ and $\left ( p \rightarrow r \right )\wedge \left ( q\rightarrow r \right )$ are $\textit{not }$ ... Depending on the values $p$ and $q$, $\text{(i)}$ can be either true or false, while $\text{(ii)}$ is always false.
answered Apr 4 in Others 26 views
1 answer
Five married couples attended a party. In the party, each person shook hands with those they did not know. Everyone knows his or her spouse. At the end of the party, Shyamal, one of the attendees, listed the number of hands that other attendees including his spouse shook. He ... $8$ once in the list. How many persons shook hands with Shyamal at the party? $2$ $4$ $6$ $8$ Insufficient information
answer edited Apr 4 in Others 36 views
2 answers
Fix $n\geq 6$. Consider the set $\mathcal{C}$ of binary strings $x_{1}, x_{2} \dots x_{n}$ of length $n$ such that the bits satisfy the following set of equalities, all modulo $2$: $x_{i}+x_{i+1}+x_{i+2}=0$ for all $1\leq i\leq n-2, x_{n-1}+x_{n}+x_{1}=0,$ ... $3$ $\left | \mathcal{C} \right |=4$. If $n\geq 6$ is not divisible by $3$ then $\left | \mathcal{C} \right |=1$.
answered Apr 4 in Others 36 views
1 answer
A matching in a graph is a set of edges such that no two edges in the set share a common vertex. Let $G$ be a graph on $n$ $\textit{vertices}$ in which there is a subset $M$ of $m$ $\textit{edges}$ which is a matching. Consider a random process where each vertex in the graph is independently selected ... $p^{2m}$ $\left ( 1-p^{2} \right )^{m}$ $1-\left ( 1-p\left ( 1-p \right ) \right )^{m}$
answered Apr 4 in Others 30 views
2 answers
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$? $\Theta ( \sqrt{n})$ $\Theta (\log _2(n))$ $\Theta(n^2)$ $\Theta(n)$
commented Apr 4 in Algorithms 626 views
2 answers
For a statement $S$ in a program, in the context of liveness analysis, the following sets are defined: $\text{USE(S)}$ : the set of variables used in $S$ $\text{IN(S)}$ : the set of variables that are live at the entry of $S$ $\text{OUT(S)}$ : the set of variables that are live at the exit ... $) }\cup \text{ OUT ($S_2$)}$ $\text{OUT ($S_1$)}$ = $\text{USE ($S_1$)} \cup \text{IN ($S_2$)}$
answered Apr 3 in Linear Algebra 308 views
3 answers
In an examination, a student can choose the order in which two questions ($\textsf{QuesA}$ and $\textsf{QuesB}$) must be attempted. If the first question is answered wrong, the student gets zero marks. If the first question is answered correctly and the second question ... and then $\textsf{QuesA}$. Expected marks $22$. First $\textsf{QuesA}$ and then $\textsf{QuesB}$. Expected marks $16$.
answered Apr 3 in Probability 598 views
2 answers
Suppose that $f: \mathbb{R} \rightarrow \mathbb{R}$ is a continuous function on the interval $[-3, 3]$ and a differentiable function in the interval $(-3,3)$ such that for every $x$ in the interval, $f’(x) \leq 2$. If $f(-3)=7$, then $f(3)$ is at most __________
answered Apr 3 in Calculus 361 views
3 answers
Suppose that $P$ is a $4 \times 5$ matrix such that every solution of the equation $\text{Px=0}$ is a scalar multiple of $\begin{bmatrix} 2 & 5 & 4 &3 & 1 \end{bmatrix}^T$. The rank of $P$ is __________
answered Apr 3 in Linear Algebra 567 views
3 answers
Consider a set-associative cache of size $\text{2KB (1KB} =2^{10}$ bytes$\text{)}$ with cache block size of $64$ bytes. Assume that the cache is byte-addressable and a $32$ -bit address is used for accessing the cache. If the width of the tag field is $22$ bits, the associativity of the cache is _________
answered Apr 3 in CO and Architecture 592 views
3 answers
Consider the three-way handshake mechanism followed during $\text{TCP}$ connection establishment between hosts $P$ and $Q$. Let $X$ and $Y$ be two random $32$-bit starting sequence numbers chosen by $P$ and $Q$ respectively. Suppose $P$ sends a $\text{TCP}$ connection request message to $Q$ with a ... $\text{SEQ}$ number $=Y$, $\text{ACK}$ bit $=1$, $\text{ACK}$ number $=X$, $\text{FIN}$ bit $=0$
answered Apr 3 in Computer Networks 500 views
4 answers
Which one of the following circuits implements the Boolean function given below? $f(x,y,z) = m_0+m_1+m_3+m_4+m_5+m_6$, where $m_i$ is the $i^{\text{th}}$ minterm.
answered Apr 3 in Digital Logic 530 views
2 answers
The number of units of a product sold in three different years and the respective net profits are presented in the figure above. The cost/unit in Year $3$ was Re. $1$, which was half the cost/unit in Year $2$. The cost/unit in Year $3$ was one-third of the cost/unit in Year $1$. ... The ratio of the selling price in Year $2$ to the selling price in Year $3$ is _________. $4:3$ $1:1$ $3:4$ $1:2$
answered Apr 3 in Quantitative Aptitude 437 views
2 answers
The number of students in three classes is in the ratio $3:13:6$. If $18$ students are added to each class, the ratio changes to $15:35:21$. The total number of students in all the three classes in the beginning was: $22$ $66$ $88$ $110$
commented Apr 3 in Quantitative Aptitude 654 views
5 answers
Three processes arrive at time zero with $\text{CPU}$ bursts of $16,\;20$ and $10$ milliseconds. If the scheduler has prior knowledge about the length of the $\text{CPU}$ bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is _____________ milliseconds.
answered Apr 1 in Operating System 359 views
1 answer
Assume that a $12$-bit Hamming codeword consisting of $8$-bit data and $4$ check bits is $d_8d_7d_6d_5c_8d_4d_4d_3d_2c_4d_1c_2c_1$ ... $0$ $x$ is $0$ and $y$ is $1$ $x$ is $1$ and $y$ is $0$ $x$ is $1$ and $y$ is $1$
commented Mar 3 in Computer Networks 1.7k views
9 answers
Given below are two statements $1$ and $2$, and two conclusions $\text{I}$ and $\text{II}$ $\text{Statement 1:}$ All bacteria are microorganisms. $\text{Statement 2:}$ All pathogens are microorganisms. $\text{Conclusion I:}$ ... is correct Either conclusion $\text{I}$ or $\text{II}$ is correct Neither conclusion $\text{I}$ nor $\text{II}$ is correct
commented Feb 21 in Analytical Aptitude 5.3k views
4 answers
A bag has $r$ red balls and $b$ black balls. All balls are identical except for their colours. In a trial, a ball is randomly drawn from the bag, its colour is noted and the ball is placed back into the bag along with another ball of the same colour. Note that the number of balls in the bag will ...
commented Feb 21 in Probability 1k views
4 answers
A relation $R$ is said to be circular if $aRb$ and $bRc$ together imply $cRa$. Which of the following options is/are correct? If a relation $S$ is reflexive and symmetric, then $S$ is an equivalence relation. If a relation $S$ is circular and symmetric, ... and circular, then $S$ is an equivalence relation. If a relation $S$ is transitive and circular, then $S$ is an equivalence relation.
answered Feb 21 in Set Theory & Algebra 501 views
2 answers
In the context of operating systems, which of the following statements is/are correct with respect to paging? Paging helps solve the issue of external fragmentation Page size has no impact on internal fragmentation Paging incurs memory overheads Multi-level paging is necessary to support pages of different sizes
commented Feb 19 in Operating System 549 views
3 answers
Consider a computer system with a byte-addressable primary memory of size $2^{32}$ bytes. Assume the computer system has a direct-mapped cache of size $\text{32 KB}$ ($\text{1 KB}$ = $2^{10}$ bytes), and each cache block is of size $64$ bytes. The size of the tag field is __________ bits.
answered Feb 18 in CO and Architecture 293 views
9 answers
A complete $n$-ary tree is one in which every node has $0$ or $n$ sons. If $x$ is the number of internal nodes of a complete $n$-ary tree, the number of leaves in it is given by $x(n-1) +1$ $xn-1$ $xn +1$ $x(n+1)$
answered Feb 5 in DS 7k views