Advanced Topics: Huffman Coding & Matrix Chain Multiplication

Key Concepts & Definitions

1. Huffman Coding: Optimal Prefix-Free Compression

Core Idea

Huffman coding is a greedy algorithm that assigns variable-length codes to input characters based on their frequency, ensuring the most frequent characters get the shortest codes. It guarantees the minimum expected code length for a given set of frequencies.

How It Works

1. Build a Binary Tree:
   • Start with a leaf node for each character, labeled with its frequency.
   • Repeatedly combine the two least frequent nodes into a new internal node (sum of their frequencies) until only one tree remains.
2. Assign Codes:
   • Traverse the tree from root to leaf: left edge = 0, right edge = 1.
   • The path from root to leaf gives the binary code for the character.

Why Prefix-Free?

Prefix-free codes ensure no code is a prefix of another, eliminating ambiguity during decoding. Huffman codes are optimal (no other prefix-free code can give a shorter expected length).

Visual: Huffman Tree Construction

graph TD
    A["Root"] --> B["a(30)"]
    A --> C["b(20)"]
    A --> D["c(25)"]
    A --> E["d(15)"]
    A --> F["e(35)"]
    C --> G["b(20)"]
    C --> H["d(15)"]
    G --> I["b(20)"]
    H --> J["d(15)"]
    D --> K["c(25)"]
    K --> L["c(25)"]
    F --> M["e(35)"]
    M --> N["e(35)"]

State After Step 3 (Combining d and b):

graph TD
    A["Root"] --> B["a(30)"]
    A --> C["b+d(35)"]
    A --> D["c(25)"]
    A --> E["e(35)"]
    C --> F["b(20)"]
    C --> G["d(15)"]

In the Real World

1. WhatsApp Messages:

   • Uses Huffman-like compression (or similar variable-length encoding) to reduce the size of text messages before transmission, saving bandwidth and reducing data costs for users.

2. eSewa & Khalti Transactions:

   • When you send money via eSewa, the app compresses the transaction data (including recipient details, amount, and metadata) using Huffman coding (or related techniques) to minimize the data sent over the network, speeding up processing.

3. YouTube Video Compression:

   • YouTube’s video encoding pipeline uses Huffman coding (alongside other entropy coding methods like arithmetic coding) to compress video frames. For example, frequent pixel patterns (like skies or walls) get shorter codes, while rare patterns (like fast-moving objects) get longer ones.

4. Nepal Stock Exchange (NEPSE) Data:

   • NEPSE’s trading platform processes thousands of stock transactions per second. Matrix chain multiplication optimizes how the system groups and processes matrix-like data (e.g., order books or portfolio matrices) to minimize computational overhead.

Worked Example: Huffman Coding for "SUPER DUPER CSIT"

Step 1: Calculate Frequencies

Assume the string is: S U P E R D U P E R C S I T (Spaces are treated as a character too. Frequencies after counting:)

Step 2: Build the Huffman Tree

1. Combine D, C, I, T (all frequency 1) pairwise:
   • D(1) + C(1) = DC(2)
   • I(1) + T(1) = IT(2)
2. Now combine DC(2) and IT(2) → DCIT(4)
3. Combine DCIT(4) with the next smallest (S, U, P, R, (space) all 2):
   • DCIT(4) + S(2) = DCITS(6)
4. Repeat until one tree remains.

Final Huffman Tree (Partial):

graph TD
    A["Root(20)"] --> B["E(3)"]
    A --> C["DCITS(14)"]
    C --> D["DCIT(4)"]
    C --> E["SUR(6)"]
    D --> F["D(1)"]
    D --> G["C(1)"]
    D --> H["I(1)"]
    D --> I["T(1)"]
    E --> J["S(2)"]
    E --> K["U(2)"]
    E --> L["R(2)"]

Step 3: Assign Codes

Total Bits for "SUPER DUPER CSIT": Original (ASCII, 8 bits/char): 16 chars × 8 = 128 bits Huffman-encoded: S(110) + U(1110) + P(1111) + E(0) + R(1111) + ... = 72 bits Compression Ratio: ~44% savings!

Matrix Chain Multiplication (MCM): Dynamic Programming Approach

Core Idea

Given a sequence of matrices $A_1,A_2,...,A_n$, where $A_i$ has dimensions $p_{i-1}\times p_i$, the goal is to parenthesize the product $A_1{A}_2...A_n$ to minimize the number of scalar multiplications.

