Your name __________________________

Harvey Mudd College CS 60 Mid-Term Exam

Spring semester, 2000

Six Problems, 100 points

Partial credit will be given for partial (correct) answers. Try to be as concise as possible. This exam is closed-book, though the use of a page of notes is OK.

1. (Rex and recursion) [25 points total]

A. [15 points] Since recent classes have started with a round of Jotto, it seemed only appropriate to start the midterm that way, too. Suppose you and a colleague are writing a jotto scoring function, jottoScore, in rex. jottoScore takes in two strings (of any length) and returns the number of letters the strings have in common. For example,

jottoScore("abcde", "bbbbb");
1

jottoScore("apple", "pales");
4

jottoScore( word1, word2 ) = jottoScoreSorted( sort(explode(word1)), 
                                               sort(explode(word2)) );

How would you write jottoScoreSorted to finish the project? Abbreviate as jSS if you'd like to. Any correct solution will get most of the credit, but for full credit, take advantage of the fact that the inputs to jSS are sorted lists. Recall that explode merely returns the list of characters from its input string, so that explode("apple") == [ 'a', 'p', 'p', 'l', 'e' ]. Thus, the inputs to jottoScoreSorted are two sorted lists of characters.

jSS( [], _ ) => 0;
jSS( _, []) => 0;
jSS( [ f|r ], [ F|R ] ) => f == F ? 1 + jSS(r,R);
jSS( [ f|r ], [ F|R ] ) => f < F ? jSS(r,[F|R]);
jSS( [ f|r ], [ F|R ] ) => f > F ? jSS([f|r],R);

B. [10 points] Is your solution to part A (the jSS function) a tail-recursive function? If so, write a non-tail-recursive version; if not, write a tail-recursive version of the same function (jSS).

jSS( W1, W2 ) => jSS( W1, W2, A );
jSS( [], _ , A ) => A;
jSS( _, [], A ) => A;
jSS( [ f|r ], [ F|R ], A ) => f == F ? jSS(r,R,1+A);
jSS( [ f|r ], [ F|R ], A) => f < F ? jSS(r,[F|R],A);
jSS( [ f|r ], [ F|R ], A) => f > F ? jSS([f|r],R,A);

2. (Higher-order functions) [10 points]

A. [5 points] Write a rex function jottoScoreList( word, L ) whose first input is a string (the hidden word) and whose second input is a list of strings (words). jottoScoreList should output a list of the scores that each word in L gets when compared to the first input (word). For example,

jottoScoreList( "apple", [ "pales", "kiosk" ] );
[ 4, 0 ]

Feel free to abbreviate as jSL and to use jottoScore (jS) as if it already works, even if you didn't answer Problem 1. You will not need to use jSS.













Answer: Note that cJS is defined in the next problem.

jSL( word, List ) = map(cJS(word), List);

B. [5 points] Write a rex function createJottoScorer( word ) that takes in a single string as input. createJottoScorer should output a function that takes a string as input and produces the score of that input when compared to word. This will let you write code like the following:

rex >  f = createJottoScorer( "apple" );


rex >  f( "pales" );
4

cJS( word ) = (x) => jS(word, x);

3. (Functional vs. Imperative Programming) [15 points]

int   f(int n)
{
  int i=n; int d=0; int c=0;

  for ( i=n ; i >= 1 ; --i )
  {
    d = n/i;
    if (d*i == n) 
    {
      ++c;
    }
  }
  return c; 
}

Answer:

f(n) = f2(n,0,0,n);

f2(i,d,c,n) = i > =1 ? f3(i,n/i,c,n) : c; 

f3(i,d,c,n) = d*i == n ? f2(i-1,d,c+1,n) : f2(i-1,d,c,n); 

A compressed version of the function is:

f(n) = factors(n, n, 0);

factors(n, i, c) = 
    i >= 1 ? 
        ((n/i)*i == n) ? 
          factors(n, i-1, c+1) 
        : factors(n, i-1, c)
    : c;

4. (Grammars and Parsing) [10 points total]

Consider the following grammar for (some of) Java's boolean expressions. Capital letters represent nonterminal symbols; lowercase letters and punctuation (boolean operators) represent terminal symbols.

E  ->  A  {  ==  A  }

A  ->  O  {  &&  O  }            ( This is the letter O. )
    
O  ->  N  {  ||  N  }

N  ->  { ! }  V

V  ->  a | b | c | ... | z

a && ( !b == a )

V  ->  a | b | c | ... | z | (E)

(AND (var a) (EQ (NOT (var b)) (var a)))
  

a = false, b = false

a = true, b = false

a * a'

a + a'

5. (Object-oriented programming and Inheritance) [10 points total]

String getAVar()
{
  String s = left.getAVar();

  if ( s == null )
  {
      s = right.getAVar();
  }

  return s;  
}

