Q·Magazine

Although each of the $O(n)$ heapify calls costs up to $O(\log n)$, most nodes are near the bottom where heapify does almost no work. Summing the cost over all levels gives $\sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot h = O(n)$ — a tighter bound than the naive per-call estimate.

In a min-heap every node is ≤ its children, so if the second-smallest value sat deeper than the root's children, its parent on the way up would itself have to be smaller — making the parent the second-smallest instead, a contradiction. So the second-smallest must be a direct child of the root, and a binary heap's root always has exactly 2 children (for $n \ge 3$).

Quick Sort's partitioning swaps elements based on pivot position without regard to the relative order of equal keys, so equal elements can be reordered — it is not stable by default.

Each of the $V$ extract-min operations costs $O(\log V)$, and each of the $E$ edge relaxations may trigger a decrease-key costing $O(\log V)$, giving $O((V+E)\log V)$ overall with a binary heap.

Here $a=3, b=2, f(n)=n$. Since $n^{\log_b a} = n^{\log_2 3} \approx n^{1.58}$ grows strictly faster than $f(n)=n$, this is Master Theorem Case 1, giving $\Theta(n^{\log_2 3})$.

A spanning tree on $n$ vertices always has exactly $n - 1$ edges (enough to connect every vertex with no cycles). Here $12 - 1 = 11$.

The hash map gives O(1) lookup of a node by key; the doubly linked list lets you move that node to the front (most-recently-used) and evict the tail (least-recently-used) in O(1), since both operations only touch a constant number of pointers.

Load factor $\alpha = n/m$, where $n$ is the number of keys and $m$ is the table size. So $m = n/\alpha = 50/0.5 = 100$.

Inorder traversal (left → node → right) visits a BST's nodes in ascending order precisely because of the BST invariant: everything in the left subtree is smaller, everything in the right subtree is larger.

A complete binary tree of height $h$ holds between $2^h$ and $2^{h+1}-1$ nodes. For $h=6$: range is $[64, 127]$, and $100$ falls inside it, so the height is 6.

Number of ways to get exactly 2 heads out of 3 tosses = $\binom{3}{2} = 3$. Total outcomes = $2^3 = 8$. Probability = $3/8$.

For continuous distributions, probability is defined by area under the density curve over an interval. A single point has zero width, hence zero area, so $P(X=x)=0$ for any specific $x$.

For a Binomial distribution, $E[X] = np = 10 \times 0.3 = 3$.

For a Binomial distribution, $\text{Var}(X) = np(1-p) = 10 \times 0.3 \times 0.7 = 2.1$.

By Bayes' theorem: $P(D|+) = \dfrac{P(+|D)P(D)}{P(+|D)P(D) + P(+|\lnot D)P(\lnot D)} = \dfrac{0.99 \times 0.01}{0.99\times 0.01 + 0.05\times 0.99} = \dfrac{0.0099}{0.0594} \approx 0.167$, or about 17%. Low base-rate diseases stay unlikely even after a positive test.

Six of the 36 equally likely outcomes sum to 7: (1,6),(2,5),(3,4),(4,3),(5,2),(6,1). Probability = $6/36 = 1/6$.

The Poisson distribution is the standard model for counting rare, independent events over a fixed interval of time or space at a known average rate $\lambda$.

Correlation is invariant to linear transformations of either variable, except that scaling by a negative constant flips the sign: $\text{corr}(aX+b, Y) = \text{sign}(a)\cdot\text{corr}(X,Y)$. Here $a=-2$, so the sign flips: $-(-0.8) = 0.8$.

Maximizing the Normal log-likelihood with respect to $\mu$ gives $\hat\mu_{MLE} = \bar{x}$, the sample mean — the same as the method-of-moments estimator here.

Since $p = 0.03 < \alpha = 0.05$, the result is statistically significant at this level, so we reject the null hypothesis $H_0$.

For a diagonal matrix, the eigenvalues are simply the diagonal entries themselves, since $Av = \lambda v$ holds trivially for each standard basis vector.

