CS100M  Spring 2001  Solutions to Review Questions R4 for the Final (test T4)

===============================================================================
R4.1
===============================================================================

a) What are some test cases that should be tried to see that the code works?
   Intersection and containment should be tested on:
   + empty intervals, e.g. $[1,0]$
   + two disjoint intervals, e.g. $[0,1]$ and $[2,3]$
   + two overlapping intervals, e.g. $[0,2] and $[1,3]$
   + first properly contains the second, e.g. $[0,3]$ and $[1,2]$
   + second properly contains the first, e.g. $[1,2]$ and $[0,3]$

b) Matlab functions (use structs to be more like Java).

   Other operations cannot be disallowed: essentially, everything is 
   $public$ in Matlab, so anybody/everybody is allowed to look inside
   and modify any piece of data.

   function s = interval(left,right)
   % s = interval(left,right): struct $s$ represents interval $[left,right]$
       s.a = left;
       s.b = right;

   function s = intersect(x,y)
   % s = intersect(x,y): intersection of intervals $x$, $y$
       s = interval(max(x.a,y.a), min(x.b,y.b));

   function yesno = contains(x,y)
   % yesno = contains(x,y): "interval $x$ contains interval $y$?"
       yesno = y.a > y.b | ( x.a <= y.a & y.b <= x.b );

   function s = tostring(x)
   % s = tostring(x): string representation of interval $x$
       s = ['[' num2str(x.a) ',' num2str(x.b) ']'];

   test script:

        x = interval(0,2);
        y = interval(1,3);
        z = intersect(x,y);
        fprintf('%s intersect %s: %s', tostring(x), tostring(y), tostring(z));
        fprintf('%s contains %s: %d', tostring(y), tostring(z), contains(y,z));

c) Java code

// closed intervals (endpoints are included)
public class Interval {
    private double a; // left endpoint
    private double b; // right endpoint

    // constructor
    public Interval(double left, double right) {
        a = left;
        b = right;
    }

    // return intersection of self with $y$
    public Interval intersect(Interval y) {
        return new Interval(Math.max(a,y.a), Math.min(b,y.b));
    }

    // return "self contains $y$?"
    public boolean contains(Interval y) {
        return y.a > y.b || ( a <= y.a && y.b <= b );
    }

    // description of self
    public String toString() {
        return "[" + a + "," + b + "]";
    }

    public static void main(String[] args) {
        Interval x = new Interval(0,2);
        Interval y = new Interval(1,3);
        Interval z = x.intersect(y);
        System.out.println(x + " intersect " + y + ": " + z);
        System.out.println(y + " intersect " + z + ": " + y.contains(z));
    }
}

===============================================================================
R4.2
===============================================================================

a) Java code

public class R4_2 {
  // minimum and its position (first occurrence) of each column of matrix $x$:
  // java $m=min(x);$ approximates matlab $[val,pos]=min(x); m=[val;pos];$
  public static int[][] min( int[][] x ) {
      // inv: $m[0..1][0..col-1]$ holds minimums and positions 
      //      for $x[:][0..col-1]$
      int col = 0 ;
      int[][]  m = new int[2][x[0].length] ;
      while ( col != x[0].length ) {
          // update $m$ for current (unprocessed) column in $x$.
          // inv: $pos$ is the row of the minimum in rows $0..row-1$ of 
          //      current column
          int pos = 0 ;
          int row = 1 ;
          while ( row != x.length ) {
              if ( x[row][col] < x[pos][col] ) // new minimum?
                  pos = row ;
              row += 1 ; // advance to next row
          }
          m[0][col] = x[pos][col] ; // record minimum
          m[1][col] = pos         ; // record position
          col += 1 ; // advance to next column
      }
      return m ;
  }

  // here is the java equivalent (but output is not formatted) of the matlab 
  // code $[val,pos] = min([27 -18 24 ; 26 4 17 ]); disp([val' pos'])$
  public static void main(String[] args) {
    int[][] m=min(new int[][] { new int[] {27,-18,24}, new int[] {26,4,17} });
    // print one column of $m$ per line of text
    // inv: already did columns $0:i-1$
    int i = 0;
    while ( i < m[0].length ) {
        System.out.println( m[0][i] + " " m[1][i] );
        i += 1;
    }
  }
}