One of the benefits of object-oriented programming is its support of code reuse, i.e., not repeating code in several places. Could the above version of getAVar() (or its equivalent) be placed in the base class Expr, so that it would not have to be written four times? Why or why not? How might the the Expr class hierarchy be improved to avoid having to write the same code four times?

To encapsulate what the four classes (AndExpr, OrExpr, ImpExpr, and EqExpr) have in common, however, we can create a layer of classes in our hierarchy between Expr and the actual expressions. In particular, we could add the classes

BinaryExpr    (for Exprs with a left and right subexpression)
UnaryExpr    (for Exprs with one subexpression (NOT))
ZeroExpr    (for Exprs without subexpressions (or we could omit this entirely))
 

6. (Data Structures) [30 points total]

A ThreeTree holds a piece of data and is the root of a tree with three children. Note that a ThreeTree is really just a single node that may have nonnull children that are ThreeTrees themselves. There is no need for a separate ThreeTreeCell class, since a ThreeTree is, in effect, a ThreeTreeCell. In the illustration, the reference T refers to a ThreeTree. The reference W refers to the ThreeTree that is T's leftmost child.

A. [10 points] Sketch a possible Java implementation for this class, ThreeTree. Include only data members and a general-purpose constructor; don't worry about other methods that the class might support. (Hint: a general-purpose constructor will have to take some ThreeTrees as input arguments.)



















Answer:

class TT
{
  String data; TT left, center, right;
  
  TT(String d, TT l, TT c, TT r)
  {
    data = d; left = l; center = c; right = r;    
  }
}

B. [20 points] As is typical at Treeage, there are far too many project ideas to possibly implement them all. You need to decide which ideas will have the best chance of getting done, given your limited time. As you scan the list of projects, you notice an idea for a SearchableThreeTree class. It is similar in structure to the ThreeTree depicted above, but is intended to support depth-first search without the need of an extra stack to keep a list of the cells on the current search path. Having just written ThreeTree, you feel that you won't have to do much additional coding to write SearchableThreeTree, by taking advantage of class inheritance.

What is the depth-first-search order of the data in the ThreeTree named T in the illustration above ?

The order was A, B, E, F, C, G, D, H, I, J .

Propose a SearchableThreeTree class that extends the ThreeTree class. Write the code for the class, including data members and a general-purpose constructor. Abbreviate as STT, if you like.

class STT extends TT
{
  STT parent;
  boolean stopSearching = false;
  
  STT(String s, STT p, STT l, STT c, STT r)
  {
    super(s,l,c,r);
    parent = p;    
  }
}

Implement a depth-first-search method DFS for your SearchableThreeTree class. The method should take as input a piece of data that it is searching for. As output, it should print the path of data from the found datum back to the root. If the desired piece of data is not found, a message to that effect should be printed.

You can assume that all of the data stored in the tree are Strings. No value needs to be returned from the DFS method.

Implement DFS as a nonstatic method. A possible signature for the implementation would be

void  DFS(String dataSought) { ... }

void DFS(String s)  /* s is the string to find */
{
  if (s.equals(this.data)) {   /* print path back to start */
    STT current = this;
    do {
      System.out.println(current.data);
      current = current.parent;
    } while (current != null);
    stopSearching = true;
    return; // this will continue to seek out other locations of s
  }
  
  if (!stopSearching) left.DFS(s);
  if (!stopSearching) center.DFS(s);
  if (!stopSearching) right.DFS(s);

  if (!stopSearching) System.out.println("Data " + s + " not found!");
}

Extra Credit #1. (Logical Circuits) [10 points total]

 Input v     Input w      Input x      Output 1     Output 2
 
   0           0            0             1            1
   0           0            1             1            0
   0           1            0             0            1
   0           1            1             1            0
   1           0            0             1            1
   1           0            1             0            1
   1           1            0             0            1
   1           1            1             0            1

A. [ 5 points ] Use the Karnaugh maps shown here to determine a minimal representation of these two logical functions (one for Output bit 1, one for Output bit 2).

B. [ 5 points ] Draw the two resulting circuits. You need not connect them in any way (just assume the inputs are the same).

Extra Credit #2. (Logic) [ 5 points ]

In addition to being far gloomier than the island, Transylvania has inhabitants that are categorized in two ways, rather than one.

First, all Transylvanians are either sane or insane. Sane Transylvanians see the world as it is. That is, sane Transylvanians believe truths and disbelieve falsehoods. Insane Transylvanians, on the other hand, only believe falsehoods and disbelieve all truths. In other words, everything a sane inhabitant believes is true; everything an insane inhabitant believes is false.

In addition, all Transylvanians are either human or vampires. Humans always tell the truth -- more precisely, they make statements that they believe to be true. Vampires always lie -- that is, they make statements that they do not believe true. Notice that this means an insane vampires will end up always making true statements, since they will lie about the falsehoods they believe.

Suppose you encounter a Transylvanian that makes the following two statements:

1) I am sane.
2) I believe that Count Dracula is dead.