A greedy algorithm arrives at a solution by making a sequence of choices, each of which simply looks the best at the moment. The hope is that locally-optimal choices will lead to a globally-optimal solution.

Making Change

def MakingChange(x):
    Coins = {5, 10, 25, 100, 200}
    Sum = 0
    while Sum != x:
        Let c in Coins be the largest denomination such that Sum + c <= x
        if there is no such denomination:
            return "No Solution"
        Add c to the change that will be returned
        Sum = Sum + c

The 0, 1 - Knapsack Problem

Find a greedy algorithm to solve the following problem.

input:

• $n$ objects such that object $i$ (1 \leq i \leq n) has a positive value $v_i$ and a positive weight $w_i$.
• A maximum weight $W$.

output: A vector $X = (x_1, x_2, ..., x_n)$ such that

• $0 \leq x_i \leq 1$
• The total value $x_1v_1+x_2v_2+ ... + x_nv_n$ is maximized.
• The total weight is not too heavy: $x_1w_1 + x_2w_2 + ... + x_nw_n \leq W$.

Lemma

If the objects are selected in order of decreasing $\frac{v_i}{w_i}$, then the greedy choice finds an optimal solution.

Algorithm

1. Compute all the $\frac{v_i}{w_i}$
2. Sort the objects in decreasing order of $\frac{v_i}{w_i}$ (use MergeSort)
3. Build the solution by applying the greedy choice with respect to decreasing order of $\frac{v_i}{w_i}$.

Total time: $O(n log(n))$

Minimum Spanning Tree

We are given edge $G = (V, E)$ that is undirected and connected. Each edge ${u, v} \in E$ has a weight $wt (u, v)$.

We want a compute a subgraph $G' of G$ such that:

