CS 60 practice final, Spring 2004

Problem big-O. (big-O running time analysis)

  for (int i=N ; i>1 ; i=i/2)      // i goes down to 1
    for (int j=0 ; j<i ; ++j)      // j goes up to i
      for (int k=0 ; k<i ; ++k)    // k goes up to i
        /* one operation here */

  T(1) = 1
  T(N) = N^2 + 2*T(N/2)

Problem 1. (Rex and functional programming)

    rex > waldo("waldo",[1, ["axe", ["waldo"], 7], 'd', 10]);
    
    1
    
    rex > waldo(12,[1,2,3,14,[15,16,[17,19]],20]);
    
    0
  

Part B    Write a function "lotto(W,L)" that takes two arguments -- W is a list of six winning lotto numbers and L is a list of "tickets," which are themselves lists of the form ["name of ticketholder", firstNumber, secondNumber, ... sixthNumber ] "lotto" returns a pair (that is, a list of two elements) that contains the name of the person who matched the most numbers and the quantity of numbers matched. If there are more than one person tied for the most mactching numbers, any one of them may be returned. Here is an example:

    lotto([1,2,3,4,5,6], [  ["Alice", 2, 10, 12, 14, 16, 18],
	                          ["Bob",   2,  3, 40, 41, 42, 43],
			                      ["Chris", 1,  2,  3,  5, 15, 19] ]);
    
    ["Chris", 4]
  

Part C    Imagine that you are in the midst of taking a CS60 exam and are writing rex code -- when you suddenly forget the names of the functions map and reduce. You can remember what the functions do, for instance,

rex >   map( sort, [ [2,3,1], ['b','z','z','u'] ] );
[ [1,2,3], ['b','u','z','z'] ]


rex >   reduce( *, 1, [ 5, 6, 0.5 ] );
15

One of the elegant features of rex is that almost all of its built-in functions can be implemented using basic recursive techniques. Having forgotten the names of map and reduce, how would you write these two functions from scratch?

Problem 2. (Models of computation and Programming paradigms)

class Transition
{
  int sourceState;
  int destinationState;
  int transitionChar;   // 0, 1, -1 represents a lambda-transition

  Transition(int ss, int ds, int tc)
  {
    this.sourceState = ss;
    this.destinationState = ds;
    this.transitionChar = tc;
  }
}


class NFA
{
  int numStates;

  Transition[] trans;
  boolean[] acceptingStates;


  NFA( ... input arguments ... )
  {
    ... a fully implemented constructor ...
  }

  boolean  run( Stack inputString )
  {
    /* not yet implemented */
  }
}

Explanation: The states of an NFA are represented by consecutive integers (starting at 0). The variable numStates holds the number of states of the DFA; trans is an array of Transitions (created in the constructor), each of which has a source and destination state, as well as a character on which the transition is valid. This transition character (tc) will always be either 0, 1, or -1. 0 and 1 represent the usual characters in the input string. The value of -1 is used to represent a λ-transition (no transition character consumed). The array acceptingStates is a list of booleans indicating if the nth state is accepting or not. You may assume that the NFA constructor is complete and works, i.e., it converts some set of input arguments to a valid NFA.

