Exercises

Table of Contents

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$.