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 20 points and is due in class on Wed., Feb. 23 or Thurs., Feb. 24.

1. Pages 139-140 in the book 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 with the methods sortAppend and cancel.

Write a rex function intersect which takes two sorted lists of elements (interpreted as sets) and returns a list of only those elements which appear in both lists (i.e., both sets). Use the merge technique, since the input lists are known to be sorted.

________________________________________________________.

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 as

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

Here, the same variable x is shared among all three functions. 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" order argument evaluation? (Motto: normal order isn't.) "Normal" vs. "applicative" argument evaluation is discussed on pp. 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: there are a couple of examples in section 6.4 of this, "McCarthy's Transformation Principle," as well as an example in the lecture notes. (Hint: 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.)