All-pairs node-to-node derivatives: Let y(i) be the variable in node i in a directed acyclic computational graph containing n nodes and m edges. Consider the case where one wants to compute S(i, j) = ∂y(j)

∂y(i) for all pairs of nodes in a computational graph, so that at least one directed path exists from node i to node j. Propose an algorithm for all-pairs derivative computation that requires at most O(n2m) time. [Hint: The pathwise aggregation lemma is helpful. First compute S(i, j, t), which is the portion of S(i, j) in the lemma belonging to paths of length exactly t. How can S(i, k, t + 1)

be expressed in terms of the different S(i, j, t)?]