Greedy Algorithms

10.1Introduction to Greedy Algorithms

10.2Steps to Design a Greedy Algorithm

GREEDY(A):
    candidates = order_by_greedy_rule(A)
    solution = []

    for candidate in candidates:
        if feasible(candidate, solution):
            solution.append(candidate)

    return solution

10.3Fractional Knapsack Problem

Second knapsack example

def fractional_knapsack(items, capacity):
    for item in items:
        item.ratio = item.profit / item.weight

    items.sort(key=lambda item: item.ratio, reverse=True)
    total_profit = 0

    for item in items:
        if capacity == 0:
            break

        if item.weight <= capacity:
            capacity -= item.weight
            total_profit += item.profit
        else:
            total_profit += item.profit * (capacity / item.weight)
            break

    return total_profit

10.4Huffman Coding

1. Problem data

2. Huffman solution approach

1. Merge the two least frequent nodes into a new node whose frequency is their sum.
2. Put the new node back and repeat until one root remains.
3. Add 0 to every left edge.
4. Add 1 to every right edge.
5. Traverse from the root to each leaf to obtain its Huffman code.

3. Final answer — the lecture’s Huffman codes

4. Verify the storage saving

10.5Building a Huffman Tree with a Priority Queue

1. Create a binary-tree node for every character and frequency.
2. Place the nodes in a priority queue—a min heap ordered by frequency.
3. Extract the two minimum nodes, attach them to a new node, and insert their sum.
4. Repeat until the queue contains one node: the root.

HUFFMAN(C):
    n = |C|
    Q = C
    for i = 1 to n - 1:
        allocate a new node z
        x = EXTRACT_MIN(Q)
        y = EXTRACT_MIN(Q)
        z.left = x
        z.right = y
        z.freq = x.freq + y.freq
        INSERT(Q, z)
    return EXTRACT_MIN(Q)  # the root is the only node left

Classic six-character construction

The second tree from the slides starts with f:5, e:9, c:12, b:13, d:16, a:45.

Encoding and decoding: FACE

Using the same six frequencies and tree shape above, relabel the symbols as A:5, B:9, C:12, D:13, E:16 and F:45. With left edges labelled 0 and right edges labelled 1, the mapping is:

Decompression

The decoder needs the mapping table (or the equivalent Huffman tree) and the compressed bitstream.

1. Read bits from left to right, adding one bit at a time to the current code.
2. When the code matches a symbol in the table, output that symbol and clear the current code.
3. Repeat until the bitstream has been decoded.

10.6Job Sequencing with Deadlines

Greedy solution

1. Sort the jobs in decreasing order of profit.
2. For each job, place it in the latest empty slot that is no later than its deadline.

Results from the slides

10.7Optimal Merge Pattern

Before optimizing a sequence of file merges, recall how two sorted arrays are merged in linear time.

i = j = m = 0
while i < len(A) and j < len(B):
    if A[i] <= B[j]:
        C[m] = A[i]
        i += 1
    else:
        C[m] = B[j]
        j += 1
    m += 1

# Append the remaining elements from A or B.

Greedy solution

1. Insert all file sizes into a min heap (priority queue).
2. Extract the two smallest files.
3. Merge them; the merge cost is the sum of their sizes.
4. Insert the merged file back into the heap.
5. Repeat until one file remains; add every merge cost to the total.

Cost comparison from the slides