CS 60 practice final, Fall 2012

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 */

/*
 * the input, List, has N elements
 */
void f(int[] List) {
  if List has only 1 element, return
  call f on the first half of the List
  call f on the second half of the List
  call insertion sort on the complete input List
}

Problem 1. (Racket and functional programming)

    > (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 (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

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)

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)

(We may not cover regular expressions in Spring 2014..., in which case don't worry about this question!)
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)

  { 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.

Problem 5. (Uncomputability)

This term in CS60 everything is computable! (There are no uncomputability questions...)

Problem 6. (fast algorithms and dynamic programming)

Design first a UIOLI algorithm then a dynamic program that

• takes in as input a list of integers: each integer represents the total tastiness of a donut. (Each integer is positive.)
• outputs the smallest possible difference in total tastiness when the donuts are divided into two disjoint groups: one for you and one for your donut-sharing comrade.
• Hint: Can you reduce this problem to one you implemented earlier in the semester?!

More explanation:    The goal of your program is to determine how evenly the list of donuts can be divided into two subsets, 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 algorithm's task is to find the smallest achievable difference in tastiness scores when the list is divided into two parts. In this case, you can use only the integers on the list (there may be repeats), but there are not infinitely many copies of them.

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

What is the size of your list: 3
Enter the donuts:  1 15 20
* The minimum possible difference is 4
* The lists are [1, 15] and [20]

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
* The lists are [2,7,7,13] and [6,6,6,13]

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
* The lists are [6,6,6,12] and [1,7,9,13]

Hints on the dynamic-programming version

To get started, create a 1d table/array, call it T, that is indexed from 0 up to half the sum of the list. Each element T[i] is meant to represent whether a tastiness sum of i is possible for a subset of the donuts, with 1 representing possible and 0 representing impossible. Since each possible i automatically implies that sum(L)-i is also possible, we don't need to keep track of those larger values (so the list only extends up to sum(L)/2.

For example, since a tastiness sum of 0 is always possible (use no donuts), initially, the list has T[0] = 1 and all of the other entries in T are equal to 0.

How could you determine all of the indices in that array that represent achievable sums of integers in time O(N*S), where N is the number of integers in the list and S is the sum (or half the sum) of the list. Then, how do you use that table to find the smallest-achievable tastiness difference?!