b) Matlab code

    function [values,positions] = min(x)
    % [values,positions] = min(x): first minimum value and its position
    %                              for each column in matrix $x$

    if size(x,2) = 1
        x = x'; % convert a row vector into a column vector
    end

    for col = 1:size(x,2)
        pos = 1;
        for row = 2:size(x,1)
            if x(row,col) < x(pos,col)
                pos = row;
            end
        end
        values(col) = x(row,pos);
        positions(col) = pos;
    end

===============================================================================
R4.3
===============================================================================

// Given:

    public class Creature {
        protected String name; // Creature's name
    
        // constructor: initialize name to n
        public Creature(String n) { 
            name = n; 
        }
    
        // speak, i.e. vocalize
        public void speak() { 
            System.out.println(name + " speaks"); 
        }
    
        // perform an action
        public void act() { 
            speak(); 
        }
    }
    
    // create 4 Creatures and repeatedly (5 times) have each act one at a time
    public class Target {
        public static void main(String args[]) {
            Creature[] c = { // 4 Creatures
                new Creature("Butch"), 
                new Creature("Fluffy"), 
                new Creature("Sleepy"), 
                new Creature("Clarus") 
            };
            // repeat 5 times: each Creature acts
                for (int times=5; times>0; times--)
                    for (int i = 0; i<c.length; i++)        
                        c[i].act();
        }
    }

// a)  

    public class Cat extends Creature {
        private int purrLength; // purr length (number of r's),
    
        // constructor: name is name, purr is purr length
        public Cat(String name, int purr) { super(name); purrLength = purr; }
    
        // speak: meow
        public void speak() { System.out.println(name + " meows"); }
    
        // purr
        public void purr() { 
            System.out.print(name + " pu");
            for (int i = 0; i<purrLength; i++) System.out.print("r");
            System.out.println("s");
        }
    
        // act: randomly choose between purr and old choice for act
        public void act() {
            if (Math.random() < .5) purr();
            else super.act();
        }
    }

// b)  

    public class Dog extends Creature {
        private int wags = 0; // number of wags already performed
    
        // constructor: name is name
        public Dog(String name) { super(name); }
    
        // speak: woof
        public void speak() { System.out.println(name + " woofs"); }
    
        // wag and print new number of times have wagged
        public void wag() { 
            wags++;
            System.out.println(name + " wags its tail for the " 
                               + wags + "-th time");
        }
    
        // act: randomly choose between wag and old choice for act
        public void act() {
            if (Math.random() < .5) wag();
            else super.act();
        }
    }

// c)  

    public class DogCow extends Dog {
        // constructor: DogCows are always named "Clarus"
        public DogCow() { super("Clarus"); }
    
        // speak: randomly choose between moof and old speak
        public void speak() { 
            if (Math.random() < .5) super.speak();
            else System.out.println(name + " moofs"); 
        }
    }

// d)  

    // create 4 Creatures and repeatedly (5 times) have each act one at a time
    public class CUCSApplication {
        public static void main(String args[]) {
            Creature[] c = { new Dog("Butch"),    new Cat("Fluffy",3), 
                             new Cat("Sleepy",7), new DogCow()         };
            for (int times = 5; times>0; times--)
                for (int i = 0; i<c.length; i++)
                    c[i].act();
        }
    }

===============================================================================
R4.4
===============================================================================

A *palindrome* is a string that reads the same forwards and backwards, e.g.
$"anna"$ is a palindrome, $"fred"$ is not a palindrome.  For this question,
___ assume all letters in all strings of interest are lower-case.

a)  // flip contents of $a$ left-to-right
    static void fliplr(char[] a) {
        // inv: $a[0..i-1]$ and $a[j+1..]$ already flipped
        int i = 0;
        int j = a.length-1;
        while (i<j) {
            char tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++; j--;
        }
    }

b) $s == fliplr(s)$ does not work in Matlab because $==$ returns the vector
   of element-wise comparisons.    See part (d) for correct way to do it.

   $fliplr(s)$ is not even a legal call in Java because $fliplr$ takes
   a character array, not a string, as a parameter.  Furthermore, $fliplr$
   does not return any value, so it does not return something that can be
   compared, e.g. $s == fliplr(s.toCharArray())$ is illegal.  ($void$ means
   "no value is returned").  Below, $oops$ and $bad$ are both legal Java code.

        char[] c = s.toCharArray();
        fliplr(c);
        boolean oops = c == c; // always $true$!
        boolean bad = s == new String(c); // (almost) always $false$!
   
   Neither $oops$ nor $bad$ has a useful value: $==$ on references in Java
   does not mean "do both objects have the same or equivalent contents?"
   but rather "are the two references aliases for the same object?"

   The $test$ code in part (c) does the test correctly.

