CS100, Spring 2000, Solutions to Review questions for Prelim 2

1. You were not asked to explain the errors (only fix them), but we included
   explanations here for your benefit.

   CORRECT                              | INCORRECT
   int x = 3;                           | int 3 = x;
       #   #                            |     #   #
                                        | 
   The line above is shorthand for      | 
                                        | 
        int x; x = 3;                   | 
                                        | 
   i.e. declare a variable x and assign | 
   to it an initial value of 3.  Keep   | 
   in mind that an assignment statement | 
   is not symmetric:                    | 
                                        | 
        destination = source;           | 
                                        | 
                                        | 
   if (7 - x == 4)                      | if (7 - x = 4)
             ##                         |           #
                                        | 
   Do not confuse equality "==" with    | 
   assignment "=".                      | 
                                        | 
                                        | 
   System.out.println("four is " + 4);  | System.Out.Println("four is " + 4);
          #   #                         |        #   #
                                        | 
   Java is case-sensitive.              | 
                                        | 
   x = 4;                               | int x = "4";
                                        | ###     # #
                                        | 
                                        | The line above is shorthand for
                                        | 
                                        |         int x; x = "4";
                                        | 
                                        | which means it tries to redeclare
                                        | variable x and tries to assign a
                                        | String to this int variable.  Java
                                        | does not allow either of these.
                                        | 
                                        | 
   if (3<4 && 4<5)                      | (3<4, 4<5)
           ##                           |     #
                                        | 
   Java uses "&&" for "and".            | 
                                        | 
                                        | 
       System.out.println("4 is ...");  |     System.out.println(4 is ...);
                          #        #    | 
                                        | 
   Double quotes (", not ') are needed  | 
   for a String.                        |

2. 

(a) $==$ is for equality and is symmetric: $x == 3$ is the same as $3 == x$

    $=$ is for assignment and is asymmetric: 
    $x = y;$ means put the value of y into variable x. 
    $y = x;$ means put the value of x into variable y.

(b) i)   int x;      // declare variable x: "create a box named x"
    ii)  int x = 3;  // declare variable x and put 3 into it
    iii) x = 3;      // put 3 into variable x, which already exists

(c) Java is case-sensitive, so $fred$ and $Fred$ are different identifiers
    (an identifier is the name of a variable, method, or class).

(d) Here are two ways.
                                while (x<0)         
    while (x<0) {               {                   
        counter *= 10;              counter *= 10;  
        if (y<z)                    if (y<z)        
            y++;                        y++;        
        else                        else            
            z = z*2;                    z = z*2;    
        x = x+2;                    x = x+2;        
        w = w/7;                    w = w/7;        
    }                           }                   

3. 
a) Ignore the base.

   Observe that the number of "hollow" spaces goes down by 1 on each row,
   whereas the number of "padding" spaces goes up by 1 on each row.

 n=1  n=2  n=3    n=4      n=5
   *  **   ***    ****     *****    row 1
       *    **     * *      *  *    row 2
             *      **       * *    row 3
                     *        **    row 4
                               *    row 5

   Since the row number $row$ goes up by 1 on each row, this means

        hollow = something - row    and    padding = something + row.

   Plugging in a few numbers from the examples yields

        hollow = n-1 - row          and    padding = -1 + row.

   Another way to think about this (think back to Exercise 3) is that
   the position of the leftmost star on a row is in column $row$
   (think of columns starting at 1, not 0), so $row-1$ "padding"
   spaces need to be printed.  The position of the rightmost star is
   in column $n$, so $n-row-1$ "hollow" spaces need to be printed
   between them.

   int n = in.readInt(); // size (= base = # of rows) of hollow right-triangle
   // print row 1 -- no padding spaces, n stars; advance to next line
       for (int i = 0; i < n; i++) System.out.print("*");
       System.out.println();
   // print rows 2 through n -- note: row n has only 1 star
       for (int row = 2; row <= n; row++) {
           // print row $row$
               // print row-1 padding spaces and a star
                   for (int i = 0; i < row-1; i++) System.out.print(" ");
                   System.out.print("*");
               // print n-row-1 hollow spaces and (if needed) another star
                   for (int i = 0; i < n-row-1; i++) System.out.print(" ");
                   if (row < n) System.out.print("*");
           // advance to next line
               System.out.println();
       }

   Remark 1: the inner loops could "count down" instead of "count up":

                   for (int i = row-1; i > 0 ; i--) System.out.print(" ");
             and
                   for (int i = n-row+1; i > 0 ; i--) System.out.print(" ");

   Remark 2: to be more like our sample solution to Exercise 3, the
             body of the outer loop could be something like this:

               int col = 1; // next column to print
               // print leftmost star
                   for ( ; col < row; col++) System.out.print(" ");
                   System.out.print("*"); col++;
               // print rightmost star (if different from leftmost)
                   for ( ; col < n ; col++) System.out.print(" ");
                   if (row != n) System.out.print("*");
               System.out.println();

