CS100M Spring 2001      Prelim T2: Questions and *Java* Solutions      April 10

Q1. Use box scope diagrams to trace execution of the main method below.
    You may omit $args$ entirely.

    public class Q1 {
        public static int five() {
            return 5;
        }

        public static void main(String[] args) {
            System.out.println(a(1,1));
        }

        public static int a(int m, int n) {
            if (m == 0) {
                return n + 1; 
            } else if (n == 0) {
                return a(m-1, 1); 
            } else {
                return a(m-1,a(m, n-1)); 
            }
        }
    }

detailed trace:

class Q1    |  class Q1     |  class Q1            |  class Q1               
++======++  |  ++=======++  |  ++==============++  |  ++===================++
|| five ||  |  || five  ||  |  || five         ||  |  || five              ||
|| main ||  |  || main  ||  |  || main         ||  |  || main              ||
|| a    ||  |  || a     ||  |  || a            ||  |  || a                 ||
++======++  |  ||       ||  |  ||              ||  |  ||                   ||
            |  || main  ||  |  || main  a(1,1) ||  |  || main  a(1,1)      ||
            |  || +---+ ||  |  || +---+ +----+ ||  |  || +---+ +---------+ ||
            |  || |   | ||  |  || |   | |    | ||  |  || |   | |   +---+ | ||
            |  || +---+ ||  |  || +---+ +----+ ||  |  || +---+ | m | 1 | | ||
            |  ++=======++  |  ++==============++  |  ||       |   +---+ | ||
            |               |                      |  ||       |   +---+ | ||
            |               |                      |  ||       | n | 1 | | ||
            |               |                      |  ||       |   +---+ | ||
            |               |                      |  ||       +---------+ ||
            |               |                      |  ++===================++
____________|_______________|______________________|___________________________
                                |
class Q1                        |  class Q1                           
++==========================++  |  ++===============================++
|| five                     ||  |  || five                          ||
|| main                     ||  |  || main                          ||
|| a                        ||  |  || a                             ||
||                          ||  |  ||                               ||
|| main  a(1,1)      a(1,0) ||  |  || main  a(1,1)      a(1,0)      ||
|| +---+ +---------+ +----+ ||  |  || +---+ +---------+ +---------+ ||
|| |   | |   +---+ | |    | ||  |  || |   | |   +---+ | |   +---+ | ||
|| +---+ | m | 1 | | +----+ ||  |  || +---+ | m | 1 | | | m | 1 | | ||
||       |   +---+ |        ||  |  ||       |   +---+ | |   +---+ | ||
||       |   +---+ |        ||  |  ||       |   +---+ | |   +---+ | ||
||       | n | 1 | |        ||  |  ||       | n | 1 | | | n | 0 | | ||
||       |   +---+ |        ||  |  ||       |   +---+ | |   +---+ | ||
||       +---------+        ||  |  ||       +---------+ +---------+ ||
++==========================++  |  ++===============================++
________________________________|____________________________________________

class Q1               
++======================================++
|| five                                 ||
|| main                                 ||
|| a                                    ||
||                                      ||
|| main  a(1,1)      a(1,0)      a(0,1) ||
|| +---+ +---------+ +---------+ +----+ ||
|| |   | |   +---+ | |   +---+ | |    | ||
|| +---+ | m | 1 | | | m | 1 | | +----+ ||
||       |   +---+ | |   +---+ |        ||
||       |   +---+ | |   +---+ |        ||
||       | n | 1 | | | n | 0 | |        ||
||       |   +---+ | |   +---+ |        ||
||       +---------+ +---------+        ||
++======================================++
_______________________________________________________________________________

class Q1               
++===========================================++
|| five                                      ||
|| main                                      ||
|| a                                         ||
||                                           ||
|| main  a(1,1)      a(1,0)      a(0,1)      ||
|| +---+ +---------+ +---------+ +---------+ ||
|| |   | |   +---+ | |   +---+ | |   +---+ | ||
|| +---+ | m | 1 | | | m | 1 | | | m | 0 | | ||
||       |   +---+ | |   +---+ | |   +---+ | ||
||       |   +---+ | |   +---+ | |   +---+ | ||
||       | n | 1 | | | n | 0 | | | n | 1 | | ||
||       |   +---+ | |   +---+ | |   +---+ | || 
||       |         | |         | | return 2| ||
||       +---------+ +---------+ +---------+ ||
++===========================================++
_______________________________________________________________________________
                                     |
