15-100 Sections S-V / Fall 2008
Quiz 3 / 30 Minutes
Quiz Date:  Tue 23-Sep-2008

1.       Each of these Java snippets is error-free. Provide the complete trace table for each snippet..
Note: the Unicode value for ‘A’ is 65, ‘a’ is 97, and ‘0’ is 48.

a.     1  class MyCode {
 2    public static void main(String[] args) {
 3      String s1 = "abcd";
 4      String s2 = s1 + s1.substring(3);
 5      String s3 = "ef";
 6      for (int x = s2.length()-1; x >= 0; x -= s3.length()) {
 7        s3 += s2.charAt(x);
 8        System.out.println(x);
 9      }
10      System.out.println(s3);
11    }
12  }

b.    1  class MyCode {
2    public static void main(String[] args) {
3      String s = "abababa";
4      int x = 0, i = -1;
5      while ((i = s.indexOf("aba",i+1)) >= 0)
6        x += i;
7      System.out.println(x + "," + i);
8    }
9  }

2.       Short answers:

a.       What is the maximum number of guesses your number-guessing program from the homework would make if it was guessing a number between 1 and 1 billion?  In 10 words or less, explain your answer.
 

b.       In 10 words or less:  what is a sentinel?
 

c.       In 10 words or less:  How does a Java program that is using a Scanner to read from a file know when it is done reading all the data in the file?
 

3.       For each of the following snippets, state the general conditions under which they will print “true”.
Assume s1 and s2 are Strings.

a.    int x = (int)Math.signum(s1.compareTo(s2));
System.out.println(x*x > x);
 

b.    System.out.println(s2.startsWith(s1.substring(s1.length()-1)));
 

c.    String t1 = s1.replace(s2,"");
System.out.println(t1.length() == s1.length() - s2.length());
 

4.       Short methods:

a.       Write a method equivalent to Character.isLetterOrDigit that does not call any Character methods.
 

b.       Write a method equivalent to Math.floor that does not call any Math methods.
 

5.       Write isPerfect, a method takes takes an int value and returns true if it is a perfect number and false otherwise, where a perfect number equals the sum of its proper divisors.  So 6 is perfect, because its proper divisors are 1, 2, and 3, and 1+2+3=6.  8 is not perfect, because its proper divisors are 1, 2, and 4, and 1 + 2 + 4 = 7 != 8.  Note that no non-positive numbers are perfect.

public static boolean isPerfect(int n) {

}
 

6.       Bonus/Optional:
a) Write a void method named “printNearestRatio” that takes a positive double “d” and an int “maxDenominator”, and prints out the two integers x and y where x>0 and y is in [1,maxDenominator] and such that the ratio x/y is closest to d for any such values in that range.  In the event of a tie, print out the smaller quotient.

b)  [This bonus problem may only make sense if you attempted the FSM bonus in the homework.]
Draw the diagram of an FSM that accepts this language:
    a(aba)*(ab)+
Note that * means “zero or more” of the preceding values in parentheses, and “+” means “one or more” of them.  So here are some strings in this language:
    a
    aaba
    aab
    aabaabab
    aabab

Note:  You may wish to use an “epsilon” transition here – this is an edge that does not include a character – the FSM can transition across this edge without consuming an input character.

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem