(W5) Greedy Algorithms

Question 1

Greedy Algorithm Theory (what is it?)

What is the consequence

Answer 1

Make a locally optimized choice at each stage and commit to it

This means, that without correctness proofs, often custom algorithms don’t find the most optimized solution

Question 2

Dijkstras Overview

Answer 2

Closely related to BFS, solves the single source all targets shortest path on graphs with non-negative weights

Question 3

Dijkstras Algorithm

Answer 3

Create a queue, sort by smallest distance (this is where the log n comes in)

For each vertex (from the queue, smallest distance)
For each outgoing edge:
if the end node is not in the distances array
add it to the queue with the weight start.distance + edge.weight
else if end.distance > start.distance + edge.weight
update the distance
mark it as visited

the distances array will then have the shortest distance

Question 4

Why can’t you have negative edge weights in with Dijkstras?

Answer 4

Because once Dijkstra pops a node off the queue, it isn’t going to revisit it

However, if negative edge weights are being used - then it’s possible that a better solution will be found.

Question 5

What is the complexity of Dijkstras?

Answer 5

θ(E * Q.update + V * Q.extract_min)

Which with a priority queue turns into θ(E * log V + V * log V) -> θ(E * log V)

Question 6

What is a Tree? (In graphs)

Answer 6

Connected unidirected graph with no cycles in it

Question 7

Spanning Tree

Answer 7

Tree that spans G (includes every vertex) and is a subgraph of G (every edge in the spanning tree belongs to G)

Question 8

Minimum Spanning Tree

Answer 8

Is a spanning tree whose weight is minimum over all possible spanning trees in the graph

Question 9

Prims Algorithm

Answer 9

Slight modification to Dijkstras

• But instead of recording in the min_queue the distance from source to that node, you record the edge weight from a node to that node
• That way you are always selecting the shortest edge to add to the min tre

Question 10

What is the complexity of Prims?

Answer 10

Same as Dijkstras - θ(E * log V)

Question 11

Kruskals Algorithm

Answer 11

Sort all the edges by weight (smallest first)

Start with each node in it’s own seperate tree

For each edge (in sorted order)
if start and end are in different trees, then add edge to the MST
if start and end are in the same tree, then skip the edge (as this would form a cycle)