c)  static boolean ispalindrome(String s) {
        char[] c = s.toCharArray();
        fliplr(c);
        boolean test = s.equals(new String(c));
        // test palindrome without using $fliplr$
        // inv: $test$ = $s[0..i-1]$ is the reverse of $s[j+1..]$
        //      (and $s[0..i-1]$ and $s[j+1..]$ have the same length)
        boolean test2 = true;
        int i = 0;
        int j = s.length()-1;
        while (test2 && i<j) {
            test2 = s.charAt(i) == s.charAt(j);
            i++; j--;
        }
        if (test != test2)
            System.out.println("two versions disagree");
        return test;
    }

d)  function yesno = ispalindrome(s)
    % yesno = ispalindrome(s): return "is string $s$ a palindrome?""
        yesno = all(s == fliplr(s));

===============================================================================
R4.5
===============================================================================

a) The top row is easy: print $n$ stars.  What about the later rows?

   Observe that the number of "hollow" spaces goes down by 1 on each row,
   whereas the number of "padding" spaces goes up by 1 on each row.

 n=1  n=2  n=3    n=4      n=5
   *  **   ***    ****     *****    row 1
       *    **     * *      *  *    row 2
             *      **       * *    row 3
                     *        **    row 4
                               *    row 5

   Since the row number $row$ goes up by 1 on each row, this means

        hollow = something - row    and    padding = something + row.

   Plugging in a few numbers from the examples yields

        hollow = n-1 - row          and    padding = -1 + row.

   Another way to think about this is that the position of the
   leftmost star on a row is in column $row$ (think of columns
   starting at 1, not 0), so $row-1$ "padding" spaces need to be
   printed.  The position of the rightmost star is in column $n$, so
   $n-row-1$ "hollow" spaces need to be printed between them.

   int n = in.readInt(); // size (= base = # of rows) of hollow right-triangle
   // print row 1 -- no padding spaces, n stars; advance to next line
       for (int i = 0; i < n; i++) System.out.print("*");
       System.out.println();
   // print rows 2 through n -- note: row n has only 1 star
       for (int row = 2; row <= n; row++) {
           // print row $row$
               // print row-1 padding spaces and a star
                   for (int i = 0; i < row-1; i++) System.out.print(" ");
                   System.out.print("*");
               // print n-row-1 hollow spaces and (if needed) another star
                   for (int i = 0; i < n-row-1; i++) System.out.print(" ");
                   if (row < n) System.out.print("*");
           // advance to next line
               System.out.println();
       }

   Remark 1: the inner loops could "count down" instead of "count up":

                   for (int i = row-1; i > 0 ; i--) System.out.print(" ");
             and
                   for (int i = n-row+1; i > 0 ; i--) System.out.print(" ");

   Remark 2: the body of the outer loop could be something like this:

               int col = 1; // next column to print
               // print leftmost star
                   for ( ; col < row; col++) System.out.print(" ");
                   System.out.print("*"); col++;
               // print rightmost star (if different from leftmost)
                   for ( ; col < n ; col++) System.out.print(" ");
                   if (row != n) System.out.print("*");
               System.out.println();

