# 9 Sep, 2021

Courses βΈ± Algorithms
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.
1. 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).
1. 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