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