Loops and Arrays

Write find_min_max(numbers) that returns (minimum, maximum).

Before you code:

• How would you find the minimum if you could only look at one number at a time?

Test cases:

find_min_max([5, 8, 2, 10, 3])  # (2, 10)
find_min_max([7, 7, 7, 7])       # (7, 7)
find_min_max([-3, 0, 3])         # (-3, 3)

You want to rescale any value to [0, 1] relative to the dataset, so the minimum maps to 0 and the maximum maps to 1.

Think it through: Given [10, 20, 30], what operation maps 10 → 0 and 30 → 1? What does 20 become? Can you write a general formula using min and max?

Write min_max_normalize(value, data). Reuse find_min_max.

min_max_normalize(20, [10, 20, 30])  # 0.5
min_max_normalize(10, [10, 20, 30])  # 0.0
min_max_normalize(30, [10, 20, 30])  # 1.0

Write compute_mean(numbers) — average of the list. Return 0 for an empty list.

compute_mean([2, 4, 6, 8])   # 5.0
compute_mean([10, 20, 30])   # 20.0
compute_mean([])             # 0

Standard deviation measures how spread out values are around the mean:

$$\sigma = \sqrt{\frac{1}{n}\sum_{i=1}^{n}(x_i - \mu)^2}$$

Break the formula into pieces you can compute step by step. You already have compute_mean.

Write compute_sd(numbers).

compute_sd([2, 4, 4, 4, 5, 5, 7, 9])  # 2.0
compute_sd([10, 10, 10, 10])           # 0.0
compute_sd([0, 6])                     # 3.0

The z-score tells you how many standard deviations a value is from the mean.

Think about it: In [10, 12, 12, 13, 12, 11, 90], the value 90 looks suspicious. How far is it from the mean? And how does that distance compare to the "typical spread" (the SD)? Write a formula for "how many SDs from the mean."

Values with $|z| >$ threshold are outliers.

Write find_outliers(nums, threshold). Reuse compute_mean and compute_sd.

find_outliers([10, 12, 12, 13, 12, 11, 90], 2)  # [90]
find_outliers([5, 6, 7, 8, 9, 10, 100], 2)       # [100]
find_outliers([1, 2, 3, 4, 5], 2)                # []

$Q_1$ is the median of the lower half of the sorted data; $Q_3$ is the median of the upper half.

You know $Q_1$ (median of the lower half) and $Q_3$ (median of the upper half). What single number captures the width of the "middle 50%" of the data?

$$IQR = Q_3 - Q_1$$

Think about how to find the median of just the lower or upper half of a sorted list.

Write compute_iqr(data).

compute_iqr([1, 2, 3, 4, 5, 6, 7, 8, 9])  # 4.0  (Q1=3, Q3=7)
compute_iqr([10, 20, 30, 40, 50, 60])      # 30.0 (Q1=20, Q3=50)

Run this cell to visualise the statistics you have built so far.

You want to transform a dataset so its mean becomes 0 and its standard deviation becomes 1. What operation shifts the mean to 0? What further operation scales the SD to 1? Combine both.

Write standardize(data). Reuse compute_mean and compute_sd.

standardize([10, 10, 10])    # [0.0, 0.0, 0.0]
# After standardizing [1,2,3,4,5]:
#   mean of result  == 0.0
#   SD of result    == 1.0

How wrong is a model? These functions measure the gap between actual and predicted values.

1. Compute error = actual[i] − predicted[i] for each pair.
2. Square each error.
3. Average the squared errors.
4. Take the square root.

Write compute_rmse(actual, predicted).

compute_rmse([2, 3, 4], [3, 2, 5])  # 1.0
compute_rmse([1, 2, 3], [1, 2, 3])  # 0.0

Bonus: What is compute_rmse([2, 3, 4], [3, 1, 7])?

Mean Absolute Error (MAE) measures how wrong predictions are, on average.

