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 PDF
2 April 2 PDF
3 April 19 PDF
4 April 30 May 4 PDF
5 May 21 PDF
6 June 11 PDF
7 June 28 June 29 PDF

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License