Name _________________________

CS 60 Worksheet Number 4

This worksheet is keyed to the second part of Chapter 4, Chapter 5, and Section 6.4 of the notes. This worksheet is worth 15 points if turned in by class time Mon, Sept. 27.

1. Page 139 defines 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.

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 merge as a model.

________________________________________________________.

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+b : a-b);      x--; return(x);         return(x);
}                            }                       }

Here, the same variable x is shared among all three functions. x starts with the value of 1 (one). (Note that this is not an endorsement for the use of such global variables. The side effects that occur here are generally considered BAD.)

What is f(g(),h()) if this (mythical) language uses "normal" order argument evaluation? (Motto: normal order isn't.)

________________________________________________________.

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. What is the difference between closed and open lists?

________________________________________________________.

9. What is the difference between a stack and a queue?

________________________________________________________.