Think: For each pair (actual, predicted), what's the simplest measure of "how wrong"? Why use absolute value instead of plain difference? How do you combine all the individual errors into one summary number?

Write compute_mae(actual, predicted) for 1-D lists.

compute_mae([3, 5, 2], [2, 5, 4])  # 1.0
compute_mae([1, 2, 3], [1, 2, 3])  # 0.0

Extension: Modify your function to handle N-D points (each element can be a list of coordinates). When elements are lists, compute the absolute difference per coordinate, then average over all coordinates across all points.

# 2-D: two points, 2 coordinates each
compute_mae([[0,0],[2,0]], [[1,0],[2,1]])  # (1+0+0+1)/4 = 0.5

Huber loss is a hybrid: squared error for small errors, absolute error for large ones. This makes it robust to outliers.

For each pair $(y, \hat{y})$:

• If $|y - \hat{y}| \le \delta$: 0.5 * (y - y_pred)^2
• Else: delta * |y - y_pred| - 0.5 * delta^2

Return the average over all pairs.

Worked example: y_true=[5,2,7], y_pred=[4.8,2.5,10], delta=1

• (5, 4.8): |0.2| ≤ 1 → 0.5 × 0.04 = 0.02
• (2, 2.5): |0.5| ≤ 1 → 0.5 × 0.25 = 0.125
• (7, 10): |3.0| > 1 → 1×3 − 0.5 = 2.5
• Average = (0.02 + 0.125 + 2.5) / 3 ≈ 0.8817

Write compute_huber_loss(y_true, y_pred, delta).

abs(compute_huber_loss([5,2,7],[4.8,2.5,10],1) - 0.8817) < 1e-3  # True
compute_huber_loss([1,2,3],[1,2,3],1)                              # 0.0

Your model's predictions for 5 data points have errors: [1, 1, 1, 1, 20]. Which error metric will be affected MORE by the single large error of 20?

A. MAE (Mean Absolute Error)

B. RMSE (Root Mean Square Error)

C. Both are affected equally

D. Neither — both ignore outliers

Finding the closest point is the core of the k-Nearest-Neighbors (k-NN) algorithm. We build up from 1-D to N-D, then add a pluggable distance function.

In the If-Else chapter you compared distances in 2-D. Now generalize to N dimensions: given three N-D points P, A, B (each a list), return "A", "B", or "Equal".

You do not need sqrt — comparing squared distances is enough.

Write closer_point(P, A, B).

closer_point([1, 2], [0, 0], [5, 5])          # "A"
closer_point([3, 3, 3], [0, 0, 0], [6, 6, 6]) # "Equal"
closer_point([15, 15], [2, 2], [20, 20])       # "B"

Given a list of numbers and a target, return the number closest to the target. Distance = |number − target|.

Write find_nearest_1d(numbers, target).

find_nearest_1d([2, 5, 8, 12], 6)    # 5
find_nearest_1d([1, 4, 10, 20], 15)  # 10

Now points are (x, y) tuples. Use Euclidean distance. (Again, squared distance is enough for comparison.)

Write find_nearest_2d(points, target).

find_nearest_2d([(1,2),(3,4),(6,1)], (2,3))  # (1, 2)
find_nearest_2d([(0,0),(5,5),(2,1)], (3,3))  # (2, 1)

Run this cell to visualise nearest-neighbour search.

Generalize: each point is a list of any length.

Write find_nearest_nd(point, points).

find_nearest_nd([1,2], [[3,4],[2,1],[0,0]])              # [2, 1]
find_nearest_nd([0,0,0], [[1,1,1],[2,2,2],[-1,-1,-1]])   # [1, 1, 1]

Different problems use different distance metrics. Accept the metric as an argument.

First implement two distance functions, then implement the general search.

Write:

1. euclidean_distance(p1, p2)
2. manhattan_distance(p1, p2) — sum of |a − b| per coordinate
3. find_nearest_neighbour(target, points, distance_func)

