(a) Explain (step by step) how the Bellman-Ford algorithm can be used to solve the following

difference constraints:

x1 x2 7

x2 x3 3

x1 x3 4.

(b) The longest path in a graph can be computed by negating the costs of all edges in the graph and then running the Floyd-Warshall algorithm.

True or False? Explain: If it is True then give a proof. If it is False, then give a counterexample and explain what the algorithm returns.

(c) Suppose that there are 3 students, {A, B, C}, and 4 graduation projects, {p, q, r, y}. Each student specifies a set of projects they would like to work on, and each supervisor of the project specifies a set of students whom they would like to work with:

A : {p,q,r}

B : {r,y}

C : {q,r}

p : {A,B,C}

q : {C} r : {C,D} y : {A, B}

Explain (step by step) how the Ford-Fulkerson algorithm can be used to assign projects to the maximum number of students, such that the following two conditions hold: there is no student matched to two different projects, and there is no project assigned to two different students.