Complete decision tree and gradient descent functions

You are given partially implemented code and must complete key functions. Implement the missing parts with correct logic and reasonable efficiency.

Task A) Decision tree split function (classification)

You are building a binary decision tree classifier for tabular numeric features.

Implement:

1. gini(y) that computes the Gini impurity of labels y (binary labels 0/1).
2. best_split(X, y) that finds the best (feature_index, threshold) to split on.

Definitions/requirements:

• X is an n x d matrix of floats.
• y is length n , values in {0,1} .
• A split is defined by (j, t) meaning:
  • left child: samples with X[i][j] <= t
  • right child: samples with X[i][j] > t
• Choose the split that minimizes weighted Gini impurity :

$G_{split} = \frac{n_L}{n} G(y_L) + \frac{n_R}{n} G(y_R)$

• If a split would produce an empty side, it is invalid.
• Return None if no valid split exists.

Constraints:

• 1 <= n <= 2e4 , 1 <= d <= 50
• Aim for ~ $O(nd \log n)$ or better.

Task B) Single-step gradient descent update (linear regression)

You are fitting linear regression with mean squared error:

$L(w,b) = \frac{1}{n}\sum_{i=1}^n (w^\top x_i + b - y_i)^2$

Implement:

• gd_step(X, y, w, b, lr) that performs one gradient descent update and returns (new_w, new_b) .

Requirements:

• X is n x d , y length n (real-valued).
• w length d , b scalar.
• Use the correct gradients for MSE (include the averaging over n ).
• Must work for n=1 and d=1 .

Notes

• You may assume Python-like pseudocode and basic numeric operations (no need for full training loop).
• Handle edge cases cleanly (constant labels, identical feature values, etc.).