16 Greedy vs DP Flashcards
How is dynamic programming and greedy algorithms in common?
Both solve optimization problems that require making a sequence of choices.
Greedy algorithms are usually ____ than DP solutions.
More efficient
Greedy Algorithm
Makes a squence of decisions. For each decision:
- takes the decision that looks best right now, without regard for future consequences.
Greedy algorithms have the advantage of :
Being simple and fast.
Spanning tree
An undirected graph G = (V,E) is a subgraph of G that is a tree and contains all the vertices of G.
Minimum spanning tree
A subgraph of an undirected wieghted graph such that
- its a tree (acyclic graph)
- covers all the vertices (contains V-1 edges)
- total cost associated with tree edges is the minimum among all possible spanning trees.
Two greedy algorithsm with the same asymptotic complexity:
Kruskal’s and Prim’s algorithm.
Prim’s algorithm
For finding an minimum spanning tree
Is a greedy algorithm.
Prim’s Algorithm time complexity using binary heap
O(V log V) + O(E log V)
Prim’s Algorithm time complexity using an array
O(V^2) + O(E) == O(V^2)
Prim’s Algorithm time complexity using a heap
O(E lg V)
Sparse Graph: E is approximately V, so O(V log V)
Dense Graph E is approximately V^2, so O(V^2 log V)
Prim’s Algorithm is only for :
Undirected Graphs (That are also connected and weighted)
Spanning Tree
For an undirected graph G = (V,E) is a subgraph of G that is a tree and contains all the vertices of G
Weight of a subgraph
The sum of the weights of the edges.
Minimum Spanning Tree
A subgraph of an undirected weighted graph such that
- it is a tree (acyclic)
- it covers all vertices (contains V-1 edges)
- the total cost associated with tree edges is the minimum among all possible spanning tree.
- Note that is it not necessarily unique (it is only unique if the original graph G is a tree).