Key Insight: The cost of multiplying two matrices $A(p\times q)$ and $B(q\times r)$ is $p\times q\times r$. Parenthesization changes the order of multiplications, affecting the total cost.

Visual: Matrix Multiplication Cost

For matrices $A(5\times 10)$, $B(10\times 15)$, $C(15\times 20)$:

• $(AB)C$: Cost = $(5\times 10\times 15)+(5\times 15\times 20)=750+1500=2250$
• $A(BC)$: Cost = $(10\times 15\times 20)+(5\times 10\times 20)=3000+1000=4000$ Optimal: $(AB)C$ (cheaper by 1750 multiplications!)

Dynamic Programming Solution

Algorithm Steps

1. Define Subproblems: Let $m[i][j]$ = minimum cost to multiply matrices $A_i$ to $A_j$. Let $s[i][j]$ = optimal split point between $A_i$ and $A_j$.

2. Base Case: $m[i][i]=0$ (no cost to multiply a single matrix).

3. Recurrence: For $i<j$: $$m[i][j]=\underset{i\le k<j}{\min }\{m[i][k]+m[k+1][j]+p_{i-1}\times p_k\times p_j\}$$ $s[i][j]=k$ that minimizes the above.

4. Fill Tables: Compute $m[i][j]$ for all $1\le i<j\le n$ in a bottom-up manner.

Example: $A(5\times 10)$, $B(10\times 15)$, $C(15\times 20)$, $D(20\times 30)$

Optimal Parenthesization:

• $m[1][4]=15000$ (split at $k=3$: $(AB)(CD)$)
• $m[1][2]=750$ (split at $k=1$: $A\times B$)
• $m[3][4]=6000$ (split at $k=3$: $C\times D$)

Final Parenthesization: $((AB)(CD))$

Code Implementation (Python)

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0 for _ in range(n+1)] for _ in range(n+1)]
    s = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for length in range(2, n+1):  # length of chain
        for i in range(1, n-length+2):
            j = i + length - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                cost = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
                if cost < m[i][j]:
                    m[i][j] = cost
                    s[i][j] = k
    return m, s

# Example usage:
p = [5, 10, 15, 20, 30]  # Dimensions: A(5×10), B(10×15), C(15×20), D(20×30)
m, s = matrix_chain_order(p)
print("Minimum cost:", m[1][4])  # Output: 15000

Trace of the Algorithm

Comparison: Huffman Coding vs. Other Compression Methods

Exam Tip

1. Huffman Coding:

   • Always sort frequencies before building the tree.
   • For equal frequencies, combine any two (order doesn’t matter).
   • Prefix-free is critical—never assign codes that are prefixes of others.
   • Exam Pitfall: Forgetting to include all characters (even rare ones) in the tree.

2. Matrix Chain Multiplication:

   • Memoization vs. DP: The DP table (m[i][j]) is filled bottom-up; never top-down like recursion.
   • Parenthesization: The s[i][j] table tracks splits. Always reconstruct the solution from s[i][j].
   • Example Trick: For $A(5\times 10)$, $B(10\times 15)$, $C(15\times 20)$, the optimal is always $(AB)C$ (since $5\times 10\times 15<10\times 15\times 20$).

3. Common Questions:

   • "Distinguish DP and Memoization": DP is bottom-up (table-driven), memoization is top-down (recursive with caching).
   • "Optimal Solution": In MCM, it’s the minimum scalar multiplications; in Huffman, it’s the shortest expected code length.
   • "Greedy vs. DP": Huffman is greedy (locally optimal at each step), but DP (like MCM) requires global optimization.

Practice Problems

1. Huffman Coding: Given frequencies: a:5, b:9, c:12, d:13, e:16, f:45.

   • Build the Huffman tree.
   • Assign codes to a, b, c.
   • Calculate the total bits for the string "abacabadababa".

2. Matrix Chain Multiplication: For matrices $A(10\times 30)$, $B(30\times 5)$, $C(5\times 60)$, $D(60\times 2)$:

   • Compute the minimum cost.
   • Find the optimal parenthesization.
   • Verify by calculating costs for all possible parenthesizations.

3. Theoretical:

   • Why is Huffman coding not used for compressing images with many colors?
   • Can MCM be solved with a greedy approach? Justify.