CS 60 Practice Final, Spring 2008

;

CS 60 practice final, Spring 2011

These problems are similar in scope and difficulty to those you will encounter on the final exam. This set does not necessarily cover all of the topics you will see on the final

Problem 1. (Racket and functional programming)

Part A Write a function (waldo w L) that takes in any datum at all (w) and any list, L, at all (arbirarily nested). The function waldo then returns #t if w is an element at some level of nesting in L and returns #f otherwise. Here are a couple of examples:

    > (waldo "waldo" '(1  ("axe"  ("waldo")  7)  "d"  10)) 
    #t
    
    > (waldo 12 (1 2 3 14 (15 16 (17 19)) 20))
    #f

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 scheme code -- when you suddenly forget the names of the functions map and foldl. You can remember what the functions do, for instance,

> (map sort ( (2 3 1)  ('b' 'z' 'z' 'u') ) )
( (1 2 3)  ('b' 'u' 'z' 'z') )



> (foldl  *  1  (5  6  0.5) )
15

but you simply can't remember their names... .

One of the elegant features of scheme is that many of its built-in higher-order functions can be implemented using basic recursive techniques. Having forgotten the names of map and foldl, how would you write these two functions from scratch in Racket?

Problem 2. (Models of computation and Programming paradigms)

You have been hired by Prof. Susan Rodger of Duke University to work on the next generation of JFLAP software. In particular, the NFA class is being rewritten (along with a Transition class), and, thus far, the code is as follows:

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; // state 0 is the start state

  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). You should assume that state 0 is the starting state of the NFA.

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 0 or a 1. 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. (DFAs 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.

Problem 4. (Prolog)

Part A We have seen that the language

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

  in other words

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

is not regular, i.e., no DFA nor NFA accepts this language. Prolog, however, is more powerful than DFAs -- that is, there is a prolog predicate, call it p, that will accept all of the strings in this language and reject all of the strings not in this language. This question asks you to write a definition (there are many possibilities) for such a prolog predicate, p.

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.

Part B Write a prolog predicate

 subseq( L, M )

that is true when the list L is a subsequence of the list M. The idea is that L is a subsequence of M when M contains all of the elements of L in the same order they appear in L, but perhaps M contains some intervening elements, too. You may assume that L and M are both lists. You will want to use prolog's nondeterministic programming to your advantage here... . Following are a couple of examples of subseq to clarify its desired behavior:

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

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

Problem 5. (Uncomputability)

We will review the problem from Hw 12 that asked you to prove that "regularity checking" is uncomputable... that is, the proof that no program can tell if another program accepts a regular language or not.

Problem 6. (fast algorithms and dynamic programming)

Write a java program (or, at least, design one) whose DonutSharing class has a main method that prompts the user for a single, positive integer (the length of the list of integers to come) and then accepts that list of integers - similar to the other DP inputs this term. In this case, each of the integers in the list represents the "tastiness" of a particular donut.

The goal of your program is to determine how evenly the list of donuts can be divided, based on total tastiness. That is, the list must be separated into two disjoint sets (whose union is the whole list) such that the sums of the two sets are as close to each other as possible.

Your Java program's task is to find this smallest achievable difference in tastiness scores when the list is divided into two parts. You simply need to print out that value (you don't need to print the "halves" of the list).

For example, a few runs of the program might look like this:

What is the size of your list: 3
Enter the donuts:  1 15 20
* The minimum possible difference is 4

What is the size of your list: 8
Enter the donuts:  2 7 6 7 13 6 6 13
* The minimum possible difference is 2

What is the size of your list: 8
Enter the donuts:  1 7 6 9 12 6 6 13
* The minimum possible difference is 0

Half-credit is available for any solution that works for small lists (up to 10-12 integers): this can be done recursively, with a "use-it-or-lose-it" approach. Full credit, however, is available for implemented algorithms that work on lists of hundreds or thousands of integers... it is possible! This would use dynamic programming.

In a comment at the top of your file, you should state the big-O run-time you expect for your algorithm and a sentence or two explanation (it need not be formal) of your reasoning.