Row 2 is exactly $2\times$ Row 1 — the rows are linearly dependent. Only one independent row remains, so $\text{rank}(A) = 1$.

Orthogonal matrices are defined by the property $A^T A = A A^T = I$ — their columns (and rows) form an orthonormal basis.

For a $2\times2$ matrix, $\det(A) = ad - bc = (4)(3) - (2)(1) = 12 - 2 = 10$.

$U$'s columns are the eigenvectors of $AA^T$ (the "left singular vectors"), while $V$'s columns are the eigenvectors of $A^TA$ (the "right singular vectors").

The trace equals the sum of the eigenvalues: $\text{tr}(A) = 5+2 = 7$. If one eigenvalue is 6, the other is $7 - 6 = 1$. (Check: $\det(A)=5\cdot2-4\cdot1=6=6\times1$ ✓.)

Orthogonality (a 90° angle between vectors) is exactly the condition that their dot product vanishes: $u \cdot v = |u||v|\cos\theta = 0$ when $\theta = 90°$.

By the Rank-Nullity Theorem, for an $m \times n$ matrix, $\text{rank} + \text{nullity} = n$ (number of columns). Here $n=6$, rank$=3$, so nullity $= 6-3 = 3$.

Diagonalizability requires a full set of $n$ linearly independent eigenvectors so they can form the columns of an invertible matrix $P$ with $A = PDP^{-1}$. (Symmetric real matrices always satisfy this, but that is a sufficient, not necessary, condition in general.)

The trace is the sum of the diagonal entries. For $I_3$, all three diagonal entries are 1, so the trace is 3.

$f'(x) = 6x + 5$. At $x=2$: $f'(2) = 12 + 5 = 17$.

A function is convex on an interval exactly when its second derivative is non-negative throughout — the slope never decreases, so the curve bends upward or stays flat.

The gradient descent update rule is $\Delta x = -\eta \cdot \nabla f = -0.1 \times 4 = -0.4$ — a step in the direction opposite the gradient.

The Hessian is the square matrix of all second-order partial derivatives, $H_{ij} = \dfrac{\partial^2 f}{\partial x_i \partial x_j}$, and its definiteness tells you whether a critical point is a min, max, or saddle.

Set $f'(x) = 2x - 4 = 0 \Rightarrow x = 2$. Since $f''(x)=2>0$, this critical point is indeed a minimum.

The method of Lagrange multipliers finds the extrema of $f(x)$ subject to one or more equality constraints $g(x) = 0$ by solving $\nabla f = \lambda \nabla g$.

By the chain rule, $\dfrac{d}{dx}\sin(x^2) = \cos(x^2)\cdot 2x$. At $x=0$: $\cos(0)\times 0 = 1 \times 0 = 0$.

SGD approximates the true gradient using one example (or a small mini-batch) per step, trading some noise in each update for dramatically faster, more scalable iterations.

$\dfrac{\partial f}{\partial y} = x^2 + 6y$. At $(1,2)$: $1 + 12 = 13$.

At a saddle point $\nabla f = 0$ (it is a critical point), but the function curves upward in some directions and downward in others — the Hessian is indefinite, so it is neither a max nor a min.

More complex models fit the training data more closely (lower bias) but become more sensitive to the specific training sample (higher variance) — the classic bias-variance tradeoff.

L1's penalty $|w|$ has a non-differentiable kink at zero that pushes many coefficients to exactly zero, performing implicit feature selection — unlike L2, whose smooth penalty shrinks weights but rarely zeroes them out.

With $k=5$ folds on 1,000 samples, each fold gets $1000/5 = 200$ samples for validation while the rest train the model.

A kernel function $K(x,y) = \phi(x)\cdot\phi(y)$ computes the inner product as if the data had been mapped to a (possibly infinite-dimensional) space $\phi$, without ever computing $\phi(x)$ directly — making nonlinear boundaries tractable.

With $k=1$, each training point's nearest neighbor is itself (distance 0), so it always predicts its own true label — giving 100% training accuracy, though this says nothing about generalization.

