26 Aug, 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.~~ We will do the Itempool questions properly in the next class, since we ran out of time today :)

🍕

Food for thought: can you come up with an algorithm to find simple paths with the lowest total cost even if some edge weights are negative? Hint: What if you took a simple, undirected, unweighted graph, and assigned every edge a weight of ? What would a simple shortest path in such a graph correspond to? Can you relate this to some other (possibly hard) problem that you have seen before?

Lecture Recording

In-class Quiz Questions

📝

We wrapped up the discussion on DSU (the last implementation involving direct leader information in an array + a linked list threading all elements of a set) and we spent some time introducing shortest paths.

Suppose you have a graph with edge weights. Can you use breadth-first search to determine distances between vertices?

Yes, as long as all edge weights are positive.
Yes, even with negative edge weights.
No, even if all edge weights are positive.

Reveal answer

✅

No - BFS cannot accurately determine distances even if all edge weights are positive.

Consider the graph on vertices a, b, c, with edges (a,b), (b,c) and (a,c); with the following edge weights:

w((a,b)) = 3

w((a,c)) = 1

w((c,b)) = 1

Then the distance between a and b is 2, given by the path a - c - b; but a BFS starting from a will pull both b and c in the first layer and think of the direct edge between a to b as being the shortest path; even though it's cost is 3, and 3 > 2.

Definitions (from slides)