Courses βΈ± Algorithms
You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.
Lecture Recording
In-class Quiz Questions
We discussed the Bellman-Ford algorithm for detecting negative-cycles and Floyd-Warshall for dealing with APSP in this class.
- If theres is a tense edge after N-1 iterations of Bellman Ford, then we can say that:
- there is a negative weight cycle for sure
- there is a negative weight edge for sure, but there may not be a negative weight cycle
- it's possible that all edge weights are positive
Reveal answer
there is a negative weight cycle for sure
Please see the lecture for a detailed explanation.
- 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:
- d(u,v,r+1)
- d(u,v,r-1)
- d(u,v,1)
- None of the above
Reveal answer
d(u,v,r-1)
If the vertex r is not even used, the answer is the same as d(u,v,r-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:
- d(u,r,r-1) + d(r,v,r-1)
- d(r,u,r-1) + d(v,r,r-1)
- d(r,u,r+1) + d(v,r,r+1)
- d(u,r,r+1) + d(r,v,r+1)
- None of the above
Reveal answer
d(u,r,r-1) + d(r,v,r-1)
Find the best way of getting from u β r and then from r β v and combine these to get a path from u β v. Note that vertices don't repeat if there are no negative cycles!
Β