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!

Β