CS100, Spring 2000, Solutions to Prelim 1 Review Questions

Q1. The carets (^) and dashes (-) show which line of output happened when.

       #    #     #    #   #    #    #     #   #     #     #    #    #
   +-+-#--+-#---+-#--+-#-+-#--+-#--+-#---+-#-+-#---+-#---+-#--+-#-+--#
a  |1| #  |2#   |4#  |8#1| #  |2#  |4#   |8#1| #   |2#   |4#  |8#1|  #
   +-+-#--+-#---+-#--+-#-+-#--+-#--+-#---+-#-+-#---+-#---+-#--+-#-+--#
c  | |4#  | #   | #  | # |5#  | #  | #   | # |8#   | #   | #  | # |17#
   +-+-#--+-#---+-#--+-#-+-#--+-#--+-#---+-#-+-#---+-#---+-#--+-#-+--#
bb | | #6.| #4.5| #4.| # | #9.| #6.| #5.1| # | #36.| #12.| #9.| # |  #
   +-+-#--+-#---+-#--+-#-+-#--+-#--+-#---+-#1+-#---+-#---+-#--+-#-+--#
       #  ^ #     #  ^ #   #  ^ #  ^ #     #   #     #     #  ^ #    #
          ^          ^        ^    ^                          ^       
output:   ^          ^        ^    ^                          ^       
16/64=1/4 ^          ^        ^    ^                          ^       
44/44=4/4 -----------^        ^    ^                          ^       
19/95=1/5 --------------------^    ^                          ^       
26/65=2/5 -------------------------^                          ^
49/98=4/8 ----------------------------------------------------^

Q2. // "rotate" a,b,c to get from a:A b:B c:C to a:C b:A c:B

    // solution 1:

        int tmp; // auxiliary variable
        // swap a & b to get from a:A b:B c:C to a:B b:A c:C
            tmp = b; 
            b = a; 
            a = tmp;
        // swap a & c to get from a:B b:A c:C to a:C b:A c:B
            tmp = a;
            a = c;
            c = tmp;

    // solution 2:

      int tmp; // auxiliary variable
      tmp = a;
      a = c;
      c = b;
      b = tmp;

Q3. // read a year and print whether or not the year is a leap year  
    TokenReader in = new TokenReader(System.in);
    int year = in.readInt();

    // solution 1:

        boolean check; // == "year is a leap year?"
        // Rule 1
            if (year%4 != 0) check = false;
        // Rule 2
            if (year%4 == 0) check = true;
        // Rule 3
            if (year%100 == 0) check = false;
        // Rule 4
            if (year%400 == 0) check = true;
        // print 
            if (check)
                System.out.println(year + " is a leap year");
            else
                System.out.println(year + " is not a leap year");

    Note: $if (check)$ suffices -- there is NO need for $if (check==true)$.

    // solution 2:

        if (year%4 == 0 && (year%100 != 0 || year%400 == 0))
            System.out.println(year + " is a leap year");
        else    
            System.out.println(year + " is not a leap year");

Q4. From the template/pattern example on the Examples webpage:

    // set up
        // declare and initialize variables
        // read first value
    while (not done) { 
        // process current  
        // read next value
    }                  
    // finish up          

Q5. // read number n of resistors in parallel and their resistances; print 
    // their effective resistance R using 1/R = 1/R1 + 1/R2 + ... + 1/Rn.   

    TokenReader in = new TokenReader(System.in);
    // read non-negative number n of resistors
        System.out.print("Number of resistors: ");
        int n = in.readInt();      // number of resistors 

    int j = 1;                // index of next resistance to process
    double invR = 0;          // sum so far of inverse resistances
    double Rinp;              // next resistance to process (not processed yet)
  
    // process resistances
        while (j<=n){
            System.out.print("Enter R" + j + ": ");
            Rinp = in.readDouble();
            invR = invR+1/Rinp;
            j = j+1;
        }
  
    // print effective resistance
        System.out.println("effective resistance R = " + (1/invR));

    Note: This is definite iteration, not indefinite.

