Solve the following coding problems. ### 1. Implement a differentiable matrix product You are given a list of `k` square matrices `M1, M2, ..., Mk`, all of shape `n x n`. 1. Implement an in-place routine that computes `M1 @ M2 @ ... @ Mk` while reusing intermediate buffers. 2. Explain why this in-place approach is unsafe for automatic differentiation in a framework with PyTorch-like autograd. 3. Implement an out-of-place version that is compatible with backpropagation. 4. Derive the backward pass manually: given the upstream gradient of the final product, compute the gradient with respect to each input matrix. 5. Re-express both the forward and backward computations using an associative parallel scan similar to the Hillis-Steele prefix-scan. ### 2. Generate a balanced ordering of tagged tasks You have three finite tag sets: `A`, `H`, and `T`. Each task is a triple `(a, h, t)` from the Cartesian product `A x H x T`. Output an ordering of all triples exactly once. For any prefix of the output sequence, define the imbalance of a family of pair buckets as: `max_bucket_count - min_bucket_count` where bucket counts are computed over all pair types in that family. 1. First, construct an ordering whose prefixes keep the `(a, h)` pair counts as balanced as possible. 2. Then strengthen the requirement so that prefixes keep both `(a, h)` and `(a, t)` pair counts as balanced as possible at the same time. 3. Describe or implement a brute-force or greedy algorithm that repeatedly chooses the next unused triple that best improves the current balance. No strict complexity target is required. ### 3. Compute numerically stable streaming entropy Given logits `z = [z1, z2, ..., zn]`, let `p = softmax(z)`. 1. Implement a numerically stable function to compute the entropy `H(p) = -sum_i p_i log p_i`. 2. Rewrite the expression so it can be computed directly from the logits using a log-sum-exp style normalization. 3. Now support a streaming setting where logits arrive one at a time. After each new logit is appended, update the entropy efficiently without recomputing from scratch. 4. Specify which running statistics must be maintained, including how to update them when the current maximum logit changes.