Name: ________________________________

CSE373 Spring Quarter
University of Washington
Miniquiz #7
April 20, 2005
Closed book, closed notes, closed neighbor; no calculators
1 point per part except as noted

.
What is the value of this postfix expression?

4   5    +    2    * 
  1. 9
  2. 11
  3. 13
  4. 14
  5. 18 
  6. 22
  7. 28
  8. 40
  9. illegal expression -- too many operands
  10. illegal expression -- too many operators
D. The infix equivalent is (4 + 5) * 2 = 18
 
.
When evaluating a postfix expression using the stack-based algorithm, what does it mean when all of the input has been processed and the stack contains exactly one value? 
  1. no error
  2. an error has occurred
no error
 
 
.
When checking for balanced parentheses using the stack-based algorithm, if the current input symbol is a right paren, the correct action is ...
  1. push a right paren on the stack
  2. push a left paren on the stack
  3. pop the stack; the value popped should be a right paren
  4. pop the stack; the value popped should be a left paren
  5. pop the stack twice and compare the two popped values                                      
D
 
 
. (1 pt. each)
Which one of these is the best?  Which one is worst?  Write B or W next to your choices.  ("Best" implies asymptotically smallest in questions like these).
  1. ___ 2n 
  2. ___ 10 + 3n2 + 2n3            
  3. ___ n log n
  4. ___ 4
  5. ___ 0.55 log n
  6. ___30n                                  
 
. (1 pt. each)
Fill in the blanks in this definition (from the slides):

 Definition: Let T and f be functions of the natural numbers. T(n) is in _______ if there are constants c and n0 such that T(n) < cf(n) for all _______.
O(f(n) or just O(f)

n >= n0 or n > n0

 
. (1 pt. each)
Study this method:
static int mystery (int input) {
     if (input < 0) {
          return -mystery(-input);
     } 
     if (input <= 1) {
          return 0;
     }
     return 1 + mystery(input/3);
}
  

What is the value of mystery(10) ? ______

 

What is the value of mystery(-4) ? ______

mystery(10) = 1 + mystery(3) = 1 + (1 + mystery(1)) = 1 + 1 + 0 = 2

mystery(-4) = -mystery(4) = -(1 + mystery(1)) = -(1 + 0) = -1 
 
. (bonus question -- 1 free pt.)
True or False: according to the syllabus, the lowest midterm will be dropped.  So if you oversleep on Friday, it's no big deal.

 

. (not graded)
Suppose you are asked to implement the following method recursively (no loops):
/** Return true if and only the array is
        non-null, non-empty, and contains only positive numbers. */
        static boolean isAllPos(double nums[]);

Think about implementing this method.  Then either

A. if you feel that isAllPos can be implemented recursively without a helper method, and without any library classes or methods, give full code for implementing isAllPos

OR

B. explain why isAllPos cannot be implemented without a helper method.

 

 

 
isAllPos is not suitable for a direct recursive implementation.  There is nothing in the parameters which allows one to keep track of how much of the array has been checked.  A suitable helper method might be this one:

/** return true iff the all the values in the array, from the position given

to the end, are positive. */

static boolean isPos(double[] nums, int position);

With this helper, you could implement isPos as follows (you did not have to give this code as part of your answer, however!)

{

if (nums == null || nums.length == 0) return false;

return isPos(nums, 0);

}