Make the best or greedy choice at any given step.

Solves an optimization problem piece-by-piece by making choices that are:

1. Feasible
2. Locally Optimal: Make choices based on less expensive, short-term criteria
3. Irrevocable: Choices cannot be undone!

Why? — Approximations can be wildly faster than precise ones.

Applies to Problems with:

• Optimal Substructures¹1. The optimal solution to the problem contains within it optimal solutions to subproblems.: Optimal solutions have optimal sub-solutions
• Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum.

Overview

Optimal Solutions:

• Always finds the absolute best solution, but sometimes takes too long (e.g., Exhaustive Search).

Approximations:

• Finds a “good enough” solution much faster using heuristics²2. like greedy algorithms.. Sometimes a greedy algorithm guarantees an optimal solution (e.g., MST).

Minimum Spanning Tree

Spanning Tree: A spanning tree of G is a connected acyclic subgraph that has all of G’s vertices.

Minimum Spanning Tree: A weighted version of the above.

• The “minimum” means this is an optimization problem (visit all vertices with minimum cost).
• Satisfies optimal substructure property.

Prim’s

Grow a MST by repeatedly adding the least-cost edge that connects a vertex in a the existing tree to a vertex not in the existing subtree.

ALGORITHM Prim(G)
    // Prim's algorithm for constructing a MST
    // Input: A weighted connected graph G = <V, E>
    // Output: E_T, the set of edges composing a minimum spanning tree of G
    V_T \leftarrow {v_0} // Start with an arbitrary vertex
    E_T \leftarrow empty set
    for i \leftarrow 1 to |V| \text{$-$} 1 do
        find minimum-weight edge e* = (v*, u*) among all edges (v, u)
        such that v is in V_T and u is in V \text{$-$} V_T
        V_T \leftarrow V_T union {u*}
        E_T \leftarrow E_T union {e*}
    return E_T

Analysis — Time complexity is O(|E| \log |V|) if implemented with a min-heap priority queue.

Kruskal’s

Grow a MST by repeatedly adding the last-cost edge that doesn’t introduce a cycle among the edge included so far.

Note — Key Question: How do you determine if its acyclic still?

If the two nodes being connected:

• belong to the same connected component, it’ll generate a cycle!
• don’t belong to the same connected component, it’s safe!

Aside — Union-Find Problem:

This is a requirement for Kruskal’s to find cycles efficiently. We use a disjoint-set data structure that supports MakeSet, Find, and Union.

Example: Union-Find Execution

Let S = \{ 1,2,3,4,5,6 \}

Applying MakeSet() six times, we initialize the structure of a selection of 6 singletons. When we add an edge connecting 1 and 2, we Union(1,2). To check if an edge 2-3 creates a cycle, we check if Find(2) == Find(3). If not, we Union them.

ALGORITHM Kruskal(G)
    // Kruskal's algorithm for constructing a MST
    // Input: A weighted connected graph G = <V, E>
    // Output: E_T, the set of edges composing a minimum spanning tree of G
    Sort E in nondecreasing order of edge weights
    E_T \leftarrow empty set
    Ecounter \leftarrow 0; k \leftarrow 0
    Initialize |V| disjoint subsets for each vertex
    while Ecounter \lt |V| \text{$-$} 1 do
        k \leftarrow k \text{$+$} 1
        e \leftarrow E[k] (which connects u and v)
        if Find(u) \ne Find(v)
            E_T \leftarrow E_T union {e}
            Union(u, v)
            Ecounter \leftarrow Ecounter \text{$+$} 1
    return E_T

Analysis — Sorting is the main thing O(|E| \log |E|). MakeSet O(|V|), Find and Union operations with path compression are nearly constant time. Thus, total time is O(|E| \log |E|).

Single Source Shortest Path Problem

Note — Remember: Do not mismatch this problem with a problem in the last chapter (Floyd’s algortihm). This problem is about one node’s relationship to everyr other node! Floyd’s was about every node!

Problem: Given a weighted connected graph G, find shortest paths for soruce vertex s to each of the other vertices.

Dijkstra’s Algorithm

Actually pretty similar to Prim’s MST.

Among vertices not already in the tree, finds vertex u with the smallest sum.

d_v + w(v,u)

where:

• v: vertex for which shortest path has already been found (on preceding iterations)
• d: length of the shortest path from source to v
• w(v,u): length (weight) of edge between v and u

ALGORITHM Dijkstra(G, s)
    // Dijkstra's algorithm for single-source shortest paths
    // Input: A weighted connected graph G and starting vertex s
    // Output: Shortest distance from s to every other vertex
    Initialize priority queue Q with all vertices
    for each v in V do d[v] \leftarrow infinity
    d[s] \leftarrow 0
    while Q is not empty do
        u \leftarrow ExtractMin(Q)
        for each neighbor v of u do
            if d[u] \text{$+$} w(u, v) \lt d[v]
                d[v] \leftarrow d[u] \text{$+$} w(u, v)
                DecreaseKey(Q, v, d[v])

Analysis — Efficiency: O(|V|^2) for graphs represented by weight matrix and array implementation of priority queue. O(|E| \log |V|) for graphs represented by adj. lists and min-heap. Space complexity is O(|V|).

Aside — A* is an extended version of this.

Note — Aside Notes:

• Doesn’t work for negative weights
• Works on directed and undirected.
• Don’t get it twisted with Prim’s nor Floyd’s! Prim’s doesn’t consider path accumulation, it just looks at raw edge weight.

Coding Problem

Coding: Assignment of bit strings to alphabet characters

Codewords: Bit strings assigned for characters of alphebet.

Two Types of Codes:

• Fixed-length encoding (e.g., ASCII)
• Variable-length encoding (e.g., Morse)

Problem: If the frequencies of the character occurence are know (e.g., Standard American English), what’s the best binary prefix-free code³3. No codeword is a prefix of another codeword. This ensures that the encoded string can be uniquely and instantaneously decoded from left to right.?

Huffman Codes

It’s an optimal prefix code generated by creating a binary tree using the frequency of the character as a weight. We repeatedly merge the two lowest-frequency nodes into a new parent node whose frequency is their sum, continuing until we have a single root. Left edges get ‘0’, right edges get ‘1’.

ALGORITHM Huffman(C)
    // Builds a Huffman tree
    // Input: A set C of n characters and their frequencies
    // Output: A Huffman tree for the characters
    Initialize a priority queue Q with all characters ordered by frequency
    for i \leftarrow 1 to n \text{$-$} 1 do
        Allocate a new node z
        z.left \leftarrow x \leftarrow ExtractMin(Q)
        z.right \leftarrow y \leftarrow ExtractMin(Q)
        z.freq \leftarrow x.freq \text{$+$} y.freq
        Insert(Q, z)
    return ExtractMin(Q) // root of the tree

Analysis — Time complexity is O(n \log n) due to priority queue operations. Space complexity is O(n) to store the tree.