SB CSE 675
Fall 2000
Program Transformation and Program Analysis
Annie Liu
Exercises 1
Handout E1
Sep. 8, 2000
Due Sep. 13

Writing, Reading, and Designing Programs. There are four problems. You should spend as little time as possible on the first three. The fourth is optional, but feel free to spend as much time as you like.

Problem 1. List element removal and list reversal

For the former, given an element i of a list x and x, we want to get the rest of list without the first occurrence of i.    For the latter, given a list x, we want to get a list with elements in x reversed.    For each of them, do the following:

a. Write a procedure that uses a loop to return such a list without modifying x.

b. Suppose x is not used for other purposes. Write a procedure that uses a loop to modify x and returns the modified list.

Problem 2. Insertion sort and selection sort

Given a list of numbers, we want to get a list of these numbers sorted in increasing order.

a. Insertion sort does this by recursively sorting the tail of a list and then inserting the head of the list into the right place of the sorted tail. Write recursive functions for this without modifying the input.

b. Selection sort does this by selecting out the least element in the list, recursively sort the rest of the list, and builds a new list with the least as the head and the recursively sorted other elements as tail. Write recursive functions for this without modifying the input.

Problem 3. Functions what1 and what2

a. Suppose List is as defined in lecture 2. What does the following C function do?

List* what1(int a, List* b) {
  List* xdot = b;
  List* r;
  List** rdot;
  rdot = &r;
  while (1) {
    if (a == xdot->head) {
      *rdot = xdot->tail;
    } else {
      *rdot = xdot;
      rdot = &((*rdot)->tail);
      xdot = xdot->tail;
  return r;

b. What does the following function do?

what2(a,b) = if empty(b) then b
             else if a=head(b) then tail(b)
             else mkList(head(b),what2(a,tail(b)))

Problem 4. Longest common subsequence and image blurring

If you think you have an efficient procedure to either of these two problems in the lecture notes, write it.