find_nearest_neighbour([1,2], [[3,4],[2,2],[0,0]],
                       euclidean_distance)   # [2, 2]
find_nearest_neighbour([1,2,3], [[5,5,5],[0,0,0],[2,2,2]],
                       manhattan_distance)   # [2, 2, 2]

A dataset has two features: age (range 0–100) and salary (range 20,000–200,000). You want to find the nearest neighbor using Euclidean distance. What happens if you DON'T normalize the features first?

A. The algorithm won't run — Python will throw an error

B. Salary will dominate the distance calculation because its numbers are much larger, making age nearly irrelevant

C. Age will dominate because it has a smaller range

D. It makes no difference — Euclidean distance handles different scales automatically

A polynomial like $2x^3 + 0x^2 + 3x + 10$ is stored as a list of coefficients in descending power order: [2, 0, 3, 10]. Index 0 = highest power; last index = constant term ($x^0$).

$(2x^3 + 3x + 10) \times 5 = 10x^3 + 15x + 50$

List form: [2, 0, 3, 10] * 5 = [10, 0, 15, 50]

Write multiply_polynomial(poly, num).

multiply_polynomial([2, 0, 3, 10], 5)  # [10, 0, 15, 50]
multiply_polynomial([1, -2, 4], 3)      # [3, -6, 12]
multiply_polynomial([1, 0], 0)          # [0, 0]

$(2x^2 + 3x + 4) + (x^2 + 5x + 6) = 3x^2 + 8x + 10$

List form: [2, 3, 4] + [1, 5, 6] = [3, 8, 10]

Tricky part: If the polynomials have different lengths, align them from the right (the constant terms line up) and treat missing higher-power terms as 0.

(5x + 2) + (3) → [5, 2] + [3] → [5, 5]

Write add_polynomials(p1, p2).

add_polynomials([2, 0, 3, 10], [1, 4, 0, 6])  # [3, 4, 3, 16]
add_polynomials([5, 2], [3])                   # [5, 5]
add_polynomials([1], [1])                      # [2]

$(2x + 3)(x + 4) = 2x^2 + 8x + 3x + 12 = 2x^2 + 11x + 12$

List form: [2, 3] * [1, 4] = [2, 11, 12]

Strategy: Each coefficient c at position i in p1 has power (len(p1)-1-i). Multiplying c * p2 by $x^k$ means appending k zeros to the end.

• Take each term from p1.
• Scale p2 by that coefficient: multiply_polynomial(p2, c).
• Shift left by the power (append zeros): shifted = scaled + [0]*k.
• Sum all shifted results with add_polynomials.

Write multiply_polynomials(p1, p2). Reuse multiply_polynomial and add_polynomials.

multiply_polynomials([2, 3], [1, 4])         # [2, 11, 12]
multiply_polynomials([2, 0, 3, 10], [1, 2])  # [2, 4, 3, 16, 20]
multiply_polynomials([1], [5])               # [5]

A linear equation with N variables: $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b$ is stored as [a1, a2, ..., an, b] (coefficients then RHS). A system of equations is a list of such lists. You will build a recursive solver step by step.

If you know all variables except the first, you can rearrange the equation to solve for it. Try it by hand with the worked example below, then generalize.

Write solve_for_first_variable(equation, vars) where vars contains values for $x_2, x_3, \ldots$

Worked example:

• equation = [3, 4, 6, 20], vars = [5, 6]
• $3x + 4(5) + 6(6) = 20$ → $3x = 20 - 20 - 36 = -36$ → $x = -12$

solve_for_first_variable([3, 4, 6, 20], [5, 6])  # -12.0
solve_for_first_variable([2, 5, 7], [4])          # -6.5

To eliminate the variable at position var_index from two equations:

1. Let c1 = eq1[var_index], c2 = eq2[var_index].
2. Compute c2 * eq1 - c1 * eq2 element by element.
3. The result has a 0 at position var_index. Drop that position.
4. Return the shorter list.