Boosting (e.g., AdaBoost, Gradient Boosting) trains weak learners sequentially, reweighting or refitting on the residual errors of prior learners — unlike bagging/Random Forest, which train independent trees in parallel.

With equal-size children, the weighted average is simply the mean: $(0.3 + 0.4)/2 = 0.35$ — a decrease from the parent's 0.5, indicating a useful split.

PCA finds orthogonal directions ordered by how much variance of the (unlabeled) data they capture — the first principal component is the direction of maximum variance.

Precision $= \dfrac{TP}{TP+FP} = \dfrac{40}{40+10} = \dfrac{40}{50} = 0.8$.

Cross-validation estimates out-of-sample performance across complexity/regularization settings, letting you pick the sweet spot where bias and variance together minimize validation error.

Backpropagation is a systematic application of the multivariable chain rule, computing $\partial L/\partial w$ layer by layer from the output back to the input, reusing intermediate gradients.

Sigmoid and tanh saturate for large-magnitude inputs, driving their derivatives toward 0. Multiplying many such small derivatives during backprop through deep networks shrinks the gradient toward zero at earlier layers.

$f(-3) = \max(0,-3) = 0$ and $f(5) = \max(0,5) = 5$. Sum $= 0 + 5 = 5$.

Dropout randomly zeroes a fraction of a layer's activations on each forward pass during training, forcing the network to avoid over-relying on any single neuron and reducing overfitting.

Pooling downsamples feature maps (reducing computation and overfitting) while making the representation more robust to small shifts in where a feature appears.

Output size $= \dfrac{W - K}{S} + 1 = \dfrac{7-3}{1} + 1 = 5$, so the output is $5\times5$.

LSTM's gating mechanism lets gradients flow through the cell state largely unimpeded across many time steps, avoiding the repeated multiplicative shrinkage that plagues vanilla RNNs.

Self-attention projects each token into Query, Key and Value vectors; attention weights come from scaled dot products of Queries and Keys (softmax-normalized), then weight the Values — letting every token attend directly to every other token.

A dense layer connects every input neuron to every output neuron: $100 \times 50 = 5{,}000$ weights.

Batch norm re-centers and re-scales each layer's inputs using batch statistics, reducing internal covariate shift and allowing higher learning rates and faster, more stable convergence.

A* combines $g(n)$, the actual cost from the start to $n$, with $h(n)$, the heuristic estimate of remaining cost to the goal, expanding the node with the lowest total estimated cost $f(n) = g(n) + h(n)$.

An admissible heuristic never overestimates the true cost-to-goal, which guarantees A* will never miss an optimal path in favor of a suboptimal one it wrongly believes is cheaper.

$3^4 = 3 \times 3 \times 3 \times 3 = 81$.

Alpha-beta pruning is a pure optimization: it safely skips branches that cannot possibly influence the final decision, so it always returns the same result as plain minimax while visiting fewer nodes.

The implication $P \rightarrow Q$ is true whenever $P$ is false or $Q$ is true, which is exactly the truth condition of $\lnot P \lor Q$ — a standard logical equivalence.

Simply $bm = 2 \times 5 = 10$ — DFS only needs to store one path from root to leaf plus the unexplored siblings along it, which is linear rather than exponential in depth.

The $\forall$ symbol is the universal quantifier — the statement asserts the implication holds for every $x$, not just some particular one.

With $h(n)=0$, A*'s evaluation function becomes $f(n)=g(n)$ alone — expanding nodes purely by accumulated path cost, which is exactly uniform-cost search.

Each of the 4 variables independently picks one of 3 values, so the total number of assignments is $3^4 = 81$.

Forward chaining is data-driven: it starts from the known facts in the knowledge base and repeatedly fires rules whose conditions are satisfied, deriving new facts until the goal is reached (or no more rules apply).

2NF eliminates partial dependency: no non-prime attribute may depend on only part of a composite candidate key — every non-prime attribute must depend on the entire key.

Atomicity guarantees a transaction executes as a single indivisible unit — either all of its operations commit, or none do.

