Data Science & Scientific Computing

📊 Key Concepts & Foundations

Algorithm Complexity

Big-O notation measures worst-case growth: $O(1)$ constant, $O(\log n)$ logarithmic, $O(n)$ linear, $O(n \log n)$ linearithmic, $O(n^2)$ quadratic, $O(2^n)$ exponential. Crucial for scalable systems.

Machine Learning Fundamentals

Supervised learning minimizes a loss function: $L(\theta) = \sum \ell(y_i, f(x_i;\,\theta))$. Gradient descent updates: $\theta \leftarrow \theta - \alpha\,\nabla L$. Bias-variance tradeoff governs generalization.

Neural Networks

Layers of neurons: $\mathbf{z} = W\mathbf{x} + \mathbf{b}$, $\mathbf{a} = \sigma(\mathbf{z})$. Backpropagation computes $\partial L / \partial W$ via chain rule. Universal approximation theorem: one hidden layer can approximate any continuous function.

Fourier Transforms

$$F(\omega) = \int_{-\infty}^{\infty} f(t)\,e^{-i\omega t}\,dt$$ Decomposes signals into frequency components. DFT for discrete data: $O(n^2)$; FFT algorithm achieves $O(n \log n)$.

Numerical Methods

Newton's method: $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$. Euler's method for ODEs: $y_{n+1} = y_n + h\,f(t_n, y_n)$. Simpson's rule for integration. Stability and convergence are paramount.

Monte Carlo Simulation

Use random sampling to estimate quantities: $\pi \approx 4 \times \dfrac{\text{points in circle}}{\text{total points}}$. Law of large numbers guarantees convergence. Error scales as $1/\sqrt{N}$.

Bayesian Inference

$$P(\theta|D) = \frac{P(D|\theta)\,P(\theta)}{P(D)}$$ Prior beliefs updated by data likelihood to form posterior. Conjugate priors simplify computation. MCMC for complex posteriors.

Information Theory

Entropy: $$H(X) = -\sum p(x)\,\log_2 p(x)\;\text{bits}$$ Mutual information: $I(X;Y) = H(X) - H(X|Y)$. KL divergence measures distribution difference. Shannon's channel capacity theorem.

✎ Problems

1 Easy

You have three sorting algorithms: Bubble Sort $O(n^2)$, Merge Sort $O(n \log n)$, and Radix Sort $O(nk)$. For a dataset of $n = 1{,}000{,}000$ integers each with at most $k = 7$ digits, estimate the number of operations each algorithm requires. Which is fastest? At what value of $n$ would Bubble Sort take approximately 1 year on a computer performing $10^9$ operations per second?

Show Hint

Bubble: $(10^6)^2 = 10^{12}$. Merge: $10^6 \times \log_2(10^6) \approx 10^6 \times 20 = 2 \times 10^7$. Radix: $10^6 \times 7 = 7 \times 10^6$. For 1 year $\approx 3.15 \times 10^7$ seconds, so max operations $= 3.15 \times 10^{16}$. Solve $n^2 = 3.15 \times 10^{16}$.

2 Easy

A binary classifier has the following confusion matrix on 1000 test samples: True Positives = 180, False Positives = 40, True Negatives = 710, False Negatives = 70. Calculate accuracy, precision, recall, F1-score, and the false positive rate. If the cost of a false negative is 10x that of a false positive, should you adjust the decision threshold up or down?

Show Hint

Accuracy $= \dfrac{TP + TN}{\text{total}} = \dfrac{890}{1000}$. Precision $= \dfrac{TP}{TP + FP} = \dfrac{180}{220}$. Recall $= \dfrac{TP}{TP + FN} = \dfrac{180}{250}$. $F_1 = \dfrac{2PR}{P + R}$. FPR $= \dfrac{FP}{FP + TN} = \dfrac{40}{750}$. Since FN is costlier, lower the threshold to increase recall (catch more positives) at the cost of more FP.

3 Medium

Compute the entropy of a source that emits symbols $\{A, B, C, D\}$ with probabilities $\{0.5, 0.25, 0.125, 0.125\}$. Design an optimal prefix-free binary code (Huffman code) for this source. What is the average code length? Compare it to the entropy. Can you explain why they match exactly in this case?

Show Hint

$H = -[0.5\log_2(0.5) + 0.25\log_2(0.25) + 0.125\log_2(0.125) + 0.125\log_2(0.125)] = 0.5 + 0.5 + 0.375 + 0.375 = 1.75$ bits. Huffman: A=0 (1 bit), B=10 (2 bits), C=110 (3 bits), D=111 (3 bits). Average $= 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75$ bits. They match because all probabilities are powers of 2.

