CSE250                   Prelim I Answer Key                   Spring 2014


(1) Consider these declarations-cum-definitions:

string a = "They call me ";
const string* apcd = new string("Yellow");
string* const acp = new string(*apcd);
string* ap = acp;

(i) apcd->at(0) = 'M'; is illegal: pointer to constant data.
acp->at(0) = 'M'; is legal since a constant pointer allows modifying data.

(ii)
After the change, ap is still pointing to the same place as acp,
since only the data underneath changed.  So *ap = "Mellow " now.  Thus

cout << a << *acp << *ap << endl; prints "They call me Mellow Mellow "

Meanwhile, *because* apcd wasn't involved, it still points to "Yellow ", so

cout << a << *acp << *apcd<<endl; prints "They call me Mellow Yellow "

(iii) The copy constructor for the built-in "string" class is called in
string* const acp = new string(*apcd);

(iv) Which lines are erroneous?  

(a) a.at(0) = 'W';   //fine in C++ (But String is immutable in Scala; only different answer.)
(b) ap->at(0) = 'H'; //OK

(c) apcd = new string("Bellow");  //legal, because the new string means
                                  //changing the *address value of* apcd,
                                  //which is OK.  The old data "Yellow"
                                  //wasn't changed.
(d) //acp = &a;      //Can't change address value of constant pointer though
(e) //ap = a;        //C++ does not allow a (non-int) value assigned to ptr.


Bonus: The difference between (*ap)[-1] = 'Q'; and ap->at(-1) = 'Q';
is the the latter throws a range-error (and aborts if you don't catch),
while operator[] silently allows corrupting adjacent out-of-range memory.



(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).
(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.
*/
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;
}