Starting from $\{A\}$: $A\to B$ adds $B$; $B\to C$ adds $C$; $C\to D$ adds $D$. So $A^+ = \{A,B,C,D\}$ — all 4 attributes, meaning $A$ alone is a candidate key.

The fact table sits at the center of the star, storing measurable, quantitative facts along with foreign keys to the surrounding dimension tables (time, product, customer, etc.).

OLAP systems are built for analytical workloads — slicing, dicing, and aggregating large historical datasets — unlike OLTP systems, which are tuned for fast, frequent, small transactions.

By the standard B+ tree convention, a leaf node of order $p$ holds at most $p-1$ keys: $4-1=3$.

BCNF is a stricter version of 3NF: for every non-trivial FD $X\to Y$, the determinant $X$ must be a superkey of the relation — no exceptions for prime attributes.

The WHERE clause filters rows (selection), and COUNT(*) then aggregates the filtered rows into a single count — a filter followed by an aggregate.

A prime attribute is any attribute that belongs to at least one candidate key. Here that set is $\{A, B, C\}$ (D and E belong to no candidate key), giving 3 prime attributes.

ETL — Extract (pull data from sources), Transform (clean/reshape it), Load (write it into the warehouse) — is the standard pipeline pattern for populating a data warehouse.

df.dropna() removes rows (by default) that contain any missing (NaN) values; fillna() instead imputes a value, and isnull() only flags them without removing anything.

23 appears 3 times, more than any other value (16 appears twice, all others once), making it the mode.

Min-max scaling maps $x \to \dfrac{x - x_{min}}{x_{max}-x_{min}}$, which by construction lands every value in $[0,1]$.

After the Map phase emits key-value pairs and the framework groups/shuffles them by key, the Reduce phase aggregates all values sharing each key (e.g., summing counts) into the final output.

20% of 10,000 is $0.20 \times 10000 = 2{,}000$ records.

The z-score transform $z = \dfrac{x - \mu}{\sigma}$ centers the data at mean 0 with unit standard deviation, by construction.

$z = \dfrac{x-\mu}{\sigma} = \dfrac{85-70}{10} = \dfrac{15}{10} = 1.5$.

Broadcasting is NumPy's rule set for implicitly expanding smaller arrays to match the shape of larger ones during arithmetic, avoiding explicit Python loops and copies where possible.

Stratified sampling divides the population into subgroups (strata) and samples proportionally from each, guaranteeing representation that simple random sampling cannot guarantee by chance alone.

$1\ \text{TB/day} \times 30\ \text{days} = 30\ \text{TB}$.

Let the numbers be $3x$ and $5x$: $3x+5x=96 \Rightarrow 8x=96 \Rightarrow x=12$. The larger number is $5x = 60$.

"Transient" means lasting only a short time. Its opposite is "permanent" (lasting indefinitely); the other three options are near-synonyms of "transient" itself.

Speed $= 300/5 = 60$ km/h. Time for 480 km $= 480/60 = 8$ hours.

A doctor practices in a hospital; analogously, a judge presides in a court — the relationship is "professional : primary workplace".

Each term follows $t_{n+1} = 2t_n + 1$: $5\to11$, $11\to23$, $23\to47$, and $47\times2+1=95$.

The premises only place engineers inside the "punctual" group and managers inside a possibly different, overlapping part of the "punctual" group — the two groups (engineers, managers) may or may not intersect, so no definite conclusion follows.

SI $= 13200-12000 = 1200$. Using $SI = \dfrac{P \cdot R \cdot T}{100}$: $1200 = \dfrac{12000 \times R \times 2}{100} \Rightarrow R = \dfrac{120000}{24000} = 5\%$.

"To bite the bullet" means to accept and endure something unpleasant or difficult because it is unavoidable.

By inclusion-exclusion, students playing at least one sport $= 30+25-10=45$. Those playing neither $= 50-45=5$.

"It's" (contraction of "it is") and "isn't" (contraction of "is not") both require apostrophes exactly where option B places them.