CSE250             Prelim I Answer Key --- Scala version                Spring 2014


(1) Consider the following lines in Scala:

val a = "They call me " 
var apcd = new String("Yellow ") 
val acp = new StringBuilder(apcd) 
var ap = acp

(i) apcd(0) = ’M’ is illegal because String is immutable(constant data).
    acp(0) = ’M’ = 'M'  is legal since StringBuilder is mutable and "val" does not protect the underlying data.

(ii)

println(a + acp + ap) 
println(a + acp + apcd)

After the change, ap is still referencing the same object as acp,
since only the data underneath changed.  So ap = "Mellow " now.  Thus it prints

"They call me Mellow Mellow "

Meanwhile, *because* apcd wasn't involved, it still has "Yellow ", so the second line prints (as expected)

"They call me Mellow Yellow "


(iii) The line that makes a copy is

val acp = new StringBuilder(apcd)

The string "Yellow " has to be copied in order to become mutable.


(iv) Which lines are erroneous?  

(a) a(0) = ’W’  //Compile-time error: String is immutable.  (But OK in C++ since "string" is mutable.)
(b) ap(0) = ’H’ //OK---ap designates a mutable StringBuilder object.
(c) apcd = "Bellow" //legal since apcd is var.
(d) acp = a     //Compile-time error because of val
(e) ap = a      //Illegal in Scala for a different reason than in C++: the compile does not allow assigning a String object to a StringBuilder variable without calling "new" to make a copy.

Bonus: With new StringBuilder... it is OK.




(2) (i) (a) executes the loop body n times.
        (b) executes the body (n/2)*(n/2) = n^2/4 times.

(ii)  (a) When body is a Theta(m)-time procedure, m=0 to n-1, overall time is
          quadratic, i.e. Theta(n^2).  This == what happens with isAscending()
          on Assgt. 3, per the exam-prep notes about it that were posted.
      (b) Theta(n^3), i.e. cubic time.  The easiest way to see this is that
          on half of the titerations, j - i is >= n/2, so the overall time
          is at least (1/2)(n/2)(n/2)*(time to sum n/2 items) = Theta(n^3).
		  
[The Fibonacci lecture notes I used in 2014 are not relevant in this text until Chapter 15,
so the next two questions are Not Applicable for now.]

(iii) (d) is like the "smart Fibonacci" recursion---it recurses n/2 times
          and stops.  The time for the base statement is "O(1)" since n=1,
          but even if it were O(n) you'd still have n/2 recursions + O(n) time
          = Theta(n) overall time
(iv)  Item (c) is the regular "dumb" Fibonacci recursion, and
      takes exponential time.  (About (golden-ratio)^n time, in fact).
      So it is vastly more time asymptotically than cubic.  Overall:
      (d) < (a) < (b) < (c) where "f < g" means f = o(g) via Little-Oh, since
      n = o(n^2) = o(n^3) = o(exponential).



(3) 
/** True if switching 2 adjacent unequal letters in x leaves y.
*/
def transpose(val x: String, val y: String): Boolean = {
   if (x.length != y.length) { return false; }
   //else
   val xlenm1 = x.length - 1
   for (i = 0 until xlenm1) {  //"until" is exclusive
                               //INV: x(j) == y(j) for j < i
      if (x(i) != y(i)) {      //mismatch, so moment of truth is now
	  
         if (x(i) == y(i+1) && x(i+1) == y(i) && x(i) != x(i+1)
               && x.substring(i+2) == y.substring(i+2)) {
            return true;  //rest of strings after transpose are equal
         } else {
            return false;
         }
	  }
   } //control here means x == y
   return false;
}




/** C++ answer, FYI
 */
bool transpose(const string& x, const string& y) {
   if (x.length() != y.length()) { return false; }
   // else
   int xlenm1 = x.length() - 1;
   for (int i = 0; i < xlenm1; i++) {
      if (x[i] != y[i]) { //mismatch, so moment-of-truth is now
         if (x[i] == y[i+1] && x[i+1] == y[i] && x[i] != x[i+1]
             && x.substr(i+2) == y.substr(i+2)) {
            return true;
         } else {
            return false;
         }
      }
   } //control here means x == y
   return false;
}