2 Sep, 2021

CoursesAlgorithms

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 worked through Dijkstra's algorithm as an adaptation of a natural modification of BFS.

  1. Suppose you have a graph with edge weights. Can you use Dijkstra's algorithm (the default version, where in the implementation edges never re-enter the heap) to determine distances between vertices?
    1. Yes, as long as all edge weights are positive.
    2. Yes, even with negative edge weights.
    3. No, even if all edge weights are positive.
    4. Reveal answer

      Yes, as long as all edge weights are positive.

      You can show the default version of Dijkstra fails with negative edge weights, but a proof of correctness can be obtained under the assumption of positive edge weights.

  2. Compute the sequence of vertices visited by a run of Dijkstra starting at vertex S on the following graph. What is the last vertex visited?
  3. image
    Reveal answer

    B

    Follows from a direct simulation.