CS 301 Midterm 2

Data of every kind becomes an array, and the shape of the array says what the data is

Data	One point	A batch of N points
a row of a table	m numbers	N×m
a grey image	H×W	N×H×W
a colour image	H×W×3	N×H×W×3
a text of L words	L×m	N×L×m

Standard Deviation

Standardized Value

W.T where W is a matrix

Values swapped (3, 8) → (8, 3)

Sigmoid

S.sum(axis=1, keepdims=True) in PyTorch

S.sum(dim=1, keepdim=True)

np.exp(S) in PyTorch

torch.exp(S)

S.max(axis=1) in PyTorch

S.max(dim=1).values

np.array([1.0, 2.0]) in PyTorch

torch.tensor([1.0, 2.0])

A group measures the product X @ W.T + b at size 4,096: 0.39 seconds on a CPU with 32 cores, and 0.03 seconds on a T4 GPU, thirteen times less. Which statement explains why the GPU is so much faster here?

Each entry of the result is a sum of products that depends on no other entry, so thousands of small cores compute different entries at the same time.

Broadcasting

Occurs during an element-wise operation (like +, -, *, /) between two arrays of different shapes.

In a session with a GPU, the tensors X_t, W_t and b_t are in the memory of the CPU. Which code computes the scores of the layer on the GPU?

Copy X_t, W_t and b_t to CUDA, then compute the scores using those tensors.

The exact inner-loop count of layer_loops is n × K × m, summarized as O(nKm). Which additional quantity is needed to turn that count into an elapsed-time estimate?

The measured average time per inner iteration.

The three loops of layer_loops take 0.6 seconds for n = 2,000 points, m = 50 coordinates and K = 10 neurons. Assuming approximately the same time per inner iteration, estimate the time for n = 4,000, m = 100 and K = 10.

2.4 seconds

On one machine, NumPy reaches 1 billion operations per second when it adds two arrays of 16 million numbers, and 50 billion operations per second when it computes the product X @ W.T with n = m = K = 2,048. Which statement explains the difference?

The product reuses cached inputs; each array-addition input is used only once.

A row-major matrix is too large for cache. In the notebook’s loops with NumPy summing each slice, column-wise traversal takes longer than row-wise traversal. Why can this happen?

Column traversal can evict cache lines before using their other entries.

In a column-reading benchmark, rows of 2,049 float64 entries run faster than rows of 2,048. Which cache effect can explain this?

The power-of-two stride concentrates accesses in fewer cache sets.

Roofline

Speed ≤ min(peak rate, 300 GB/s × operations per byte)

X and W are 1,200 × 1,200 float32 matrices, with 4 bytes per entry. Their product uses about 2 × 1,200³ arithmetic operations. In an idealized memory-traffic estimate, each input is read once and the result written once. How many operations are performed per byte transferred?

200

The T4 reaches at most 8 trillion operations a second, and its memory delivers at most 300 GB a second. A computation does 2 operations for every byte that it reads or writes.

At most how many billion operations a second can this computation reach on the T4?

600 billion

Arithmetic Intensity

Operations per Byte Transferred

Ridge Point

Peak Operations / Peak Bandwidth

On the T4, the roof turns at about 27 operations a byte: below that, memory sets the speed. Using the idealized arithmetic-intensity model in the slides, which computations fall below that ridge point? Check all that apply.

• a layer of K = 4 neurons applied to a million points with 1,000 coordinates each

• a + b on two arrays of 16 million float32 numbers

• elementwise multiplication of two long float32 arrays

Energy

Power * Time

Efficiency

Total Operations / Total Energy

In the hardware-energy example discussed in class, which action uses the most energy?

Fetching a value from external DRAM onto the chip.

A neural network layer applying $K$ neurons to $n$ data points with $m$ features

Requires 2 x n x m K Arithmetic operations

Big-O

O(nKm)

Throughput

$$\text{Throughput}=\min\big(\text{Peak Arithmetic Rate},\;\text{Bandwidth}\times\text{Intensity}\big)$$

Left of Ridge (< 27 ops/byte)

Memory-Bound. Bandwidth limits speed (e.g., vector addition a+b, and layers with few neurons like k = 4)

Right of Ridge (> 27 ops/byte)

Compute-Bound

A system has three equations in three unknowns. The coefficient rows of the first two equations are linearly independent. The third equation, including its right-hand side, is the first minus the second. What follows?

The coefficient matrix has rank 2, and there are infinitely many solutions.

If k(A) ≈ 1

The equations are perpendicular

If k(A) = 1,000,000

The equations are nearly parallel / nearly linearly dependent.

For a nonsingular system Ax = b with A fixed and b nonzero, what does the condition number κ(A) tell us about a small perturbation of b?

It bounds the amplification from relative change in b to relative change in x.

Rule of thumb formula

16 − log₁₀(condition number)

Let x_v be the probability that a random walk starting at v reaches red before blue. Node v is neither red nor blue and has exactly three neighbours: 3, 7 and 12. Each is chosen with probability 1/3 on the next step. Which equation holds?

x_v = (x_3 + x_7 + x_12) / 3

In forward elimination, let factor = A[i, k] / A[k, k], with a nonzero pivot. The algorithm subtracts factor times row k from row i and makes the same change to the right-hand side. What is the purpose?

