Name _________________________

CS 60 Worksheet Number 2

This worksheet is keyed to the second part of Chapter 4, Chapter 5, and Section 6.4 of the notes. It is worth 25 points and is due in class on Thursday, February 28, at the end of class.

1. Page 124 in the book (139-140 in the old version) define a merge function which takes as input two sorted lists and outputs a single sorted list consisting of all of the elements of the two input lists. We've used the technique several times, e.g. in Unicalc's simplify and multiply.

Write a rex function intersect which takes two sorted lists of elements and returns a list of only those elements which appear in both lists (i.e., the "intersection" of the two lists). Use the merge technique, since the input lists are known to be sorted. (You may assume that no element appears twice in either of the input lists when considered individually, though some elements may appear in both input lists -- otherwise intersect would not have much to do!

________________________________________________________.

2/3. Write the labels of the nodes of the tree below in the order they would be considered in a breadth-first search and then in the order they would be considered in a depth-first search (ties are broken left to right). Label each ordering clearly.

4. Suppose f, g, and h are functions defined in an imperative language (like Java) as follows

int  f(int a, int b)         int g()                 int h()
{                            {                       {
  return (b==1 ? a+3 : a+7);      x++; return(x);         return(x);
}                            }                       }

Here, the same "global" variable x is being manipulated by all three functions, f, g, and h. x starts with the value of 0 (zero). (Note: this is not an endorsement for the use of global variables like x. In fact, the side effects that occur in this example are generally considered bad.)

What is f(g(),h()) if this (mythical) language uses "normal" evaluation? "Normal" evaluation specifies that the outer function be evaluated before its arguments; that is, the arguments get placed as is into the body of the outer function (f). Only then do the arguments get evaluated. "Normal" vs. "applicative" evaluation is discussed on pp. 148-149 (old version: 165-167).

5. What is f(g(),h()) (from #4) if the above language uses "leftmost applicative order" for its argument evaluation?

6. Write a set of mutually recursive rex functions which performs the same computation as the imperative function intSR below. Hint 1: there are a couple of examples in section 6.4 of this, "McCarthy's Transformation Principle," (p. 204, old version: p. 227-237), as well as an example in the lecture notes. (Hint 2: you can make the for loop into an equivalent while loop.)

int intSR(int n)
{
  int x=1; int c=0; int s=0;
  
  for ( ; s < n ; x+=2)
  {
    s+=x;
    ++c;
  }
  return c;
}

7. What is intSR (above) computing? ____________________________.

8/9. Write a recursive rex function named length that does what the built-in length function does. Then, write a second implementation of length that is tail-recursive. (I suppose if your first length was tail recursive, write the second one using a non-tail-recursive style.)