Your colleague has left the run method for you to implement. The idea is that run takes one input -- a Stack with the usual methods: isEmpty(), push (you won't need), and pop, which will always return (and remove) the int at the top of the list: either a 0s or a 1s. run should output a boolean value -- true, if the input is accepted by the NFA and false otherwise. Implement the run method for this NFA class.

Part B (inheritance)

You are also in charge of creating a NTM (nondeterministic turing machine) class for the new system. A nondeterministic turing machine is equivalent to a deterministic turing machine, except that there may be multiple transitions on a single tape character from a single state. Like an NFA, if there is any valid computational path that accepts an input string, then that string is considered to be accepted by the NTM. Your colleague suggests making the NTM class a derived class (subclass) of part A's NFA class.

Do you think making NTM a derived class of NFA is a good idea -- why or why not? Would you have to change the Transition class? Briefly explain any additional data members or member functions you would add in the case that you did derive NTM from the NFA class, and explain its impact on the Transition class.

Problem 3. [60 points] (DFAs, circuit design, and regular expressions)

Hormel, Inc., the manufacturer of Spam luncheon meat, has sent its vice president, Eric Brown, on an undercover mission to HMC in order to find creative ways to improve Spam's marketability. Eric has successfully infiltrated the Mudd community, and has managed to bring up the topic of Spam in casual conversations without attracting undue attention... .

In these conversations Eric has found that a key problem with Spam is its lack of aesthetic appeal. To remedy this, he has proposed a new Spam variant -- one so thinly sliced that it is essentially transparent. Trials at Platt in which Transparent Spam was added atop all of the available entrees have indicated that Transparent Spam has a promising future.

To ensure transparency, however, Hormel measures the density of each spam slice along its length. Readings of 0 are thin enough to be transparent, while readings of 1 indicate too much thickness. To qualify as Transparent Spam, a slice must register no more than one 1 within any contiguous set of four readings. If any contiguous set of four (or fewer) readings does register two or more 1's, it is sent back for reconstitution. Note that this rule also holds for inputs with fewer than four measurements.

Here are some examples of accepted and rejected readings:

   0 0 1 0 0 0 0 0 1 0               (accepted -- considered transparent)

   1 0 0 1 0 0 0 0                   (rejected -- two 1's in a four-sensor span)

   0 1 0                             (accepted -- considered transparent)

   0 0 0                             (accepted -- considered transparent)

                                     (accepted -- this piece is _really_ transparent!)

   1                                 (accepted -- it does meet the definition: no more than one 1)

   1 1                               (rejected -- two 1's in a four- (or fewer) sensor span)

   0 0 0 0 1 1 1 0 0 0               (rejected -- three 1's in a four-sensor span)

Part A. (reg. expressions)

What is a regular expression that matches all (and only) the binary patterns that are considered transparent by the above definition?

Part B. (DFAs)

Draw a DFA (Deterministic Finite Automaton) that accepts sequences of measurements for Transparent Spam and rejects any other sequences of measurements. You can assume that each sequence corresponds to a single slice to be tested.

Part C. (truth tables and circuits)

The success of Transparent Spam has led Hormel to create "Transparent Spam Snak Paks," which include a large number of length-four pieces of transparent spam. These snacks can be made so quickly, however, that Hormel would like to check for their transparency in hardware, with a dedicated logic circuit. They are maintaining their requirement that there not be more than one 1 in any set of four readings, i.e., not more than one 1 in each snack is allowed. All snacks produce exactly four readings.

Create a truth table that indicates the acceptability of each possible four-bit input according to the above rules. An output of 1 indicates that the snack is acceptable for packaging. 0 indicates that it is not acceptable.

Use the minterm expansion principle to create a circuit that will indicate whether or not a set of input readings is acceptable.

Problem 4. (Prolog)

  { w | w consists of N 0's followed by N 1's, for some N >= 0 }

  in other words

	{ λ, 01, 0011, 000111, ... }

For this problem, you can assume that the input string is formatted as a list (recall that prolog lists are like rex lists). Feel free to write helper predicates if you would like. Also, you may use any of the predicates we wrote or used in class without redefining them.

Here are some examples of p in action:

?- p([]).
yes.

?- p([0,0,0,0,0,1,1,1,1,1]).
yes.

?- p([0,0,0,1,1,1,0]).
no.

?- p([0,1,1]).
no.

 subseq( L, M )

?- subseq( [1, 2, 3], [0, 1, 5, 3, 2, 4] ).
no.

?- subseq( [1, 2, 3], [0, 1, 5, 3, 2, 4, 3] ).
yes.