HW4 Solution

1.

There are 5 rounds. The Bellman-Ford algorithm returns FALSE, there is a negative-weight-cycle: càdàaàsàc with total weight of -8. The following graph shows the result after the 5th round:

2.

3.

Solution 1:

Solution 2:

4.

D(0):

/ a / b / c / d / e / s
a / 0 / -5 / / / 13 / 8
b / / 0 / / / 2 /
c / / -26 / 0 / -25 / 4 /
d / -1 / -9 / / 0 / /
e / / / / / 0 /
s / / / 10 / 17 / / 0

The final round:

D(6) :

/ a / b / c / d / e / s
a / -8 / -16 / -18 / -7 / -14 / 0
b / / 0 / / / 2 /
c / -34 / -42 / -8 / -33 / -40 / -26
d / -9 / -17 / 17 / -8 / -15 / -1
e / / / / / 0 /
s / -24 / -32 / 2 / -23 / -30 / -16

5. (Pesudocode is from Chun-Yin Liu)

Since the graph is sparse, |E| = O(|V|), and the DFS_VISIT runs in time O(V+E), so DFS_VISIT will run in time O(V). The DFS (developing Transitive Closure of G) will run in time O(V), and there are T times hashing operations, so total preprocessing time will be O(V + T). The space will be proportional to T, since there are T entries in hashtable. In average case, the reachability query to the hashtable takes constant time.

6.

(From Brian Barbosa)

The underlying graph in the ad hoc wireless network must be unweighted, otherwise the logic behind Theorem 3 fails to hold. Theorem 3 relies on the fact that if a connection exists between vi-1 and vi+1, then it is automatically a shorter path than {vi-1, vi, vi+1}. However, in a weighted graph, it’s possible for this to not be true. For instance, if we had the following:

{vi-1, vi} = 1

{vi, vi+1} = 1

{vi-1, vi+1} = 3

In this case, using the non-gateway node would make a shorter path, so the Theorem would fail. Since this theorem is part of the basis of the algorithm, the entire argument for the algorithm would fall down without it.

7. The maximum flow from s to t is 11.

8. Yes, The Bellman-Ford algorithm can be used to find an augment path in G.

(From SUGANTHI MANICKAM)

9.

10.