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