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

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

A *closed* *interval* is a contiguous set of the real numbers:

    [a..b] = { x | a <= x <= b }

Special cases are the empty set (e.g. $[2..1]$) 
and a single point (e.g. $[1..1]$).

Suppose we want the following operations:
___ create an interval
___ compute the intersection of two intervals
___ test containment (whether the second interval is a subset of the first)
___ display/describe an interval

Further suppose:

___ we do not want any other operations on intervals
    except for combinations of the operations above.

Bonus: Implement general intervals, i.e. allow all four of these cases:

    [a..b] = { x | a <= x <= b }
    ]a..b[ = { x | a < x < b }
    ]a..b] = { x | a < x <= b }
    [a..b[ = { x | a <= x < b }

a) What are some test cases that should be tried to see that the code works?

b) ___ Write Matlab functions to implement the 4 operations on closed 
   intervals and explain either ___ how you disallow other operations or 
   ___ why you are unable to disallow other operations.

   ___ Also write a small script that uses all 4 operations.

c) ___ Write a Java class to implement closed intervals with only the 4
   operations listed above.  ___ Include a main method that uses all 4
   operations.

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

a) Fill in the blanks below to complete Java method $min$.  All matrices
   are ___ non-empty, ___ rectangular, ___ row-major, and hold ___ integers.
   ___ Pay attention to comments!

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 = _______________ ;

      ____________________ m = ______________________________________________ ;

      while ( ___________________________________________ ) {

          // 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 = _______________ ;
          
          int row = _______________ ;

          while ( _______________________ ) {

              if ( _________________________________________ ) // new minimum?

                  pos = _________________ ;

              row += ______________ ; // advance to next row
          }

          _____________ = _______________________ ; // record minimum

          _____________ = _______________________ ; // record position

          col += __________________ ; // advance to next column
      }
      return _________________ ;
  }

  // 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) Suppose Matlab did not have $min$ or $max$ or $sort$. Write Matlab 
   function $min$: duplicate the functionality of the built-in $min$
   for vectors and matrices.

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

Consider a class $Creature$ for creatures that have a $name$, can $speak$,
and can $act$ and a $main$ method that creates four $Creature$s and has
each $act$ five times:

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

Observe the use of an array to reduce redundancy.

Define the sub-classes as specified below.
___ Use good style.
___ Use $super$ as appropriate to invoke the constructor of a super-class
    and to invoke an implementation inherited from a super-class.

a) Class $Cat$ is a sub-class of $Creature$:
   ___ Method $speak$: $meow$ instead of $speak$, e.g. $Fluffy meows$
       instead of $Fluffy speaks$.
   ___ Integer field $purrLength$: the non-negative number of $r$s in a purr.
       Do not allow code outside of class $Cat$ access this variable directly.
   ___ Method $purr$: purr with $purrLength$ r's, e.g. $Sleepy purrrrrs$ has 
       5 r's.
   ___ Method $act$: randomly (50-50) choose between the original $act$ of a 
       $Creature$ and the new action $purr$.  Write your code so that if 
       $Creature.act$ were changed, then $Cat.act$ would inherit the changes.

b) Class $Dog$ is a sub-class of $Creature$:

    ___ Integer field $wags$: how many times the dog has already wagged its
	tail.
    ___ Method $speak$: $woof$ instead of $speak$.
    ___ Method $wag$: $wag$ and print the number of times its tail has wagged,
	e.g. $Butch wags its tail for the 1-th time$.
    ___ Method $act$: (like $Cat.act$) randomly (50-50) choose between the 
	original $act$ of a $Creature$ and the new action $wag$.

c) Class $DogCow$ is a sub-class of $Dog$:

    ___ Every $DogCow$ is named $Clarus$.  
    ___ Method $speak$: randomly (50-50) choose between how
        a Dog normally speaks and saying $moof$.

d) Modify method $main$ to make 
       ___ a $Dog$ named $Butch$,
       ___ a $Cat$ named $Fluffy$ with purr length 3,
       ___ a $Cat$ named $Sleepy$ with purr length 7,
       ___ and a $DogCow$ $Clarus$.
   ___ Each Creature should still $act$ 5 times.

HINT: Here is a solution to $Cat$.

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

===============================================================================
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) Write a static Java method $fliplr$ such that a call $fliplr(a);$ is
   roughly equivalent to the Matlab statement $a = fliplr(a);$ for a
   1-dimensional array $a$ of characters.  

   ___ Do *not* create any additional arrays: just modify the parameter.

___ For the parts (b)-(e), assume $fliplr$ is available and works correctly.

b) The test $s == fliplr(s)$ would not work in either Matlab or Java for
   testing whether $s$ is a palindrome.  Why not?

   ___ Explain why it does not work in Matlab.
   ___ Explain how to fix it so that it is valid Java code.
   ___ Explain why, once fixed to be valid Java code, the code does not work.

c) Write a static Java function $ispalindrome$ such that $ispalindrome(s)$
   returns the boolean answer to "is string $s$ a palindrome?"  In the body 
   of the function, compute the answer in two different ways and print an
   error message if they disagree.  The two ways are:

   ___ Use $fliplr$ but no loops.
   ___ Use loops but not $fliplr$.
   ___ Give a useful and correct invariant for each loop.

d) Write a Matlab function $ispalindrome$.

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

a) Write Java code to read a positive integer n from input and print a 
   hollow n-triangle.  Examples for 1, 2, 3, 4, 5 are shown below.
   
   __ Assume $TokenReader in = new TokenReader(System.in);$
      has already been included.
   __ Use good style.
   __ Clearly indicate in a comment how many "hollow" spaces you
      intend to print on each line.
   __ Clearly indicate in a comment how many "padding" spaces you
      intend to on each line before the first star.
   __ No arrays.  
   __ No strings of unbounded length.

   *  **   ***    ****     *****
       *    **     * *      *  *
             *      **       * *
                     *        **
                               *

b) Same situation as (a), but ___ assume $n$ is odd, 
   and ___ print isosceles triangles, as shown below for 1, 3, 5, 7.

   *   ***   *****   *******
        *     * *     *   *
               *       * *
                        *

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

Write Matlab code to read a 0-terminated input sequence of positive
integers one at a time and print out only the *perfect* numbers.

__ Use good style.
__ Use the pattern for processing input with a stopping value.
__ No arrays.  No user-defined functions.  No error-checking.
__ Prompt the user for input.

HINT: is $1$ perfect?

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

Modify the $Pile$ code from project P7 to include a method $sortBySuit$
that sorts cards such that all cards of the same suit occur together, in
the order clubs, diamonds, hearts, spades.  ___ Do *not* use any additional
arrays: just modify elements of instance variable $cards$.