121 Week 19 - Greedy ALgorithms Flashcards
Algorithmic paradigm
the way in which an algorithm approaches solving a problem.
E.g., recursion, divide and conquer, sweep-line, greedy.
Greedy algorithm
A way of solving problems in stages by choosing the locally optimal choice.
Means that it is a fast algorithm but can give incorrect or non-optimal solutions as it does not look at the whole problem.
Greedy algorithms can find optimal solution to some problems very quickly. E.g., travelling salesman problem.
Travelling salesman problem
Travelling salesman wants to travel to a set of cities (nodes) but needs to find the most efficient way to go to each city which minimises distance (edge weights) without visiting the same city twice and returning to the origin node.
A greedy algorithm solves this by only comparing the distance (edge weights) of nodes it can reach in 1 travel. It may not find the shortest path but it would be a good enough route.
Greedy algorithm for finding shortest paths
Start at the source node, and visit in each stage, the (yet) unvisited node which is closest to the source – Dijkstra’s algorithm.
Greedy algorithm for vertex 3-coloring
3-coloring (ring) graphs: given an undirected ring graph, assign a colour in {1,2,3} to all nodes such that no two neighbours have the same colour.
Greedy algorithms solve this by iterating through the nodes in the graph and for each node, it iterates through the array of colours, {1,2,3}, until it gets to one that no neighbour has already chosen.
Greedy algorithm for vertex 2-coloring
2-coloring (ring) graphs: given an undirected ring graph, assign a colour in {1,2} to all nodes such that no two neighbours have the same colour.
Greedy algorithms solve this by iterating through the nodes in the graph and for each node, it iterates through the array of colours, {1,2}, until it gets to one that no neighbour has already chosen.
Greedy algorithms will always fail 2-colouring odd-numbered ring graphs but can also fail on even-numbered graphs even though there is always a way to complete it.
Shows that even if there is a solution, a greedy algorithm may not always find it.
Greedy algorithm for maximal independent set
Maximal Independent Set (MIS): find a subset I of an undirected graph G where each node in I are not neighbours but all nodes from G that are not in I were neighbours of the node in I.
Greedy algorithm solves this by creating an empty graph I then iterating through every node in G. For each node in G it checks if the node has any neighbours in I, if it doesn’t, it adds the node to I.
Greedy algorithms will always output a correct solution.
Greedy algorithm for maximum independent set
Similar to maximal but it finds the largest subset of nodes I from a graph G that are not neighbours but all nodes in G are a neighbour of a node in I.
Greedy algorithms use the exact same method to find a solution.
Greedy algorithms do not always find a correct solution as there may exists a solution with a larger subset.
Greedy algorithms for minimum-weight spanning trees (MST)
Minimum-weight spanning tree (MST) problem: Given an undirected weighted graph G, compute the spanning tree with minimum total edge weights.
There are 2 greedy approaches to solving the MST problem - Kruskal’s algorithm and Prim’s algorithm.
Kruskal’s algorithm for minimum-weight spanning trees (MST)
Create an empty tree T.
Sort edges from lowest to highest weight.
Go through each edge in the sorted order and if it does not form a cycle when added to T, add it to T.
Kruskal’s algorithm time complexity
Worst case time complexity: O(E logV) where E is number of edges and V is number or vertices.
Prim’s algorithm for minimum-weight spanning trees (MST)
- Start with a list of vertices and edges. Vertices contains the first node and edges is empty.
- Visit the first node and compare the edge weights of its neighbours. Go to the node with smallest edge weight and add it to the list of vertices.
- Look at all edges coming from any node in the list of vertices. Find the smallest edge that is not in the list of edges and go to the node it connects to. Add this node to the list of vertices.
- Repeat step 3 until the list of vertices contains all nodes in the graph.
Prim’s algorithm time complexity
If Prim’s algorithm is implemented in the easiest way, its worst case time complexity is : O(E + V logV) where E is number of edges and V is number or vertices.
If Prim’s algorithm is implemented in the best way, its worst case time complexity is : O(|V|2) or O(E logV) where E is number of edges and V is number or vertices.
