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;
}