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:

Given a sequence of n cars to be painted c different colors, and k adjacent positions each car can move, we want to find a sequence with the minimum number of adjacent color changes. Recall that we described a dynamic programming algorithm that takes O(n*c*k^c) time. Could one find a greedy algorithm? Below is one attempt for a special case where c is 2, i.e., there are only two colors, say denoted 0 and 1: If we start with 0s, move all 0s we can next to it.
The next color is 1, so move all the 1s we can next to it.
The next color is 0, so ... We show that this greedy algorithm is incorrect. In particular, consider sequence 100010100111 and let k be 2, i.e., each car can be at most 2 positions away from its original position.

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.)