1.4 ?

This technique is called memoization4. Here is our memoized algorithm: COST(node) if node is end then return 0 if node has no children then return infinity // Now we compute a set of values-one value for each child of node: foreach child of node do if child is end then just compute WEIGHT(node, child) else if Cost(child) has not already been computed then compute Cost(child) and enter it in the lookup table compute WEIGHT(node, child) + LOOKUP-COST(child) return the minimum of those computed values 1.4 Exercise Show that the cost of the memoized algorithm is O(IV| + |E), where as usual V is the set of vertices in the DAG and E is the set of edges