To remove unknown k from equation i while preserving the solutions.

After elimination, Ux = c has an upper-triangular U with nonzero diagonal entries. In which order does back substitution find the unknowns?

Last to first, using the unknowns already found below.

Suppose elimination takes 0.5 seconds at n = 1,000. Using its leading cubic operation count and assuming similar throughput, estimate the time at n = 2,000.

4 seconds

Which statements support using a suitable direct solver rather than explicitly forming A⁻¹ to solve Ax = b for one right-hand side?

• Forming the inverse and multiplying by b can produce a less accurate solution.

• A direct solve avoids constructing an entire inverse that this task does not need.

• A sparse direct solver can avoid storing a full inverse when sparse A has a dense inverse.

COO

Row, column, and value

CSR

Groups entries by row and records row boundaries. (A @ v: O(nnz + N))

CSC

Groups by column

A matrix with 300 rows and 1,200 nonzeros is stored in the CSR format. How many entries does its array indptr have?

301

In the CSR format, where are the nonzeros of row i?

In data[indptr[i]:indptr[i + 1]], with matching positions in indices.

Dense Storage

Every Entry is stored in Memory

For a 4,000 × 4,000 matrix-vector product, why does the density at which dense storage becomes faster than CSR depend on the machine and library?

CSR skips zeros but adds index handling; the two implementations have different throughput.

The off-diagonal nonzero pattern of a symmetric positive-definite matrix is a star: node 0 is connected to five leaves. For generic nonzero values, how does eliminating node 0 first compare with eliminating all leaves first?

Centre first connects the leaves; leaves first produces no fill.

Z holds the columns of a table with n rows, each column standardized: minus its mean, divided by its standard deviation (dividing by n, as np.std does). Which expression gives the correlation matrix of all the columns at once?

Z.T @ Z / n

In the has-rated matrix B, 215 people rated Toy Story, 202 rated Independence Day, and 122 rated both. What is the cosine similarity of the two columns of B?

122 / sqrt(215 x 202), about 0.585

Under the has-rated matrix B, the movies nearest to Toy Story are Independence Day, Jurassic Park and Forrest Gump. Under the user-centred ratings (each rating minus that person's mean rating, 0 where there is no rating) they are Toy Story 2, Aladdin and Toy Story 3. Why do the lists differ?

B measures shared raters, which favours popular movies; the centred ratings measure whether the same people rate both movies above, or both below, their own usual rating.

XX^T

Compare Rows. (n x n) The dot product of observations i and j

X^TX

Compare Columns. (m x m) The dot product of features a and b

XX^T work

O(n²m)

X^TX

O(nm²)

XW^T

O(nKm)

The Residual

(r = b − A x̂) measures how closely x̂ satisfies the equations

Which statement correctly describes the SVD of the centered data matrix X = USV^T?

The columns of V are the feature-space axes, and US = XV contains the point coordinates.

Variance

Standard Deviation Squared (Vax)

A dataset has singular values 3, 2, and 1. What fraction of the total variance is retained by keeping the first two PCA axes?

13/14

The only links are A → B, A → C, B → C, C → A, and D → C.

In the sending matrix G, columns are senders and rows are receivers. Write an entry as G[row, column]. Which entry represents the link from A to C?

G[C, A] = 1/2

Uniform Restart Equation

$$r_C^{\text{new}} = \alpha \cdot (\text{incoming score to } C) + \frac{1 - \alpha}{N}$$

The only links are A → B, A → C, B → C, C → A, and D → C. The current scores are r_A = 0.4, r_B = 0.2, r_C = 0.3, and r_D = 0.1.

Each page splits its current score equally among its outgoing links. Use α = 0.8 and uniform restarts across the four pages. What is C’s new score?

0.45

What is one reason PageRank includes random restarts?

They allow the walker to leave a closed group of pages with no outgoing links to the rest of the graph.

Two pixels far apart have identical RGB values. What additional information does a grid graph represent?

Which pixels are spatial neighbors.

A walker can leave a node along edges of weights 1, 2, and 5. What is the probability of choosing the weight-5 edge?

5/8

In seeded segmentation, a pixel has foreground probability h_i = 0.8. What does this mean?

A walk starting there has probability 0.8 of reaching foreground seeds before background seeds.

Value of an unseeded node

$$h = \frac{\sum (w_i \cdot h_i)}{\sum w_i}$$

When solving for segmentation probabilities, where do we enforce (Lh)_i = 0?

At unseeded nodes; seed values are fixed separately.

For a symmetric positive semidefinite matrix, which statement about SVD is correct?

Its singular values equal its eigenvalues, and its singular vectors can be chosen as eigenvectors.

A connected graph’s Laplacian has eigenvalues 0, 0.2, 0.7, 3, 5. Which two eigenvectors provide the spectral drawing used in class?

Those for 0.2 and 0.7.

A tangled graph becomes three visibly separated groups after changing to spectral coordinates. What is justified?

New coordinates revealed possible community structure in the same graph.

A PCA plot of genetic measurements resembles European geography, although its two components explain a small fraction of the variation. What is the best interpretation?

A small share of total variation can still reveal a meaningful pattern.