CS 306, Computer Algorithms II

Quiz 5, 11 November 2008

  1. Suppose a Huffman tree encoding a symbol set is also a balanced tree (as defined by AVL balance). What can you say about the symbol frequencies? Justify your answer.

    The symbol frequencies are equal or approximately so. The sum of two symbol frequencies is always more than any particular symbol frequency because they're approximately equal. The greedy algorithm will pair up the symbols to form n/2 pseudo-symbols of approximately equal frequency (and an extra symbol if n is odd). The argument then repeats with the pseudo-symbols.

  2. Stamps come in 1, 2, 4, and 8 cent denominations. A vending machine accepts n > 0 cents and returns an equivalent value in stamps as follows: vend as many 8 cent stamps as possible, then as many 4 cent stamps as possible and so on. Argue that this greedy algorithm vends the smallest number of stamps possible for positive n.

    Let (g0, g1, g2, g3) be the results returned by the vending machine when n cents were depositied, where gi is the number of 2i cent stamps vended. Let (o0, o1, o2, o3) be be the optimal (that is, minimal) result for n cents with similar definitions.

    Optimal local choice: Compare g3 with o3. If they're equal, then the greedy (locally optimal) choice was the (globally) optimal choice. Given the greedy algorithm, n - 8g3 < 8; that is, it's not possible to vend more than g3 8 cent stamps. If g3 and o3 are not equal, it must be that o3 < g3. That means some combination of smaller-denomination stamps must make up the shortfall in 8 cent stamps. However it's always going to take more than one smaller-denomination stamp to equal one 8 cent stamp, which means the optimal results were not minimal, a contradiction.

    Optimal subproblems: Take the optimal result and form a reduced result by removing all eight-cent stamps. The resulting stamps sum to n - 8o3 = n' cents. Suppose the alternate configuration (a0, a1, a2) also sums to n' and contains fewer stamps than the reduced configuration. The result (a0, a1, a2, o3) equals n and contains fewer stamps than the optimal result, which is a contradiction. An alternate configuration that sums to the same value as the reduced result and has fewer stamps can't exist, and so the reduced result is also optimal.

  3. The auditorium scheduling problem schedules as many non-conflicting talks as possible. Describe a greedy algorithm based on talk duration solve the problem. Does the algorithm produce maximal schedules? Justify your answer.

    A greedy scheduling algorithm based on talk duration schedules the unscheduled talk with the smallest duration that doesn't conflict with already scheduled talks. This algorithm can produce sub-maximal schedules; given the pending talks

    pending talks

    the algorithm schedules t1 and t2, while the maximal schedule contains talks t3 through t6.

  4. Given a greedy algorithm, explain how you would add backtracking. Would the resulting algorithm still be greedy? Explain.

    At each point in the greedy algorithm requiring a decision, remember the set of choices available and the choice made. When the algorithm ends unsuccessfully, it could retreat back to the most recent remembered decision and make another. If there are no more choices available, the remembered decision is discarded and the algorithm retreats back to the second most recently remembered decision, and so on.

    The modified algorithm isn't greedy because it will generally make suboptimal choices when it retreats back to remembered decisions.

This page last modified on 11 November 2008.