# 9 Sep, 2021

You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.

### In-class Quiz Questions

📝

We discussed the Bellman-Ford algorithm for detecting negative-cycles and Floyd-Warshall for dealing with APSP in this class.

1. If theres is a tense edge after N-1 iterations of Bellman Ford, then we can say that:
1. there is a negative weight cycle for sure
2. there is a negative weight edge for sure, but there may not be a negative weight cycle
3. it's possible that all edge weights are positive

there is a negative weight cycle for sure

Please see the lecture for a detailed explanation.

2. If d(u,v,r) is as defined, and the path witnessing this value does NOT use the vertex labeled r, then d(u,v,r) is the same as:
1. d(u,v,r+1)
2. d(u,v,r-1)
3. d(u,v,1)
4. None of the above

d(u,v,r-1)

If the vertex r is not even used, the answer is the same as d(u,v,r-1).

3. If d(u,v,r) is as defined, and the path witnessing this value does use the vertex labeled r, then d(u,v,r) is the same as:
1. d(u,r,r-1) + d(r,v,r-1)
2. d(r,u,r-1) + d(v,r,r-1)
3. d(r,u,r+1) + d(v,r,r+1)
4. d(u,r,r+1) + d(r,v,r+1)
5. None of the above