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

a) Explain (step by step) how the Bellman-Ford algorithm can be used to solve the following difference constraints: \[ \begin{array}{l} x_{1}-x_{2} \leq 7 \\ x_{2}-x_{3} \leq-3 \\ x_{1}-x_{3} \leq 4 . \end{array} \] ) 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: \[ \begin{array}{ll} A:\{p, q, r\} & p:\{A, B, C\} \\ B:\{r, y\} & q:\{C\} \\ C:\{q, r\} & r:\{C, D\} \\ & y:\{A, B\} \end{array} \] 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.