Spring 2001 CS100M       Exercise E5: P3 Help         due online 8am Tue 2/20

Use Matlab's Editor to create a file E5.m with all the answers, code
and text.  You may put the text as comments, but are not required to.

1. (Read P3.*4* (earlier draft said P3.3) before starting.)  
   Consider the function definition below:

   file addpoly.m
   ___________________________________________________________________________
   | function p = addpoly(p1,p2)                                             |
   | % addpoly.  add two polynomials.                                        |
   | %     p = addpoly(p1,p2): given polynomials $p1$, $p2$, not necessarily |
   | %     canonical, return their canonical sum $p$                         |
   | p = p1 + p2;                                                            |
   |_________________________________________________________________________|

   a) On some valid values of of $p1$ and $p2$, using $addpoly$ would
      produce an incorrect answer.  

      Give a concrete example and explain why the answer is wrong.

   b) On some valid values of $p1$ and $p2$, using $addpoly$ would cause
      Matlab to report an error.  

      Give a concrete example and explain why there is an error.

   HINT: consider the polynomials x, -x, 5.

   NOTE: if you want to run the function above, you must save it without
   the surrounding "box" above, and you must also tell Matlab how to find it.

   telling Matlab how to find stuff involves telling it the "Path" where to
   search -- that can be annoying if you're not used to it.  a consultant
   in carpenter should be able to show you how if you have trouble.

2. Consider the loop below and its trace (as in lecture, we show line #s).
   At which snapshots (a) - (m) does the loop invariant hold?

1      x = 6; y = 11; X = x; Y = y; z = 0;
       % inv: X*Y = x*y + z
       while x ~=0 & y ~= 0
           if x < y
2              t = x;
3              x = y;
4              y = t;
           end
           if rem(y,2) == 0 % [2/18] typo: was rem(y,1)
5              x = x+x;
6              y = y/2;
           else
7              z = z+x;
8              y = y-1;
           end
       end
   
snapshot:  (a) (b)  (c) (d)  (e) (f)  (g) (h)  (i) (k)  (l) (m)
            |   |    |   |    |   |    |   |    |   |    |   |
       #  1 | 2 |  3 | 4 |  5 | 6 |  7 | 8 |  5 | 6 |  7 | 8 |
       X  6 |   |    |   |    |   |    |   |    |   |    |   |
       Y 11 |   |    |   |    |   |    |   |    |   |    |   |
       x  6 |   | 11 |   | 22 |   |    |   | 44 |   |    |   |
       y 11 |   |    | 6 |    | 3 |    | 2 |    | 1 |    | 0 |
       z  0 |   |    |   |    |   | 22 |   |    |   | 66 |   |
       t    | 6 |    |   |    |   |    |   |    |   |    |   |

Notes:

+ if somehow we deleted the initialization of $z$,
  we could use the loop invariant to recover its initial value.

+ when the $while$ loop finishes, we know the loop guard is false,
  i.e. $~( x ~= 0 & y ~= 0)$, which by DeMorgan's law is $x == 0 | y == 0$.
  this, together with the loop invariant, tells us:

    X*Y = x*y + z = z  (since x == 0 or y == 0), 

  that is, $z$ is the product of the original values of $x$ and $y$.

+ $X$, $Y$ are used only by the loop invariant:
  we can delete them from the code without altering its correctness,
  in which case they appear in the invariant as conceptual variables
  holding the initial values of $x$ and $y$.  

  how do we know they're supposed to be conceptual variables
  holding the initial values of $x$ and $y$?  we put them in a 
  *precondition* comment immediately before the invariant:

  % pre: let X = x, Y = y
  % inv: X*Y = x*y + z

===============================================================================

Submission:

    Respect the Submission Rules on the Exercises page.
    
    Use the Exercise Submission Site on the Exercises page.