b) Observe that the number of "hollow" spaces goes down by 2 on each row,
   whereas the number of "padding" spaces goes up by 1 on each row.

  n=1  n=3   n=5     n=7
   *   ***   *****   *******    row 1
        *     * *     *   *     row 2
               *       * *      row 3
                        *       row 4

   Since the row number $row$ goes up by 1 on each row, this means

        hollow = something - 2*row    and    padding = something + row.

   Plugging in a few numbers from the examples yields

        hollow = n - 2*row            and    padding = -1 + row.

   int n = in.readInt(); // size (=base) of hollow isosceles triangle
   int last = (n+1)/2;   // index of last row of triangle
   // print row 1 -- no padding spaces, n stars, advance to next line
       for (int i = 0; i < n; i++) System.out.print("*");
       System.out.println();
   // print rows 2 through last -- note, last row has only 1 star
       for (int row = 2; row <= last; row++) {
           // print row $row$
               // print row-1 padding spaces and a star
                   for (int i = 0; i < row-1; i++) System.out.print(" ");
                   System.out.print("*");
               // print n-2*row hollow spaces and (if needed) another star
                   for (int i = 0; i < n-2*row ; i++) System.out.print(" ");
                   if (row < last) System.out.print("*");
           // advance to next line
               System.out.println();
       }

   Remark 1: again the inner loops could count down instead of up.

   Remark 2: Here is another solutions for rows after the first row.
             The leftmost and rightmost stars are initially at columns
             2 and $n-1$, and "move in" by 1 on each row.  We stop
             when the leftmost and rightmost stars swap positions.
             This solution is:

   int n = in.readInt(); // size (=base) of hollow isosceles triangle
   // print row 1 -- no padding spaces, n stars, advance to next line
       for (int i = 0; i < n; i++) System.out.print("*");
       System.out.println();
   // print remaining rows
       int leftmost = 2;    // leftmost star on next row to print
       int rightmost = n-1; // rightmost star on next row to print
       while (leftmost <= rightmost) {
           int col = 1; // column to print next
           // print leftmost star
               for ( ; col < leftmost; col++) System.out.print(" ");
               System.out.print("*"); col++;
           // print rightmost star (if different from leftmost)
               for ( ; col < rightmost; col++) System.out.print(" ");
               if (leftmost != rightmost) System.out.print("*");
           // advance to next print line and move leftmost, rightmost in by 1
               System.out.println();
               leftmost++; rightmost--;
       }

For both parts (a) and (b), the code can be written super-concisely by
following this pseudocode:

    loop from row 1 until the last row
        loop from column 1 until the last column needed
            if a star is needed, then print a star, otherwise print a space
        println to go to the next row

It turns out "is a star needed?" is not too hard to answer: 

    A star is needed =  we are on row 1              
                     OR we are at the leftmost star  
                     OR we are at the rightmost star.

a)  int n = in.readInt();
    for (int row = 1; row <= n; row++) {
        for (int col = 1; col <= n; col++)
            if (row == 1 || col == row || col == n) System.out.print("*");
            else System.out.print(" ");
        System.out.println();
    }

b)  int right = in.readInt();
    for (int row = 1; row <= right; row++) {
        for (int col = 1; col<=right; col++)
            if (row == 1 || col == row || col == right) System.out.print("*");
            else System.out.print(" ");
        right--;
        System.out.println();
    }

===============================================================================
R4.6
===============================================================================

A number $m>0$ is *perfect* if it is equal to the sum of all its proper
divisors $d$ (proper means $0<d<m$), e.g. $6=1+2+3$ and $28=1+2+4+7+14$ are
perfect, but $5~=1$ and $15~=1+3+5$ are not perfect.

% read 0-terminated input sequence of positive integers one at a time and 
% print the ones that are perfect
    stopping = 0; % stopping value
    prompt = ['number (' num2str(stopping) ' to stop)? '];
    n = input(prompt); % current input value
    while n ~= stopping
        d = 1:n-1;
        d = d(rem(n,d) == 0); % proper divisors of $n$
        if n == sum(d)
            fprintf('%d is perfect', n);
        end
    end

note: $1$ is not perfect: it has no proper divisors, so the sum of its 
      perfect dvisiors is the empty sum, which is $0$.

===============================================================================
R4.7
===============================================================================

include the two methods below in class $Pile$.
note: the original code uses suit names like HEART, with no "s" at the end,
      but the solutions uses suit names like HEARTS, with an "s" at th end.

    // swap $cards[i]$, $cards[j]$
    private void swap(int i, int j) {
        Card tmp = cards[i];
        cards[i] = cards[j];
        cards[j] = tmp;
    }

    public void sortBySuit() {
            /* invariant:
        
            | 0     | c        | d         h |      s |        | size
            +-------+----------+-------------+--------+--------+-----------
            | clubs | diamonds | unprocessed | hearts | spades | unused ...
            +-------+----------+-------------+--------+--------+-----------
            |       |          |             |        |        |
            */

            int c = 0;
            int d = c;
            int s = size-1;
            int h = s;
            while (d <= h) {
                int suit = cards[h].suit();
                if (suit == Card.HEARTS) h--;
                else if (suit == Card.DIAMONDS) { swap(d,h); d++; }
                else if (suit == Card.SPADES) { swap(h,s); h--; s--; }
                // was: else { swap(c,h); swap(d,h); c++; d++; }
		else { swap(c,d); swap(c,h); c++; d++; }
            }
    }