Worked example: Eliminate x (index 0) from [2, 1, 5] and [1, -1, 1]:

• c1=2, c2=1: 1*[2,1,5] - 2*[1,-1,1] = [0, 3, 3]
• Drop index 0: [3, 3] — this represents $3y = 3$

Write eliminate_variable_pair(eq1, eq2, var_index).

eliminate_variable_pair([2, 1, 5], [1, -1, 1], 0)   # [3, 3]
eliminate_variable_pair([1, 2, 3], [2, 1, 4], 1)    # [-3, -5]

Verify the second by hand: c1=2, c2=1: 1[1,2,3]-2*[2,1,4] = [-3,0,-5], drop idx 1 → [-3,-5]*

Given a full system of equations, eliminate the variable at var_index using the first equation (the pivot) against each other equation.

1. Let pivot = equations[0].
2. For each other equation, call eliminate_variable_pair(pivot, other, var_index).
3. Return the list of reduced equations (pivot not included — it served its purpose).

Write eliminate_variable(equations, var_index).

# System: 2x + y = 5, x - y = 1
eliminate_variable([[2, 1, 5], [1, -1, 1]], 0)
# Eliminates x using pivot [2,1,5] vs [1,-1,1]
# c1=2, c2=1: 1*[2,1,5]-2*[1,-1,1] = [0,3,3] → [3,3]
# Returns: [[3, 3]]

Now put it all together:

Base case: One equation, one unknown: x = equation[-1] / equation[0].

Recursive case:

1. Eliminate variable 0 from the system → reduced system.
2. Recursively solve the reduced system → values for $x_2, x_3, \ldots$
3. Substitute those into the first equation to find $x_1$ (use solve_for_first_variable).
4. Return [x1] + [x2, x3, ...].

Write solve_equations(equations).

# 2 variables: 2x + y = 5, x - y = 1
solve_equations([[2, 1, 5], [1, -1, 1]])   # [2.0, 1.0]

# 3 variables: x+y+z=6, 2y+5z=-4, 2x+5y-z=27
solve_equations([[1,1,1,6],[0,2,5,-4],[2,5,-1,27]])
# [5.0, 3.0, -2.0]

Random processes underlie stochastic gradient descent, Monte Carlo methods, and many more ML algorithms. You will build from a simple coin toss up to a temperature-scaled weighted sampler.

Write fair_coin_toss() that:

• Uses random.random() (returns float in [0, 1)).
• Prints "HEAD" and returns 0 if the value < 0.5.
• Prints "TAIL" and returns 1 otherwise.

Run it 10 times. Is it roughly 50/50?

Write biased_coin_toss() — Head 70% of the time, Tail 30%. Print "Head" / "Tail", return 0 / 1.

After writing, run 1000 tosses and check that the fraction of heads is near 0.70.

Generalise: write biased_coin_toss(p) where p is the probability of Head.

biased_coin_toss(0.3)  # Head ~30% of the time
biased_coin_toss(0.9)  # Head ~90% of the time

Given a list of probabilities that sum to 1, return one index chosen according to those weights.

Idea: Build cumulative boundaries.

• [0.5, 0.3, 0.2] → boundaries [0.5, 0.8, 1.0]
• Draw r = random.random().
• Return the first index whose boundary exceeds r.

Write weighted_choice(probabilities).

Before you code: If r=0.6, which index is chosen?

# Statistical test: ~50%, ~30%, ~20% for each index
weighted_choice([0.5, 0.3, 0.2])  # returns 0, 1, or 2

Divide each weight by the total sum so the list sums to 1.

Write normalize_to_probabilities(numbers).

normalize_to_probabilities([1, 2, 2])  # [0.2, 0.4, 0.4]
normalize_to_probabilities([3, 3, 4])  # [0.3, 0.3, 0.4]

Take the array [1, 2, 5, 10]. After normalizing to probabilities, the value 10 gets about 55% of the total — but you want the big values to stand out even more and the small values to shrink further.

