GATE Questions & Instant Answers

Track the remainder mod $5$. On reading a bit $b$, the value updates as $r \to (2r + b) \bmod 5$. The five remainders $\{0,1,2,3,4\}$ are all reachable and distinguishable, so exactly $5$ states are needed, with remainder $0$ as the only accepting state.

$\{a^n b^m\}$ needs no counting — it is described by the regular expression $a^* b^*$. The other three require matching/counting an unbounded quantity, which a finite automaton cannot do (provable via the pumping lemma).

The Master Theorem does not apply (the driving term is not a polynomial in $n$). Summing costs over levels: level $i$ contributes $\dfrac{n}{\log n - i}$, so the total is $n\sum_{k=1}^{\log n}\tfrac{1}{k} = n\,H(\log n) = \Theta(n \log \log n)$.

Dijkstra finalizes a vertex's distance greedily when extracted. A later negative edge could reduce that distance, but the vertex is never reconsidered — so a single negative edge can produce a wrong answer. (Bellman–Ford handles negative edges.)

Pair up elements ($n/2$ comparisons), then compare pair-winners for the max and pair-losers for the min: $\lceil 3n/2 \rceil - 2$. For $n=100$: $150 - 2 = 148$.

Minimum nodes follow $N(h) = N(h-1) + N(h-2) + 1$ with $N(0)=1,\ N(1)=2$. So $N(2)=4,\ N(3)=7,\ N(4)=12,\ N(5)=20$.

Blocks $= 16\text{KB}/32 = 512$. Sets $= 512/4 = 128 \Rightarrow 7$ index bits. Offset $= \log_2 32 = 5$ bits. Tag $= 32 - 7 - 5 = 20$ bits.

Effective CPI $= \text{ideal CPI} + (\text{branch fraction}) \times (\text{penalty}) = 1 + 0.2 \times 2 = 1.4$.

SJF order: $3, 6, 7, 8$. Waiting times: $0,\ 3,\ 9,\ 16$. Average $= (0+3+9+16)/4 = 28/4 = 7$.

FIFO is not a stack algorithm — its frame contents at $k$ frames are not guaranteed to be a subset of those at $k+1$ frames, so adding a frame can increase faults. LRU and OPT are stack algorithms and are immune.

The FDs form a cycle, so every single attribute functionally determines all others — each attribute is a candidate key. Therefore every non-empty subset of the $4$ attributes is a superkey: $2^4 - 1 = 15$.

$Conflict-serializability$ is decided by the precedence graph built on conflicting operations (read–write, write–read, write–write on the same item). The schedule is $conflict-serializable$ exactly when this graph has no cycle.

Host bits $= 32 - 26 = 6 \Rightarrow 2^6 = 64$ addresses. Subtract the network and broadcast addresses: $64 - 2 = 62$.

Efficiency $= \dfrac{T_t}{T_t + 2T_p} = \dfrac{1}{1 + 2(20)} = \dfrac{1}{41} \approx 0.024 \approx 0.02$. This is why Stop-and-Wait is inefficient on high-latency links.

By inclusion–exclusion: $3^4 - \binom{3}{1}2^4 + \binom{3}{2}1^4 = 81 - 48 + 3 = 36$.

Reflexivity fixes the $n$ diagonal pairs as present; the remaining $n^2 - n$ ordered pairs are free. Count $= 2^{n^2 - n} = 2^{9-3} = 2^6 = 64$.

Cayley's formula gives $n^{n-2}$ spanning trees for $K_n$. For $n=4$: $4^{4-2} = 4^2 = 16$.

Outcomes with at least one $3$: $11$ (six with first die $3$, six with second, minus the double-counted $(3,3)$). Among these, sum $=8$ occurs for $(3,5)$ and $(5,3)$. So $P = 2/11$.

Pointer arithmetic: p + 3 points to a[3] $= 4$, so *(p+3) is $4$. Then `4 + 2 = 6$.

For an $n \times n$ matrix, $\det(kA) = k^n \det(A)$. Here $\det(2A) = 2^3 \times 2 = 8 \times 2 = 16$.