Q·Magazine

Characteristic equation: $\lambda^2 - 7\lambda + 10 = 0 \Rightarrow (\lambda-2)(\lambda-5)=0$. Eigenvalues are 2 and 5.

The determinant equals the product of the eigenvalues: $1\times2\times3 = 6$.

$\int_0^1 x^2\,dx = \left[\tfrac{x^3}{3}\right]_0^1 = \tfrac13$.

$\lim_{x\to0}\tfrac{\sin 5x}{x} = 5\lim_{x\to0}\tfrac{\sin 5x}{5x} = 5\times1 = 5$.

$P(A\cup B) = P(A)+P(B)-P(A\cap B) = 0.5+0.4-0.2 = 0.7$.

$E[X] = \tfrac{1+2+3+4+5+6}{6} = \tfrac{21}{6} = 3.5$.

A set of $n$ elements has $2^n$ subsets: $2^5 = 32$.

By inclusion–exclusion: $3^4 - \binom31 2^4 + \binom32 1^4 = 81 - 48 + 3 = 36$.

$K_n$ has $\binom{n}{2}$ edges: $\binom52 = 10$.

$\binom{8}{3} = \dfrac{8\times7\times6}{3!} = 56$.

$1\cdot8 + 0\cdot4 + 1\cdot2 + 1\cdot1 = 11$.

$+6 = 0110$; invert to $1001$, add 1 → $1010$.

By the absorption/redundancy law, $A + A'B = A + B$.

A $2^n : 1$ MUX needs $n$ select lines; $8 = 2^3$, so 3.

XOR outputs 1 only when inputs differ; $1\oplus1 = 0$.

Full-adder SUM $= A \oplus B \oplus C_{in}$; carry $= AB + C_{in}(A\oplus B)$.

A mod-$N$ counter needs $\lceil \log_2 N \rceil$ flip-flops; $\log_2 16 = 4$.

For $n$-bit 2’s complement the range is $-2^{n-1}$ to $2^{n-1}-1$: $-128$ to $+127$.

Group in nibbles: $1101 = D$, $1010 = A$ → $DA$.

Tie both inputs of a NAND together: $\overline{A\cdot A} = \overline{A}$.

Blocks $= 8\text{KB}/16 = 512 \Rightarrow 9$ index bits; offset $= \log_2 16 = 4$; tag $= 32 - 9 - 4 = 19$.

AMAT $= 10 + (1-0.9)\times100 = 10 + 10 = 20$ ns (hit time + miss rate × miss penalty).

Effective CPI $= 1 + 0.2\times2 = 1.4$.

$1\text{K} = 2^{10}$ locations, so 10 address lines.

With enough instructions and no stalls, a $k$-stage pipeline approaches a speedup of $k$.

$2^{20}$ words need 20 address bits.

Booth’s encoding replaces a run of 1s with one subtract and one add, so long runs of 1s minimize operations.

Write-back defers memory writes until the dirty block is replaced (evicted), reducing memory traffic.

Immediate addressing embeds the operand value directly in the instruction.

DMA transfers data between I/O and memory without the CPU handling each word, freeing the CPU.

p+3 points to a[3]=4, so *(p+3)=4; then 4+2=6.

A full binary tree of height $h$ has $2^{h+1}-1$ nodes.

$N(h)=N(h-1)+N(h-2)+1$, $N(0)=1,N(1)=2 \Rightarrow N(5)=20$.

This is the Catalan number $C_3 = \dfrac{1}{4}\binom{6}{3} = 5$.

The call stack stores activation records in LIFO order for function calls/returns.

In-order traversal of a BST yields keys in ascending sorted order.

A circular queue wraps around to reuse freed slots at the front, preventing false "queue full" states.

Linear probing checks the next consecutive slots until an empty one is found.

Advance one pointer $k$ nodes, then move both together; when the lead hits the end, the trailing pointer is at the $k$-th from end.

In a 1-indexed binary heap, parent$(i) = \lfloor i/2 \rfloor$, children are $2i$ and $2i+1$.

By the Master Theorem (case 2), $a=b^{\,d}$ with $d=1$ gives $\Theta(n\log n)$ — this is merge sort.

The Master Theorem fails; summing levels gives $n\sum 1/k = \Theta(n\log\log n)$.

A poor pivot (e.g. sorted input, last-element pivot) gives $O(n^2)$; average is $O(n\log n)$.

$\lceil \log_2 1000 \rceil = 10$.

$\lceil 3n/2 \rceil - 2 = 150 - 2 = 148$ (pair up, then compare winners and losers).

Kruskal’s algorithm greedily adds the lightest edge that doesn’t form a cycle, using union–find.

Dijkstra finalizes vertices greedily; a later negative edge can invalidate a finalized distance. Use Bellman–Ford for negatives.

$W$ is a numeric value (not input size), so $O(nW)$ is pseudo-polynomial — exponential in the bits of $W$.

BFS explores by levels, giving the minimum number of edges from the source.