class Q1                             |  class Q1                           
++===============================++  |  ++===============================++
|| five                          ||  |  || five                          ||
|| main                          ||  |  || main                          ||
|| a                             ||  |  || a                             ||
||                               ||  |  ||                               ||
|| main  a(1,1)      a(1,0)      ||  |  || main  a(1,1)      a(0,2)      ||
|| +---+ +---------+ +---------+ ||  |  || +---+ +---------+ +---------+ ||
|| |   | |   +---+ | |   +---+ | ||  |  || |   | |   +---+ | |         | ||
|| +---+ | m | 1 | | | m | 1 | | ||  |  || +---+ | m | 1 | | |         | ||
||       |   +---+ | |   +---+ | ||  |  ||       |   +---+ | |         | ||
||       |   +---+ | |   +---+ | ||  |  ||       |   +---+ | |         | ||
||       | n | 1 | | | n | 0 | | ||  |  ||       | n | 1 | | |         | ||
||       |   +---+ | |   +---+ | ||  |  ||       |   +---+ | |         | || 
||       |         | | return 2| ||  |  ||       |         | |         | ||
||       +---------+ +---------+ ||  |  ||       +---------+ +---------+ ||
++===============================++  |  ++===============================++
_____________________________________|________________________________________
                                     |
class Q1                             |  class Q1                           
++===============================++  |  ++===============================++
|| five                          ||  |  || five                          ||
|| main                          ||  |  || main                          ||
|| a                             ||  |  || a                             ||
||                               ||  |  ||                               ||
|| main  a(1,1)      a(0,2)      ||  |  || main  a(1,1)      a(0,2)      ||
|| +---+ +---------+ +---------+ ||  |  || +---+ +---------+ +---------+ ||
|| |   | |   +---+ | |   +---+ | ||  |  || |   | |   +---+ | |   +---+ | ||
|| +---+ | m | 1 | | | m | 0 | | ||  |  || +---+ | m | 1 | | | m | 0 | | ||
||       |   +---+ | |   +---+ | ||  |  ||       |   +---+ | |   +---+ | ||
||       |   +---+ | |   +---+ | ||  |  ||       |   +---+ | |   +---+ | ||
||       | n | 1 | | | n | 2 | | ||  |  ||       | n | 1 | | | n | 2 | | ||
||       |   +---+ | |   +---+ | ||  |  ||       |   +---+ | |   +---+ | ||
||       |         | |         | ||  |  ||       |         | | return 3| ||
||       +---------+ +---------+ ||  |  ||       +---------+ +---------+ ||
++===============================++  |  ++===============================++
_____________________________________|________________________________________

class Q1                 |  class Q1                 
++===================++  |  ++=======++  
|| five              ||  |  || five  ||  
|| main              ||  |  || main  ||  
|| a                 ||  |  || a     ||  
||                   ||  |  ||       ||  
|| main  a(1,1)      ||  |  || main  ||  
|| +---+ +---------+ ||  |  || +---+ ||  output: 3
|| |   | |   +---+ | ||  |  || |   | ||  
|| +---+ | m | 1 | | ||  |  || +---+ ||  
||       |   +---+ | ||  |  ||       ||  
||       |   +---+ | ||  |  ||       ||  
||       | n | 1 | | ||  |  ||       ||  
||       |   +---+ | ||  |  ||       ||  
||       | return 3| ||  |  ||       ||  
||       +---------+ ||  |  ||       ||  
++===================++  |  ++=======++  
          
===============================================================================

Q2. Write a function $grad(v)$ to take a vector $v$ of $int$s and return
    "$v$'s gradient is strictly increasing?".

matlab solution:

    function ans = grad(v)
    % ans = grad(v): return "gradient of $v$ is strictly increasing?"
    
        ans = logical(1); % answer so far   <-- $logical$ not required
        i = 1;        
        % check pairs of successive differences; 
        % stop if find pair that is not strictly increasing
        while ans & i <= length(v)-2
            ans = ans & v(i+2) - v(i+1) > v(i+1) - v(i);
            i = i+1;
        end

java solution:

    // "$v$'s gradient is strictly increasing?"
    public static boolean grad(int[] v) {
        boolean ans = true; // answer so far
        int i = 0;
        // check pairs of successive differences; 
        // stop if find pair that is not strictly increasing
        while (ans && i < v.length-2) {
            ans = ans & v[i+2] - v[i+1] > v[i+1] - v[i];
            i += 1;
        }
    }

Q3. omitted.

Q4. part of project P6.