Problem B {1 pt, this is related to CLRS Problem 24.2-3 on page 657) Suppose you are given an acyclic directed graph G that represents a combinational circuit C, where 0 Each node is a sub-circuit (e.g., AND gate, OR gate, NOT gate, 2:1 multiplexer, 4:1 demultiplexer, 4-bit adder, etc) Directed edges are wires Each node u has a nonnegative weight w(u) that is the propagation delay of sub-circuit u Each edge {u,v) has a nonnegative weight w(u,v) that is the propagation delay ofthe edge The input wires have propagation delay 0 The output wires have propagation delay 0 Note that circuit C will have inputs and outputs. As shown in the figure below, the inputs are at sub-circuits we will refer to as ingress sub-circuits, and the outputs are at sub-circuits we will refer to as egress sub-circuits. Similarly, nodes in G that correspond to ingress sub-circuits will be referred to as ingress nodes, and node that correspond to egress sub- circuits will be referred to as egress nodes. lngress nodes Egress nodes '2,- 2?. As shown below, add new nodes 5 and t to G. Then add directed edges from node 5 to each ingress node, and node t has directed edges from each egress node. These new nodes and edges have zero propagation delay. lngress nodes Egress nodes We define the weight of a path from s to t to be the sum of the weights (propagation delays) of the vertices and edges along the path. Note that the maximum weighted path is the critical path of the circuit, i.e., the path that dictates the overall propagation delay of the circuit. Now let's develop a critical path finding algorithm which consists of two steps. Step 1: Define new edge weights w' with the following property. Consider an arbitrary path p from 5 tot. Let L be the length of path p under the node and edge weights w. Then the length of path p under the edge weights w' is L too (Note w' doesn't have node weights). What is the weight w'(u,v) for the edge (u,v)? What is the time complexity to compute edge weights w'? Step 2. We will use the Dag-Shortest-Paths (CLRS pg 655) to a path from s to t. Note that the the path is a shortest path. Do we use edge weights w' or another edge weights? If we use another edge weights, define that weight w*(u,v) for all edges (u,v). What is the time complexity to accomplish Steps 1 and 2