Exercises

Exercises should be submitted in recitation or to Danny's or Rani's mailbox on Schreiber's 2nd floor.

Number Due Exercise
1 March 1922
2 April 2
3 April 19
4 April 30 May 4
5 May 21
6 June 11
7 June 28 June 29

## Clarifications

### Exercise 2, question 4

The vertices have integer labels, in respect to which the minimum is taken. That is, if $R(v) = \{2,4,10,11\}$ then $\rho(v) = 2$.

### Exercise 5, question 4

If all paths $P: s \leadsto v$ have positive $\varphi$ value but there is a cycle $C: s\leadsto v \to s$ with $0 < \varphi(C) < 1$, we will say that $\varphi(v) = 0$.
This is analogous to the case $d[v] = -\infty$ in the presence of a negative cycle in the standard shortest paths problem.

### Exercise 5, question 5

$J_i$ in the footnote was a typo. It should have been $M_i$.