b) Observe that the number of "hollow" spaces goes down by 2 on each row,
   whereas the number of "padding" spaces goes up by 1 on each row.

  n=1  n=3   n=5     n=7
   *   ***   *****   *******    row 1
        *     * *     *   *     row 2
               *       * *      row 3
                        *       row 4

   Since the row number $row$ goes up by 1 on each row, this means

        hollow = something - 2*row    and    padding = something + row.

   Plugging in a few numbers from the examples yields

        hollow = n - 2*row            and    padding = -1 + row.

   int n = in.readInt(); // size (=base) of hollow isosceles triangle
   int last = (n+1)/2;   // index of last row of triangle
   // print row 1 -- no padding spaces, n stars, advance to next line
       for (int i = 0; i < n; i++) System.out.print("*");
       System.out.println();
   // print rows 2 through last -- note, last row has only 1 star
       for (int row = 2; row <= last; row++) {
           // print row $row$
               // print row-1 padding spaces and a star
                   for (int i = 0; i < row-1; i++) System.out.print(" ");
                   System.out.print("*");
               // print n-2*row hollow spaces and (if needed) another star
                   for (int i = 0; i < n-2*row ; i++) System.out.print(" ");
                   if (row < last) System.out.print("*");
           // advance to next line
               System.out.println();
       }

   Remark 1: again the inner loops could count down instead of up.

   Remark 2: again, we could use a solution more similar to that of
             Exercise 3.  Ignore the base.  The leftmost and rightmost
             stars are initially at columns 2 and $n-1$, and "move in"
             by 1 on each row.  We stop when the leftmost and
             rightmost stars swap positions.  This solution is:

   int n = in.readInt(); // size (=base) of hollow isosceles triangle
   // print row 1 -- no padding spaces, n stars, advance to next line
       for (int i = 0; i < n; i++) System.out.print("*");
       System.out.println();
   // print remaining rows
       int leftmost = 2;    // leftmost star on next row to print
       int rightmost = n-1; // rightmost star on next row to print
       while (leftmost <= rightmost) {
           int col = 1; // column to print next
           // print leftmost star
               for ( ; col < leftmost; col++) System.out.print(" ");
               System.out.print("*"); col++;
           // print rightmost star (if different from leftmost)
               for ( ; col < rightmost; col++) System.out.print(" ");
               if (leftmost != rightmost) System.out.print("*");
           // advance to next print line and move leftmost, rightmost in by 1
               System.out.println();
               leftmost++; rightmost--;
       }
 
4. // print perfect numbers in a sequence of positive integers
   int n = in.readInt(); // next input to process
   while (n!=0) {                   
       int sum = 0; // sum so far of proper divisors d of n
       for (int d=1; d<n; d++)    
           if (n % d == 0)        
               sum += d;          
       if (sum == n)              
           System.out.println(n); 
       n = in.readInt();          
   }                                