NP-complete = in NP and NP-hard (every NP problem reduces to it). A poly-time solution would imply P = NP.

Track remainder mod 5; on bit $b$, $r \to (2r+b)\bmod 5$. Five distinguishable remainders → 5 states.

$a^*b^*$ needs no counting; the others require matching unbounded counts, which FAs cannot do.

States track progress: start → seen "a" → seen "ab" (accepting); 3 states suffice.

Subset construction can produce up to $2^n$ DFA states (one per subset of NFA states).

It gives a necessary property of regular languages; a violation proves a language is not regular.

A PDA can match $a$s and $b$s using its stack, but no DFA can — so it is CFL but not regular.

Regular languages are closed under union, intersection, complement, concatenation and Kleene star.

The Halting Problem is undecidable, but it is Turing-recognizable (semi-decidable) — a TM can accept when $M$ halts.

Non-deterministic pushdown automata recognize exactly the context-free languages.

$(aa)^*$ matches $\varepsilon, aa, aaaa, \dots$ — strings of $a$ with even length.

A compiler proceeds lexical analysis → syntax analysis (parsing) → semantic analysis.

The lexer groups characters into tokens (identifiers, keywords, operators, literals).

LL(1) is top-down predictive parsing using 1 lookahead token and FIRST/FOLLOW sets.

Canonical LR(1) handles the largest class of grammars; LALR(1) is a compact, slightly weaker variant.

Left recursion causes infinite recursion in top-down parsers, so it must be eliminated for LL parsing.

FIRST/FOLLOW sets drive entries of the LL(1) predictive parsing table.

Three-address code (e.g. t1 = a + b) is a common intermediate representation between the front and back ends.

The symbol table records identifiers with attributes such as type, scope and memory location.

SDT associates semantic rules/actions (using synthesized/inherited attributes) with productions.

The interference graph is colored with $k$ colors ($k$ = registers); adjacent live variables get different registers.

Order 3,6,7,8; waiting times 0,3,9,16; average $=28/4 = 7$.

FIFO is not a stack algorithm, so adding frames can increase faults. LRU and OPT are immune.

The four conditions are mutual exclusion, hold-and-wait, NO preemption, and circular wait. "Preemption" (allowing it) actually prevents deadlock.

Available permits over time: init 3 + 3 signals = 6 grants possible; 5 P succeed immediately/eventually, but net demand 5 vs supply 3+? Value $= 3 - 5 + 3 = 1$ ⇒ one more P than available, so 1 process is blocked.

SJF/priority scheduling can starve long (low-priority) jobs if short jobs keep arriving.

$4\text{KB} = 2^{12}$ bytes per page, so 12 offset bits (the remaining 20 bits are the page number).

Semaphores "empty" and "full" track buffer slots/items, and a mutex protects the shared buffer.

The Banker’s algorithm grants a request only if the resulting state is "safe" — it avoids deadlock.

Thrashing is high paging activity with low CPU utilization, caused by too little memory per active process.

If the quantum exceeds every burst, each process runs to completion in arrival order — i.e. FCFS.

The FD cycle makes every single attribute a candidate key, so every non-empty subset is a superkey: $2^4-1 = 15$.

BCNF requires the left side of every non-trivial FD to be a superkey.

Conflict-serializability holds exactly when the precedence (serialization) graph has no cycle.

ACID = Atomicity, Consistency, Isolation, Durability; committed changes survive failures.

WHERE filters rows before grouping; HAVING filters after aggregation on grouped results.

Natural join equates tuples that match on all commonly-named attributes and drops the duplicate columns.

In a B+ tree, internal nodes hold only keys for routing; all record pointers/data live in the linked leaves.

2PL (a growing phase then a shrinking phase) guarantees conflict-serializable schedules, though deadlocks can still occur.

$A\to B$ and $B\to C$ give $A\to C$ by transitivity, so $A^+ = \{A,B,C\}$ — $A$ is a key.

2NF violation = a non-prime attribute depends on part of a composite candidate key (partial dependency).

Host bits $= 32-26 = 6 \Rightarrow 2^6 = 64$; minus network and broadcast → 62.

$/26$ sets 26 leading 1-bits: 255.255.255.11000000 = 255.255.255.192.

$2^{26-24} = 2^2 = 4$ subnets.

Physical, Data Link, Network, Transport, Session, Presentation, Application — 7 layers.

UDP is connectionless, unreliable and lightweight — no handshake, ordering, or flow control, so lower overhead.

Efficiency $= \dfrac{T_t}{T_t + 2T_p} = \dfrac{1}{1+40} = \dfrac{1}{41} \approx 0.02$.

Ethernet used CSMA/CD — carrier sense, and collision detection with back-off — on a shared medium.

A minimum Hamming distance of $d+1$ detects up to $d$ bit errors; $2d+1$ is needed to correct $d$ errors.

HTTP uses TCP port 80; HTTPS uses TCP port 443.

ARP (Address Resolution Protocol) maps a known IPv4 address to its link-layer MAC address.