Greedy algorithms

An optimization problem is one in which you want to find, not just a solution, but the best solution
A “greedy algorithm” sometimes works well for optimization problems
A greedy algorithm works in phases: At each phase:
- You take the best you can get right now, without regard for future consequences
- You hope that by choosing a local optimum at each step, you will end up at a global optimum

Example: Counting money

Suppose you want to count out a certain amount of money, using the fewest possible bills and coins
A greedy algorithm would do this would be:
At each step, take the largest possible bill or coin that does not overshoot
Example: To make $6.39, you can choose:

a $5 bill
a $1 bill, to make $6
a 25¢ coin, to make $6.25
a 10¢ coin, to make $6.35
four 1¢ coins, to make $6.39
For US money, the greedy algorithm always gives the optimum solution

Doesn't always work.

In some (fictional) monetary system, “krons” come in 1 kron, 7 kron, and 10 kron coins
Using a greedy algorithm to count out 15 krons, you would get

A 10 kron piece
Five 1 kron pieces, for a total of 15 krons
This requires six coins
A better solution would be to use two 7 kron pieces and one 1 kron piece
This only requires three coins
The greedy algorithm results in a solution, but not in an optimal solution

Spaning Trees

Suppose you own a telecom company and you're looking to lay cable in a new neighborhood. ...

A spanning tree T of a connected graph $G = (V,E)$ is a
subgraph of $G$ that is:

connected
acyclic
includes all of V as vertices.

The minimum spanning tree (MST) problem:
Suppose that we have a connected, undirected graph $G=(V,E)$ , with a numerical weighting $w(u,v)$ for each edge $(u,v)$ .
Problem: Find an acyclic subset $T \subseteq E$ that connects all of the vertices in $V$ , and minimizes:
$\Sigma \{w(u,v) | (u,v) \in T\}$
Solution: We will look for an algorithm of the form:
$E_T \leftarrow$ empty set of edges
while ( $E_T$ is not a spanning tree)
- add an edge to $E_T$
At each stage we will ensure that $E_T$ is a subset of a MST

If $e$ is a minimum-weight edge in a connected
graph, then $e$ must be an edge in at least one
minimum spanning tree

True or False?

Must $e$ be an edge in all minimum
spanning trees of the graph?

If every edge in a connected graph $G$ has a
distinct weight, then $G$ must have exactly one
minimum spanning tree?

Proof
Assume the contrary, that there are two different MSTs $A$ and $B$ .

Since $A$ and $B$ differ despite containing the same nodes, there is at least one edge that belongs to one but not the other. Among such edges, let $e1$ be the one with least weight; this choice is unique because the edge weights are all distinct. Without loss of generality, assume $e1$ is in $A$ .
As $B$ is an MST, $e1 \cup B$ must contain a cycle $C$ with $e1$ .
As a tree, $A$ contains no cycles, therefore $C$ must have an edge $e2$ that is not in $A$ .
Since $e1$ was chosen as the unique lowest-weight edge among those belonging to exactly one of $A$ and $B$ , the weight of $e2$ must be greater than the weight of $e1$ .
As $e1$ and $e2$ are part of the cycle $C$ , replacing $e2$ with $e1$ in $B$ therefore yields a spanning tree with a smaller weight.
This contradicts the assumption that $B$ is a MST.

Prim's Algorithm

Idea: Construct a MST by greedily expanding an initial tree, composed of just a single vertex of the graph's vertices. To expand the tree, attach the nearest vertex, i.e. add the vertex connected by the lowest weight edge amongst the neighbors of the current expanding tree such that we don't create a cycle.

Pseudocode:
Input: A weighted connected graph $G = (V,E)$
Output: $E_r$ the set of edges composing a minimum spanning tree of G.

Prim(G):
$V_r \leftarrow {v_0}$
$E_r \leftarrow \varnothing$
for $i \leftarrow 1$ to $|V|- 1$ do:
- find a minimum-weight edge $e^* = (v^*, u^*)$ among all the edges $(v, u)$ such that $v$ is in $V_r$ and $u$ is in $V - V_r$
- $V_r \leftarrow V_r \cup \{u^*\}$
- $E_r \leftarrow E_r \cup \{e^*\}$
return $E_r$

Let's try two examples

A bit more detail:

The input is the graph G=(V, E), and a root r \in V.
for each v in V
  key[v] ← ∞;
  parent[v] ← null;
key[r] ← 0;
add all vertices in V to the queue Q.
while (Q is nonempty) {
  u ← extractMin(Q);
  for each vertex v that is adjacent to u {
    if v ∈ Q and weight(u,v) < key[v] {
      parent[v] ← u;
      key[v] ← weight(u,v);
    }
  }
}

Ideas: Store all vertices that are not in ( $V_T, E_T$ ) in a priority queue Q with an extractMin operation.
If u is a vertex in Q, what’s key[u] (the value that determines u’s position in Q)?
- key[u] = minimum weight of edge from u into $V_T$
- If no such edge exists, key[u] = ∞.
- We maintain information about the parent (in ( $V_T, E_T$ )) of each vertex v in an array parent[].
- $E_T$ is kept implicitly as {(v, parent[v]) | v ∈ V−Q−{r}}.

Assuming a binary heap:

Initialization takes O(|V|) time.
Main loop is executed |V| times, and each extractMin takes O(log |V|).
The body of the inner loop is executed a total of O(|E|) times; each adjustment of the queue takes O(log |V|) time.
Overall complexity: O((|V|+|E|) log |V|) = O(|E| log |V|).

Kruskal's Algorithm

Idea: create a forest F (a set of trees), where each vertex in the graph is a separate tree
create a set S containing all edges in the graph
while S is not empty ad F is not yet spanning:
-remove and edge with minimum weight from S
-if the removed edge connects to different trees, then add it to F, combining two trees into a single tree
At the termination of the algorithm, the forest forms a minimum spanning tree of the graph.

Pseudocode using the union find data structure:

Kruskal(G):
  A = null
  for each v in V:
    MakeSet(v)
  for each (u, v) in E, sorted by weight from smallest to largest:
    if FindSet(u) != FindSet(v):
      A = A union {(u, v)}
      Union(u, v)
  return A

Union Find (disjoint set) data structure
The operations we need are:

Make a singleton set;
Test if two sets are equal;
Union two sets together.

Complexity:
Sorting the edges costs O(E log E)
The union find data structure can perform O(V) operations in O(V log V) time.

A sophisticated union find data structure can run in $\mathcal{O}(\alpha (V))$ time.
Combined with a linear time sorting algorithm, we could achieve $\mathcal{O}(E \alpha(V))$ run time.

Shortest path - Dijkstra’s Algorithm

Dijkstra’s finds the lowest cost path from source node and a destination node in a weighted graph.

Input: A source node s and destination node d, Graph G =
(V, E) with edge weights {W[e] | e in E}
Output: the path weight from s to d

for i <- V.length
  dist[i] <- infinity
  previous[i] <- nil
dist[s] <- 0

H <- minHeap(V) // using the values in dist as keys
while H is not empty
  u <- deleteMin(H)
  for all edges (u, v) in E
    if dist[v] > dist[u] + E[u,v]
      dist[v] <- dist[u] + E[u,v]
      previous[v] <- u
      update H

Other algorithms you should consider studying:

Proababilistic/Random Algorithms:
Random pivot selection for Quicksort
Bloom Filter - space-efficient probabilistic data structure
Skip List

Hashing
Cuckoo hashing
Universal hashing