Lecture Notes for CS 512, Algorithm Design

17 April 2000, Greed Problems

1. huffman codes (a Java animation)

   1. given a set of n characters, encode them

      1. fixed-length encoding - use ceiling(log n) bits

      2. variable-length encoding - let more frequent characters be represented with fewer bits than are less frequent characters

   2. how to encode according to frequency

      1. use a full binary tree with leaves representing characters to be encoded

      2. build the tree so that more frequently appearing characters are closer to the root - minimize the sum of the depth-frequency product for each character

      3. the path from root to leaf gives the encoding - left is 0 and right is 1

   3. how to build the tree

      1. does it have the optimal subproblem property

         1. let T be optimal and consider sibling characters x and y

         2. form T' from T by combining x and y into a character z with f_z = f_x f_y

         3. let T'' be an optimal version of T'

         4. then replacing z in T'' with x and y would produce a more optimal version of T, a contradiction

         5. T'' can't exist and T' is optimal

         6. the optimal subproblem property holds

      2. does it have the greedy choice property

         1. let T be an optimum tree T and the characters b and c be furthest from the root of T; let f_b <= f_c

         2. x and y have the lowest frequencies with f_x <= f_y; these are the two characters picked by the greedy algorithm

         3. form T' by swapping x and b in T

         4. the depth-product sum for T is no less than the depth-product sum for T', but T is optimal, so its sum is no more than the sum for T' - that is the sums are equal.

         5. repeat the argument with characters c and y

         6. the optimal tree T can be converted into an optimal tree incorporating the first greedy choice

         7. repeat as needed

         8. the greedy choice property holds

      3. the tree-building algorithm

         1. store the characters in a min-priority queue ordered by frequency

         2. repeatedly select the two smallest items, combine into a tree node with a combined frequency and add the new node to the queue

         3. stop when the queue contains one item - the root of the optimal tree

This page last modified on 17 April 2000.