Text:

2.(10p). We shall now consider directed graphs, where each edge has a weight (a positive integer). The algorithm below takes as input a directed graph G with nodes 1..n and with a edges, and computes a boolean array S such that for each i 1..n, S[i] is the sum of the weights of the edges that have i as target.

AddIncoming(G) for i 1 to n

S[i] 0 for k 1 to n

edges G.allFrom(k) foreach e edges

i the target of e w the weight of e S[i] S[i] + w

Your task is to find the (worst-case) running time of this algorithm, expressed in the form (f(n,a)) with f as simple as possible, for each of the graph representations listed below:

1. G is represented by an adjacency matrix.

2. G is represented by adjacency lists.

2. (10p). We shall now consider directed graphs, where each edge has a weight (a positive integer). The algorithm below takes as input a directed graph G with nodes 1..n and with a edges, and computes a boolean array S such that for each i E 1..n, S[i] is the sum of the weights of the edges that have i as target. ADDINCOMING(G) for i = 1 to n s[i] - 0 for k = 1 to n edges - G.ALLFROM(k) foreach e E edges i - the target of e w - the weight of e s[i] + S[i] + w Your task is to find the (worst-case) running time of this algorithm, expressed in the form O(f(n, a)) with f as simple as possible, for each of the graph representations listed below: 1. G is represented by an adjacency matrix. 2. G is represented by adjacency lists. 2. (10p). We shall now consider directed graphs, where each edge has a weight (a positive integer). The algorithm below takes as input a directed graph G with nodes 1..n and with a edges, and computes a boolean array S such that for each i E 1..n, S[i] is the sum of the weights of the edges that have i as target. ADDINCOMING(G) for i = 1 to n s[i] - 0 for k = 1 to n edges - G.ALLFROM(k) foreach e E edges i - the target of e w - the weight of e s[i] + S[i] + w Your task is to find the (worst-case) running time of this algorithm, expressed in the form O(f(n, a)) with f as simple as possible, for each of the graph representations listed below: 1. G is represented by an adjacency matrix. 2. G is represented by adjacency lists