Error description:
CH 5 defines a dependency graph as a directed graph as follows:
Another good example is the dependency graph of a recursive algorithm.
Dependency graphs are directed acyclic graphs. The vertices are all the distinct
recursive subproblems that arise when executing the algorithm on a particular
input. There is an edge from one subproblem to another if evaluating the second
subproblem requires a recursive evaluation of the first.
My understanding (which the example for Fibonacci (Figure 5.4) also supports) is that this definition means that the subproblem (the one being evaluated via recursion) is a predecessor of the subproblem doing the recursive call. In CH 6, we are asked to "recall" the definition, which is paraphrased as follows:
Recall that the dependency graph of a recurrence has a vertex for every recursive subproblem and an edge from one subproblem to another if evaluating the first subproblem requires a recursive evaluation of the second.
CH 6 goes on to say that
Carrying this analogy further, evaluating a recurrence using dynamic programming is the same as evaluating all subproblems in the dependency graph of
the recurrence in reverse topological order—every subproblem is considered
after the subproblems it depends on. Thus, every dynamic programming algorithm is equivalent to a postorder traversal of the dependency graph of its
underlying recurrence!
The definition that the above paragraph appears to rely on seems to be the transpose of the dependency graph as defined in CH 5.
Suggested fix (if any): The problem here is that both definitions being used are locally consistent to the Chapters they belong to (5 and 6). They are not globally consistent. Suppose, we define a dependency graph as one where there is an edge leaving a node and entering another node IFF the first node's solution is needed to evaluate the second node (CH 5), then the topological order needed for DP will be a forward topological order. Suppose, we instead define the dependency graph as defined in CH 6, then the topological sort needed for DP will be a reverse topological order.
Chapter number or note title: CH 5, CH 6
Page number: P193, P234
Error description: CH 5 defines a dependency graph as a directed graph as follows:
My understanding (which the example for Fibonacci (Figure 5.4) also supports) is that this definition means that the subproblem (the one being evaluated via recursion) is a predecessor of the subproblem doing the recursive call. In CH 6, we are asked to "recall" the definition, which is paraphrased as follows:
CH 6 goes on to say that
The definition that the above paragraph appears to rely on seems to be the transpose of the dependency graph as defined in CH 5.
Suggested fix (if any): The problem here is that both definitions being used are locally consistent to the Chapters they belong to (5 and 6). They are not globally consistent. Suppose, we define a dependency graph as one where there is an edge leaving a node and entering another node IFF the first node's solution is needed to evaluate the second node (CH 5), then the topological order needed for DP will be a forward topological order. Suppose, we instead define the dependency graph as defined in CH 6, then the topological sort needed for DP will be a reverse topological order.