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.

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.

  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
    4. Reveal answer
      βœ…

      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
    5. 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).

  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
    6. 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!