SB CSE 675 Fall 2000 |
Program Transformation and Program Analysis
Annie Liu Solution 7 |
Handout S7
Nov. 8, 2000 |
Problem 1.
a. sequence from greedy: 100000111101, number of color changes: 4
b. better sequence: 001110000111, number of color changes: 3
Problem 2.
a.
list* cons(int a, list* b) { list* cell = (list *)malloc(sizeof(list)); cell->car = a; cell->cdr = b; return cell; } int least(list* x) { list* xdot = x; list* s = NULL; int r; while (1) { if (xdot->cdr == NULL) { r = xdot->car; break; } else { s = cons(xdot,s); xdot = xdot->cdr; } } while (xdot != x) { xdot = s->car; s = s->cdr; r = (xdot->car < r) ? xdot->car : r; } return r; }b.
int least(list* x) { list* xdot = x; list* s = NULL; int r; while (1) { if (xdot->cdr == NULL) { r = xdot->car; break; } else { list* tmp = xdot->cdr; xdot->cdr = s; s = xdot; xdot = tmp; } } while (xdot != x) { list* tmp = s->cdr; s->cdr = xdot; xdot = s; s = tmp; r = (xdot->car < r) ? xdot->car : r; } return r; }