SB CSE 675
Fall 2000 |
Program Transformation and Program Analysis
Annie Liu Exercises 7 |
Handout E7
Nov. 2, 2000 Due Nov. 8 |

**More on Dynamic Programming, Recursion to Iteration.** (Due
at class time next Wednesday.)

**Problem 1. Car painting problem**

Consider the car painting problem discussed in class:

Recall that we described a dynamic programming algorithm that takes**a.** What is the resulting sequence if one applies the greedy
algorithm above? What is the number of adjacent color changes?

**b.** What is a better resulting sequence? What is the number
of adjacent color changes? (Actually there are at least two better
ones.)

**Problem 2. Recursion to iteration**

Function `least` in the following C code returns the
minimum element of a nonempty list using recursion.

typedef struct { int car; void* cdr; } list; int least(list* x) { if (x->cdr == NULL) { return x->car; } else { int v = least(x->cdr); if (x->car < v) { return x->car; } else { return v; } } }

**a.** What is an iterative version of `least` using an
explicit stack data structure? (for an example, see slide 13)

**b.** What is an optimized version of `least` from item
**a** after pointer reversal? (for an example, see slide 14) (This
iterative version is actually 10 times as fast as the recursive
version.)