5. [updated 3/17]

   // Draw the contents of a window $w$ pixels wide, $h$ pixels high:
   // erase the contents, and then draw 3 filled-in, randomly placed
   // but fully visible circles:
   //  a Color.yellow circle of radius 10,
   //  a Color.cyan circle of radius 20, and
   //  a Color.magenta circle of radius 30.
   void paint(Graphics g, int w, int h) {
           g.clearRect(0, 0, w, h);
           int r, x, y; // radius r and center (x,y) of circle to draw next
           r = 10;
           x = r + (int) (Math.random * (w-2*r));
           y = r + (int) (Math.random * (h-2*r));
           g.setColor(Color.yellow);
           g.fillOval(x-r, y-r, 2*r, 2*r);
           r = 20;
           x = r + (int) (Math.random * (w-2*r));
           y = r + (int) (Math.random * (h-2*r));
           g.setColor(Color.cyan);
           g.fillOval(x-r, y-r, 2*r, 2*r);
           r = 30;
           x = r + (int) (Math.random * (w-2*r));
           y = r + (int) (Math.random * (h-2*r));
           g.setColor(Color.magenta);
           g.fillOval(x-r, y-r, 2*r, 2*r);
       }
   }

   Remark: the redundancy here cries out for the use of methods.

6. 

a) x=y; y=z;               Output: 2, 3, 3 on separate lines
b) x=y; y.k=z.k;           Output: 3, 3, 3 on separate lines
c) x.k=y.k; y.k=z.k;       Output: 2, 3, 3 on separate lines

class Person{
    int k;
    void print() { System.out.println(k); }
} 


public class Equal_notEqual {
    public static void main(String[] args) {
        Person x = new Person(), y = new Person(), z = new Person(); 
        x.k = 1; y.k = 2; z.k = 3; 
        // ***replace this line***
        x.print(); y.print(); z.print(); 
    }
} 

7. [Too hard to show in plain text]

8.  note: we assume #test>=1 and #projects>=1.

    public class Question8 {
        public static void main(String[] args) {
            TokenReader in = new TokenReader(System.in);
            int ntest = in.readInt(); // # of tests
            int nproj = in.readInt(); // # of projects
            int score = in.readInt(); // next test or project score to process
            double max = -1;          // max course score so far
            // process test and project scores for each student
            while (score>0) {
                double tottest = 0.0; // sum of student's test scores so far
                double totproj = 0.0; // sum of student's project scores so far
                // process test scores
                    tottest += score;
                    for (int i = 1; i < ntest; i++)
                        tottest += in.readInt();
                // process project scores
                    for (int i = 0; i < nproj; i++) {
                        score = in.readInt();
                        totproj += (score/10) + (score%10);
                    }
                // update max course score so far
                    max = Math.max(max, 
                               0.8 * tottest/ntest + 20 * (totproj/nproj/10));
                score = in.readInt();
            }
            if (max<0) System.out.println("no students");
            else System.out.println("max course score is " + max);
        }
    }

9.  class Folder {
        String name;
        Folder enclosing;
        Folder subfolder; // subfolder and companion are used like 
        Folder companion; // youngestChild and olderSibling in Project 4
                          // to link all subfolders in an enclosing Folder
        // create a folder with 0 subfolders, name n, enclosed within folder e;
        // establish appropriate subfolder and companion links
        Folder(String n, Folder e) {
            name = n;
            enclosing = e;
            if (e != null) { companion = e.subfolder; e.subfolder = this; }
        }
        // return the desktop
        Folder desktop() {
            Folder top = this;
            while (top.enclosing != null) top = top.enclosing;
            return top;
        }
        // print names of immediate subfolders
        void list() {
            System.out.println("Subfolders of " + name + ":");
            for (Folder next = subfolder; next != null; next = next.companion)
                System.out.println(next.name);
            System.out.println("end of listing");
        }
        // return pathname
        String pathname() {
            String s = "";
            for (Folder next = this; next != null; next = next.enclosing)
                s = next.name + "/" + s; // <-- note: cannot use $+=$
            return s;
        }
    }