4 Medium

Monte Carlo Estimation: You want to estimate the integral $I = \displaystyle\int_0^1 e^{-x^2}\,dx$ using Monte Carlo sampling with $N$ random points uniform on $[0,1]$. Write the Monte Carlo estimator. If $N = 10{,}000$ samples yield a mean of $0.7462$ with standard deviation $0.1283$, construct a 95% confidence interval. How many samples would you need to reduce the margin of error to $0.001$?

Show Hint

MC estimator: $\hat{I} = \dfrac{1}{N}\sum e^{-x_i^2}$. Standard error $= s/\sqrt{N} = 0.1283/\sqrt{10000} = 0.001283$. 95% CI: $0.7462 \pm 1.96 \times 0.001283$. For margin $0.001$: $N = (1.96 \times 0.1283 / 0.001)^2 \approx 63{,}300$ samples.

5 Medium

Use Newton's method to find the root of $f(x) = x^3 - 2x - 5$ starting from $x_0 = 2$. Perform three iterations. What is the order of convergence? Compare the error at each step to verify quadratic convergence. The exact root is approximately $2.09455148$.

Show Hint

$f'(x) = 3x^2 - 2$. Iteration: $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$. $x_0 = 2$: $f(2) = -1$, $f'(2) = 10$, $x_1 = 2.1$. $x_1 = 2.1$: $f(2.1) = 0.061$, $f'(2.1) = 11.23$, $x_2 \approx 2.09457$. Check that each error is roughly the square of the previous error (quadratic convergence).

6 Medium

Bayesian Reasoning: A medical test for a rare disease (prevalence 1 in 1000) has 99% sensitivity (true positive rate) and 99% specificity (true negative rate). If a patient tests positive, what is the probability they actually have the disease? Explain why this result surprises most people. What prevalence would make a positive test result 50% reliable?

Show Hint

$P(D|+) = \dfrac{P(+|D)\,P(D)}{P(+|D)\,P(D) + P(+|\neg D)\,P(\neg D)} = \dfrac{0.99 \times 0.001}{0.99 \times 0.001 + 0.01 \times 0.999} \approx \dfrac{0.00099}{0.01098} \approx 9.0\%$. For 50%: solve $0.99p = 0.01(1-p)$, giving $p \approx 1/100 = 1\%$.

7 Hard

A single-layer neural network (perceptron) with sigmoid activation $\sigma(z) = \dfrac{1}{1+e^{-z}}$ is trained on 2D data with weights $\mathbf{w} = [0.5,\,-0.3]$ and bias $b = 0.1$. For input $\mathbf{x} = [2, 3]$, compute the forward pass output. Then, if the true label is $y = 1$ and we use binary cross-entropy loss $L = -[y\ln(\hat{y}) + (1-y)\ln(1-\hat{y})]$, compute $\partial L/\partial w_1$, $\partial L/\partial w_2$, and $\partial L/\partial b$ using backpropagation.

Show Hint

Forward: $z = 0.5(2) + (-0.3)(3) + 0.1 = 1.0 - 0.9 + 0.1 = 0.2$. $\hat{y} = \sigma(0.2) = 1/(1+e^{-0.2}) \approx 0.5498$. For cross-entropy with sigmoid: $\partial L/\partial z = \hat{y} - y = 0.5498 - 1 = -0.4502$. Then $\partial L/\partial w_1 = (\hat{y}-y) \times x_1 = -0.4502 \times 2 = -0.9004$. $\partial L/\partial w_2 = -0.4502 \times 3$. $\partial L/\partial b = -0.4502$.

8 Hard

Fourier Analysis: A signal $f(t) = 3\sin(2\pi \times 50\,t) + \sin(2\pi \times 120\,t)$ is sampled at $1000$ Hz for 1 second ($N = 1000$ points). What frequencies will appear in the DFT? What is the frequency resolution? If the sampling rate were reduced to $200$ Hz, what happens to the 120 Hz component? Explain aliasing and the Nyquist theorem in this context.

Show Hint

DFT shows peaks at $50$ Hz (amplitude 3) and $120$ Hz (amplitude 1). Frequency resolution $= f_s/N = 1000/1000 = 1$ Hz. Nyquist frequency at $1000$ Hz sampling $= 500$ Hz, so both components are captured. At $200$ Hz sampling, Nyquist $= 100$ Hz. The $120$ Hz component exceeds Nyquist and aliases to $|200 - 120| = 80$ Hz — a false frequency appears!

9 Hard