Q6. // count unique values in non-decreasing grade sequence terminated by -1
    TokenReader in = new TokenReader(System.in);
    System.out.println("Enter non-decreasing sequence of grades:"); 
    int grade = in.readInt();     // next grade to process (not processed yet)
    int stoppingValue = -1;       // stopping criteria for loop
    int previous = stoppingValue; // previous entry
    int count = 0;                // number of unique entries so far
  
    // determine # of unique entries
        while (grade != stoppingValue) {
            if (grade != previous)
                count = count+1;
            previous = grade;
            grade = in.readInt();
        }
  
    // print number of unique entries
        System.out.println("Number of unique entries: " + count);

Q7. 

(A) // print 2nd largest DISTINCT value in sequence of non-zero integers

    TokenReader in = new TokenReader(System.in);
    System.out.println("Enter non-zero Integers:"); 
    int num = in.readInt();   // next value to process (not processed yet)
    int first = num;          // largest distinct value
    int second = num;         // second largest distinct value --
                              // if doesn't exist, set to first, i.e.
                              // first==second means "no 2nd largest"
    // determine 2nd largest
        while (num != 0){
           if (num>first) {
              second = first;
              first = num;
           } else if (num != first && (first==second || num>second))
              second = num;
           num = in.readInt();
        }
    
    // print 2nd largest distinct value or error message
        if (first == second)
            System.out.println("not enough distinct values for a 2nd largest");
        else
            System.out.println("Second largest distinct value: " + second);

    Note: $second$ is intialized to an impossible/illegal value to indicate
          the condition that it is not set, that it does not exist.

(B) // print 2nd largest element in sequence of non-zero integers
  
    // Input sequence of non-zero Integers 
    System.out.println("Enter non-zero Integers:"); 
    TokenReader in = new TokenReader(System.in);
    int num = in.readInt();   // next value to process (not processed yet)
    int first;                // largest value so far
    int second;               // second largest value so far
  
    if (num == 0) 
        System.out.println("No values");
    else {
        first = num;
        num = in.readInt();
        if (num == 0) 
            System.out.println("Only 1 value");
        else {
            if (num >= first) {
               second = first;
               first = num;
            } else 
                second = num;
            num = in.readInt();
            // determine second largest
                while (num != 0) {
                   if (num>=first) {
                       second = first;
                       first = num;
                   } else if (num>second)
                        second = num;
                   num = in.readInt();
                }
            // print second largest element
                System.out.println("Second largest: "+second);
        }
    }

    Note: Instead of using an impossible/illegal value for $second$ as in (A),
          here we test for boundary conditions before going into the loop.
    
    Note: $first$, $second$ are initialized (assigned a value) before their
    values are used/read -- it is an error to use a variable's value before it
    has been assigned a value.

Q8. // print max subsequence sum in a sequence of non-zero integers
    int max = 0;     // max subsequence sum so far
    int prevmax = 0; // max sum of a subsequence ending on previous value
    int next;        // next value to process -- not included in max, prevmax

    System.out.println("Enter non-zero integers:"); 
    TokenReader in = new TokenReader(System.in);
    next = in.readInt();

    // solution 1: empty sequences not allowed

        if (next == 0)
            System.out.println("No values");
        else {
            // determine max subsequence sum
                while (next != 0) {
                    prevmax = Math.max(prevmax+next, next);
                    max = Math.max(prevmax, max);
                    next = in.readInt();
                }
            // print max subsequence sum
                System.out.println(max);
        }

    // solution 2: empty sequences allowed

        // determine max subsequence sum
            while (next != 0) {
                prevmax = Math.max(prevmax+next, 0);
                max = Math.max(prevmax, max);
                next = in.readInt();
            }
        // print max subsequence sum
            System.out.println(max);

    Note: You could use conditionals instead of $Math.max$.
          (On Prelim 1, we would tell/remind you about $Math.max$.)

    Note: In all the sample solutions here, the comments for variables used in
    a loop are intended to be true ONLY when the loop test is evaluated,
    i.e. BEFORE and AFTER each iteration (execution of the loop body).  A way
    to think about this is as follows:

    + Open your eyes when the loop test is evaluated.
      The variable definitions had better be true.

    + Close your eyes during execution of the loop body:  Pretend not to notice
      if the variable definitions are temporarily made false.  The idea is, you
      don't care how/what the loop body does as long as those variable
      definitions become true again by the time the loop test is reached.

    Thus, $prevmax$ involves only the previous value, not the value in $next$.