• The vertex set of $G' is V$,
• $G'$ is connected,
• and $weight(G')$ is minimum, where
  • $weight(G')$ = sum of weights of edges in $G'$.

$G'$ is called a Minimum Spanning Tree of G (MST of G).

Lemma

Let $G = (V, E)$ be an undirected and connected graph, where each edge ${u,v} \in E$ has a weight $wt(u,v)$.

Split $V$ into $A$ and $B$. Let ${u,v} \in E$ be a shortest edge connecting $A$ and $B$. then there is an MST of $G$ that contains ${u,v}$.

From the previous lemma, any algorithm that follows this greedy scheme is guaranteed to work:

1. X = {}
2. Repeat until $|X| = |V| - 1$
   • Pick a set $S$ such that $X$ has no edge between $S$ and $V/S$.
   • Let $e \in E$ be a minimum-weight edge between $S$ and $V/S$.
   • $X = X \cup {e}$

Union-Find Data Structure

Before presenting a first algorithm to compute an MST, we first open a parenthesis and study a data structure called Union-find.

Given $n$ sets, each of size one, process a sequence of operation, where each operation is one of:

def union (A,B,C):
    Set C = A U B
    A = {}
    B = {}
def find (x):
    Return the name of the set that contains x

The sequence consists of $n-1$ Union operations, $m$ Find operations. This can be done in any arbitrary order.

We store each set in a list:

• the list has a pointer to the head and a pointer to the tail
• the first node stores the name of the set and the size of the set
• each other node stores one element of the set
• each node $u$ stores two pointers:
  • next($u$) the next node in the list
  • back($u$) first node in the list

For the Union Function:

• if size of set $A$ is larger than $B$, append $B$ to $A$. Otherwise append $A$ to $B$.
• running time $O(\mathrm{min}{|A|,|B|}$

For the Find function:

• follow the back pointed from the node storing $x$ to the head of the list and return the name stored at the head.
• $O(1)$

Total running time:

• $n-1$ Union operations = $O (n \log{n})
• Any sequence of $n-1$ Union operations and $m$ Find operations takes $O(m + n \log{n})$

Kruskal Algorithm

• Approach: Maintain a forest. In each step, add an edge of minimum weight that does not create a cycle.
• Start: At the beginning, each vertex is a (trivial) tree.
• One Iteration: Combine two trees using an edge of minimum weight

# Input: G = (V,E), where V = {x1, x2, ..., xn} and m = |E|
# Output: A minimum spanning tree of G
def Kruskal(G):
    Sort the edges of E by weight using Merge Sort
    for i in range(n):
        V[i] = x[i]
    T = {}
    for k in range(m):
        Let u[k] and v[k] be the vertices of e[k]
        Let i be the index such that u[k] is in V[i]
        Let j be the index such that v[k] is in V[j]
        if (i != j):
            V[i] = Vi[i] union V[j]
            V[j] = {}
            T = T union {{u[k], v[k]}}
    return T

Running time

• Sorting: $O(m \log{m})$
• First loop: $O(n)$ time
• Second for loop:
  • Store $T$ in a linked list Total time to maintain this list: $O(n)$ time
  • Store the sets $V_i$ using the Union-Find data structure
  • In this second For-Loop, we do
    • $2m$ Find operations
    • $n-1$ Union operations
  • So in total for the second for loop: $O(n) + O(m + n \log{n})$
• Total running time is $O(m \log{n})$

Prim Algorithm

Start:

• $A$ is a set consisting of one (arbitrary) vertex of $V$
• $T$ is an empty set of edges.
• $Q = V/A$

One Iteration:

• Take an edge ${u, v}$ of minimum weight such that $u \in A$ and $v \in Q$
• Add the edge ${u, v}$ to $T$
• Move $v$ from $Q$ to $A$

Repeat until $A = V$ (i.e. $Q={}$)!

# Input: G = (V,E)
# Output: A minimum spanning tree of G
def Prim(G):
    Let r in V be an arbitrary vertex. 
    A = {r}
    T = {}
    while A != V:
        # Q = V\A
        find an edge {u, v} in E of min weight such that u in A and v in Q
        A = A union {v}
        T = T union {{u,v}}

Finding the edge ${u,v}$ takes $O(|E|)$ time, so total running time is $O(|V| \cdot |E|)$

To improve running time, we can maintain extra information.

For each vertex $y \in Q$, minweight$(y)$: minimum weight of any edge between y and a vertex of $A$. closest$(y)$: vertex $x \in A$ for which $wt(x, y) = \mathrm{minweight}(y)$. Observe that: a shortest edge ${u, v}$ connecting $A$ and $Q$ has weight $min_{y\in Q}{\mathrm{minweight}(y)}$.

Algorithm

# Input: G = (V , E)
# Output: A minimum spanning tree of G
Let r ∈ V be an arbitrary vertex
A = {r}
T = { }
for each vertex y != r:
    minweight(y) = infinity
    closest(y) = nil
for each edge {r, y}:
    minweight(y) = wt(r, y)
    closest(y) = r
Q = V \ {r}
k = 1 # Stores the size of A
while k != n:
    Let v be the vertex of Q for which minweight(v) is minimum
    u = closest(v)
    A = A ∪ {v}
    Q = Q \ {v}
    T = T ∪ {{u, v}}
    k = k + 1
    for each edge {v, y}:
        if y ∈ Q and wt(v, y) < minweight(y):
            minweight(y) = wt(v, y)
            closest(y) = v
return T

• Store the vertices of $Q$ in a min-heap.
• For each vertex $v \in Q$, the key of $v$ is minweight(v).
• Store $T$ in a list.
• With each vertex of $V$, store one bit indicating whether the vertex
• belongs to $A$ or to $Q$.

Running time:

• Up to the while loop: $O(n)$ time (this includes the time to build the heap).
• One iteration of the while-loop:
  • extract min: $O(\log(n))$ time
  • At most $\mathrm{degree(v)}$ many decrease key operations: $O(\mathrm{degree}(v) · \log{n})$ time
• Total time for the while-loop: $O (m \log{n})