Compare Euler's method, the midpoint method (RK2), and the classical Runge-Kutta (RK4) method for solving $dy/dx = -2y$ with $y(0) = 1$ (exact solution: $y = e^{-2x}$). Use step size $h = 0.1$ and compute $y(0.5)$. Calculate the absolute error for each method. How does the error scale with $h$ for each method?

Show Hint

Exact: $y(0.5) = e^{-1} \approx 0.36788$. Euler (order 1): each step $y_{n+1} = y_n + h(-2y_n) = y_n(1-2h) = 0.8\,y_n$. After 5 steps: $y = (0.8)^5 = 0.32768$. Error $\approx 0.040$. RK2 error scales as $O(h^2)$, RK4 as $O(h^4)$. RK4 gives ~6 more correct decimal places than Euler for the same step size.

10 Hard

Bias-Variance Tradeoff: A polynomial regression model of degree $d$ is fit to noisy data generated from a true quadratic function $y = 2x^2 - x + 1 + \varepsilon$ where $\varepsilon \sim \mathcal{N}(0, 0.5^2)$. Qualitatively describe the bias and variance as $d$ increases from 1 to 20. At $d = 1$, what is the nature of the error? At $d = 15$ with 20 data points? What criterion (AIC, BIC, or cross-validation) would you use to select the optimal $d$, and why?

Show Hint

$d = 1$ (linear): high bias (underfitting), low variance — model cannot capture the quadratic shape. $d = 2$: optimal, low bias and low variance. $d = 15$ with 20 points: low bias but very high variance (overfitting) — model fits noise. Cross-validation is generally preferred as it directly estimates prediction error without assumptions about model form. BIC penalizes complexity more strongly than AIC.

11 Advanced

KL Divergence & Information: Consider two probability distributions: $P = \{0.3, 0.4, 0.2, 0.1\}$ and $Q = \{0.25, 0.25, 0.25, 0.25\}$ (uniform). Compute the KL divergence $D_{\text{KL}}(P \| Q)$ and $D_{\text{KL}}(Q \| P)$. Show that KL divergence is not symmetric. Then compute the mutual information $I(X; Y)$ for two binary variables where $P(X=0,Y=0) = 0.4$, $P(X=0,Y=1) = 0.1$, $P(X=1,Y=0) = 0.2$, $P(X=1,Y=1) = 0.3$.

Show Hint

$D_{\text{KL}}(P\|Q) = \sum P(i)\ln\!\left(\dfrac{P(i)}{Q(i)}\right) = 0.3\ln(1.2) + 0.4\ln(1.6) + 0.2\ln(0.8) + 0.1\ln(0.4)$. $D_{\text{KL}}(Q\|P) = \sum Q(i)\ln\!\left(\dfrac{Q(i)}{P(i)}\right)$. These differ because $\ln(a/b) \neq -\ln(a/b)$ when weighted differently. For mutual information: $I(X;Y) = \sum\sum P(x,y)\log\!\left(\dfrac{P(x,y)}{P(x)P(y)}\right)$. First compute marginals: $P(X=0) = 0.5$, $P(X=1) = 0.5$, $P(Y=0) = 0.6$, $P(Y=1) = 0.4$.

12 Advanced

MCMC & Bayesian Computation: You observe data $x_1 = 3.2$, $x_2 = 2.8$, $x_3 = 3.5$, $x_4 = 3.1$ from a normal distribution $\mathcal{N}(\mu, 1)$. Using a prior $\mu \sim \mathcal{N}(0, 10^2)$, derive the posterior distribution analytically. Then explain how the Metropolis-Hastings algorithm could be used to sample from the posterior when no closed-form solution exists. What is the acceptance probability formula? Why is a "burn-in" period necessary?

Show Hint

With known variance $\sigma^2 = 1$ and normal prior $\mathcal{N}(\mu_0, \tau^2)$: posterior is $\mathcal{N}(\mu_n, \sigma_n^2)$ where $\sigma_n^2 = \dfrac{1}{n/\sigma^2 + 1/\tau^2} = \dfrac{1}{4 + 0.01} = 0.2494$ and $\mu_n = \sigma_n^2\!\left(\dfrac{n\bar{x}}{\sigma^2} + \dfrac{\mu_0}{\tau^2}\right) = 0.2494 \times (4 \times 3.15 + 0) \approx 3.14$. MH acceptance: $\alpha = \min\!\left(1,\;\dfrac{P(\theta'|D)}{P(\theta|D)} \times \dfrac{q(\theta|\theta')}{q(\theta'|\theta)}\right)$. Burn-in discards initial samples before the chain converges to the stationary distribution.