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