Come up with as many ideas as you can to amplify the differences before normalizing. Test each one:

1. Multiply every value by 10. Normalize. Did the probabilities change?
2. Square every value. Normalize. Did the probabilities change?
3. Cube every value. Normalize. What about now?
4. Can you think of any other transformation?

For each idea, print the resulting probabilities and explain whether (and why) it worked.

You built normalize, but it fails when values are negative — negative "probabilities" make no sense.

Key idea: What if you transformed each value to be positive first, while preserving order? Try math.exp(x) — it is always positive, and larger inputs give larger outputs. Now normalize these exponentials.

Write softmax(values).

All outputs should be positive and sum to 1.

softmax([1, 2, 3])   # approx [0.090, 0.245, 0.665]
softmax([2, 2, 2])   # [0.333, 0.333, 0.333]
sum(softmax([1, 2, 3])) == 1.0  # True (up to floating point)

Problem: math.exp(1000) raises OverflowError.

Your challenge: Try softmax([1000, 1001, 1002]). It crashes! The exponentials are astronomically large. But you only care about the ratios, not the absolute sizes. What constant could you subtract from every value before exponentiating, to keep the numbers small without changing the ratios? Try it and verify the result matches softmax([1, 2, 3]).

Rewrite softmax(values) with this trick.

softmax([1000, 1001, 1002])  # [0.090, 0.245, 0.665] — no overflow!

Verify that softmax([1,2,3]) and softmax([1000,1001,1002]) give the same result.

Experiment: What happens to the softmax output if you divide all values by 2 before applying softmax? Try it. Then try dividing by 0.5. What pattern do you see?

Dividing by a number $T$ before softmax controls the sharpness of the distribution. This $T$ is called the temperature.

• Predict: what happens when $T = 1$?
• Predict: what happens when $T < 1$?
• Predict: what happens when $T > 1$?

Write softmax_with_temperature(values, T).

softmax_with_temperature([1, 2, 3], 1)    # [0.090, 0.245, 0.665]
softmax_with_temperature([1, 2, 3], 0.5)  # sharper
softmax_with_temperature([1, 2, 3], 2)    # flatter

Run this cell to visualise softmax at different temperatures.

Combine what you have built: given weights and temperature $T$, sample an index with probability proportional to weight^(1/T).

Steps:

1. scaled = [w ** (1.0 / T) for w in weights]
2. probs = normalize_to_probabilities(scaled)
3. Return weighted_choice(probs)

Write weighted_choice_with_temperature(weights, T).

Before you code:

• What happens as $T \to 0$? (The largest weight dominates completely.)
• What happens as $T \to \infty$? (All weights become equal.)

Raise ValueError if $T \le 0$ or all weights are zero.

Run a statistical test: with weights [1, 2, 8], index 2 should be chosen more often at $T=0.5$ than at $T=2$.

In softmax with temperature, what happens as the temperature T approaches 0?

A. All outputs become equal (uniform distribution)

B. The output with the highest input gets nearly all the probability — the distribution becomes "sharper"

C. All outputs become 0

D. The function becomes undefined

A nested list contains other lists inside it, to any depth: [1, [1, 2, [3, 4]]]

Flattening produces a single flat list: [1, 1, 2, 3, 4].

Write flatten_list(nested_list) using recursion.

Before you code:

• Use isinstance(element, list) to check if an element is a sub-list.
• Base action: if the element is a number, add it to the result directly.
• Recursive action: if the element is a list, call flatten_list on it and extend.

flatten_list([1, [1, 2, [3, 4]]])    # [1, 1, 2, 3, 4]
flatten_list([1, [2, [3, [4, 5]]]])  # [1, 2, 3, 4, 5]
flatten_list([1, 2, 3])              # [1, 2, 3]
flatten_list([[[]]])                 # []

Instead of strings like "(20+40)*90", expressions are stored as nested arrays:

• ["+", 20, 40] means 20 + 40 = 60
• ["*", ["+", 20, 40], 90] means (20 + 40) × 90 = 5400

Format: [operator, left_operand, right_operand]. Each operand is either a number or another such array.

Write solve_expression(expr) using recursion.

Before you code:

• Base case: if expr is a number (not a list), return it.
• Recursive case:
  1. Extract operator = expr[0], left = expr[1], right = expr[2].
  2. Recursively solve left and right.
  3. Apply the operator (+, -, *, /).

solve_expression(42)                                   # 42
solve_expression(["+", 20, 40])                        # 60
solve_expression(["*", ["+", 20, 40], 90])             # 5400
solve_expression(["-", ["*", ["/", 100, 10], 5], 15])  # 35

solve_expression assumed every operator takes exactly two operands. Real calculators are pickier and more flexible: + happily sums ten numbers, but sqrt of two numbers is nonsense.

Write calculate(expr) — an upgraded evaluator:

• New operators: "sqrt" (use x ** 0.5) and "log" (base 10 — math.log10).
• Arity rules: + and * accept two or more operands; - and / accept exactly two; sqrt and log accept exactly one. Wrong count → raise ValueError with a message naming the operator.
• Unknown operator → ValueError too.
• Operands may be numbers or nested expressions, as before.

Hint: evaluate all operands first (args = [calculate(a) for a in expr[1:]]), then check len(args) against the operator's rule before applying it.

calculate(42)                                      # 42
calculate(["+", 1, 2, 3])                          # 6
calculate(["*", 2, 3, 4])                          # 24
calculate(["-", 10, 4])                            # 6
calculate(["/", 8, 2])                             # 4
calculate(["sqrt", 16])                            # 4
calculate(["log", 100])                            # 2
calculate(["+", ["sqrt", 16], ["log", 1000], 2])   # 9

These should all raise ValueError:

["-", 1, 2, 3]   # - takes exactly 2
["sqrt", 4, 9]   # sqrt takes exactly 1
["/", 8]         # / takes exactly 2
["@", 1, 2]      # unknown operator

Try combining things you built:

# Evaluate a nested expression
expr = ["*", ["+", 1, 2], ["+", 3, 4]]
print(solve_expression(expr))   # 21

# Flatten the result of some computation
nested = [[1, 2], [3, [4, 5]]]
print(flatten_list(nested))     # [1, 2, 3, 4, 5]

Some array jobs come with a hard constraint: no second array allowed. A billion-element list won't fit in memory twice, so you must rearrange it in place, using only a spare variable or two.

First, meet a new operator. ^ is XOR (exclusive or): for each bit of the two numbers, the result bit is 1 exactly when the input bits differ.

1 ^ 2  ->  3      (01 ^ 10 = 11)
5 ^ 5  ->  0      (a number XOR itself is always 0)
5 ^ 0  ->  5      (XOR with 0 changes nothing)

Write xors(a, b, c) that takes three equal-length lists and returns a new list where element i is a[i] ^ b[i] ^ c[i].

Write reverse_in_place(arr) that reverses the list without creating a new list — no arr[::-1], no reversed(), no second list. Walk two indices toward each other from the ends, swapping as you go. The function should modify arr and return nothing.

Write shift_left(arr) that moves every element one position to the left, with the first element wrapping around to the end — in place, with only one temporary variable: [10, 20, 30] becomes [20, 30, 10].

Shifting left by k could be done by calling shift_left k times — but that is O(n·k). There is a beautiful O(n) trick that uses reversal three times. Watch [1, 2, 3, 4, 5] with k = 2:

1. Reverse the first k elements: [2, 1, 3, 4, 5]
2. Reverse the remaining elements: [2, 1, 5, 4, 3]
3. Reverse the whole array: [3, 4, 5, 1, 2] — done!

Write shift_left_k(arr, k) using this trick. You will want a helper that reverses just the slice between indices i and j in place.