/*
             MyDisk
              /  \
             /    \
            /      \
          TV    Courses
         / |       / \
        /  |      /   \
       /   |     /     \
    Buffy Angel CS100  Psych 101
               / | | \
              /  | |  \
             /   / \   \
           P1  P2   P3  P4
                       / \
                      /   \
                     old  new
*/

    public class Question9 { // <-- review question asked for Question8.  oops!
        public static void main(String[] args) {
            Folder mydisk, tv, courses, cs100, p4;
            mydisk = new Folder("MyDisk", null);
            tv = new Folder("TV", mydisk);
            new Folder("Buffy", tv); new Folder("Angel",tv);
            courses = new Folder("Courses", mydisk);
            cs100 = new Folder("CS100", courses);
            new Folder("P1",cs100); new Folder("P2",cs100);
            new Folder("P3",cs100); p4 = new Folder("P4",cs100); 
            new Folder("old", p4); new Folder("new", p4);
            new Folder("Psych 101", courses);
            System.out.println(cs100.pathname());
            cs100.list();
        }
    }

[added 3/17]

/******************************************************************************
The solution above used constructors.  Below is the body of $main$ rewritten
if we had deleted the constructor:

        Folder(String n, Folder e) {
            name = n;
            enclosing = e;
            if (e != null) { companion = e.subfolder; e.subfolder = this; }
        }

The code below is written to closely parallel the deleted constructor.

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

Folder mydisk, tv, courses, cs100, p4, tmp;
// mydisk = new Folder("MyDisk", null);
    mydisk = new Folder(); mydisk.name = "MyDisk"; 
    mydisk.enclosing = null; // <-- not needed
// tv = new Folder("TV", mydisk);
    tv = new Folder(); tv.name = "TV"; tv.enclosing = mydisk;
    tv.companion = mydisk.subFolder; // <-- not needed
    mydisk.subFolder = tv;
// new Folder("Buffy", tv); 
    tmp = new Folder(); tmp.name = "Buffy"; tmp.enclosing = tv;
    tmp.companion = tv.subFolder; // <-- not needed
    tv.subFolder = tmp;
// new Folder("Angel",tv);
    tmp = new Folder(); tmp.name = "Angel"; tmp.enclosing = tv;
    tmp.companion = tv.subFolder; tv.subFolder = tmp;
// courses = new Folder("Courses", mydisk);
    courses = new Folder(); courses.name = "Courses"; course.enclosing= mydisk;
    courses.companion = mydisk.subFolder; mydisk.subFolder = courses;
// cs100 = new Folder("CS100", courses);
    cs100 = new Folder(); cs100.name = "CS100"; cs100.enclosing = courses;
    cs100.companion = courses.subFolder; // <-- not needed
    courses.subFolder = cs100;
// new Folder("P1",cs100); 
    tmp = new Folder(); tmp.name = "P1"; tmp.enclosing = cs100;
    tmp.companion = cs100.subFolder; // <-- not needed
    cs100.subFolder = tmp;
// new Folder("P2",cs100);
    tmp = new Folder(); tmp.name = "P2"; tmp.enclosing = cs100;
    tmp.companion = cs100.subFolder; cs100.subFolder = tmp;
// new Folder("P3",cs100); 
    tmp = new Folder(); tmp.name = "P3"; tmp.enclosing = cs100;
    tmp.companion = cs100.subFolder; cs100.subFolder = tmp;
// new Folder("P4",cs100); 
    p4 = new Folder(); p4.name = "P4"; p4.enclosing = cs100;
    p4.companion = cs100.subFolder; cs100.subFolder = p4;
// new Folder("old", p4); 
    tmp = new Folder(); tmp.name = "old"; tmp.enclosing = p4;
    tmp.companion = p4.subFolder; // <-- not needed
    p4.subFolder = tmp;
// new Folder("new", p4); 
    tmp = new Folder(); tmp.name = "new"; tmp.enclosing = p4;
    tmp.companion = p4.subFolder; p4.subFolder = tmp;
// new Folder("Psych 101", courses);
    tmp = new Folder(); tmp.name = "Psych 101"; tmp.enclosing = courses;
    tmp.companion = courses.subFolder; courses.subFolder = tmp;
System.out.println(cs100.pathname());
cs100.list();

******************************************************************************/