Lab 7 Strategy Session

Monday March 3, 2007
5pm - 8pm
@ Phelp 1413
The show starts at 5:40pm*

This will replace my office hours on Thursday.

* I will be there at 5pm. I will be eating my dinner and answering your questions. I will start talking about Lab 7 Strategy at 5:40pm. The talk may be about 60 - 90 mins.

Tentative Outline

1. The math needed
   For those who already know how to write this program but get stuck on Math.
2. How spiral example works
   Understanding how the spiral application (in the book) works.
   
3. Basic hints
   Aimed at putting you in the right mindset to do the lab yourself. If you don't want to spoil the challenge, you should leave after this.
4. More hints
   More detailed hints, suggested design. Warning: the fun could be spoiled. But you still need to understand what's going on in order to write the code.
   
5. Even more hints? Nah... But let's look at some other examples.
   What if the lab is a Sierpinski Gasket? or a fractal tree?
   
6. Questions

I can stick around a little after 8pm if people need me.

- Mock

Lab 7 Strategy Session

Dear cs10 Students,

Lab 7 seems to be tricky to many people, although it will not be much of a code change from the spiral example. I encourage you all to start early.

At least, please (please, please) read the lab and try to understand the example code by this weekend. Type it in your computer, run it, appreciate it, modify it to look differently. Play around with it. Try to understand how the code works.

Next, please read my Notes for Week #7 (previous post). Toward the end, I wrote about Sierpinski Gasket (which I didn't get to in the session yesterday). This, together with the spiral example in the book, can provide an insight into how you approach your lab.

Now, I would like to take a vote from you. If you care (:P), please reply to this email with answers to the following questions:
[1] Should I reschedule my office hours next week to Monday?
[2] If so, what time on Monday works for you?

I will call it a "Lab 7 Strategy Session" where I will provide "incremental hints" to those who need. You can come in, take some ideas, and leave (so you won't be spoiled by the hints). Or you can stick around to see more concrete examples of (other similar kinds of) fractals.

Have a nice weekend :)
- Mock

Lab Grades

Dear Students:

If you are not satisfied with your lab grade (that was graded by me), especially for the functionality part, please read this email.

Grade disputes can be done in person by visiting my office hours: Thursday from noon - 3pm at Phelp 1413. If you cannot come in during that time, you can grab me after my discussion session on Wednesday from 4-5pm at Phelp 1445. If you still cannot make it, we can make an appointment.

In general, there will be a standard 10 points deduction for the "CODE DOES NOT COMPILE" or "CODE NOT EMAILED" situation. But if you need to change your code a lot, the deduction can be more. Of course, if you can show me that it is not at all your fault, then you will get your points back without a deduction, plus an apology from me :) (and probably some chocolate, if I still have some.)

I cannot re-grade your program by email because

1. I've already graded it, and already found that it did not compile or function properly. (Please read my comment in your lab paper.)
2. I need to show you that it really does not work. And you need to show me that, with minimal code change, you can make it work. This is easiest done in person, especially when there are many students with different circumstances.
   
3. I need to make sure you understand the seriousness of, among other things, the "CODE DOES NOT COMPILE" situation. In real-life work, it usually does not matter if your program compiles and works on your machine. What matters is whether your program compiles and works on your customer's (or boss', or professor's, ...) machine. Therefore, it is of great importance to check and re-check to make sure that your submission will work as expected.
4. I need to note the new points on your paper and take it back to Prof Carlin to record it.
   

For your information, the most common mistakes are:

1. You did not include all the needed files.
   When I grade your code, I download your files into an empty directory, and run
   javac *.java
   If there is an error because it is missing some files (such as Mover.java), then it does not compile.
   
2. You included too many files, and some of them do not compile.
   You may have edited some code and you decided you no longer need it. Do not include it in your submission, since
   
3. You decided to put comments in at the last minute, and you did not test it after that.
   
4. You put your code in a package, which requires a directory structure.
   Most likely, the IDE did this for you. Make sure you set it up properly.
5. You forgot to turn it in.
   
6. You turned it in, but you did not include your full name and lab number in the subject line.
7. You turned it in properly, but the email got lost.
   For this, I will need to ask for a proof.

- Mock

homework 1

Homework 1 is graded. If you submitted it on time, you will get it back soon.

Please review the solution and look at my comments -- even if you've got a good grade. Sometimes, there are minor mistakes that worth a note, but I didn't always take off points.

Grade dispute can be done in person during office hours, or by appointment.

These are some problems many people made mistakes on:

Problem	Comments
2b	The answer is "EMPTY STRING". Please note that there is a difference between null and empty strings.
2c	The answer is "STATIC". Normally, when we have a non-static method inside a class C, we have to call it by _variableName.methodName(); where _variableName is a variable of type C. We cannot simply call: C.methodName(); unless the method is static.
5a	javax.swing.JApplet is extended to create an applet. JFrame is not the correct answer. JFrame is used to create a window for a java application.
5g	The answer can be: blueprints, guides, stamps, models, cookiecutters.
9c	An algorithm is a set of steps leading to a result. Pseudocode can help develop an algorithm because it focuses on the steps, not the language. An algorithm is NOT a process of refining pseudocode. An algorithm is a process of solving a problem. Pseudocode is used to describe an algorithm.
9e	To write a loop, one must not forget to set an initial value to the counter.
10c	Many of you wrote that in a sentinel-controlled repetition, the number of times the code is repeated depends on user's input. This is not wrong, but not entirely true. It could depend on a lot of other things: e.g. result of a calculation, random number, state of the machine, network data.

Please also check my calculation on the cover page. In summing up your scores, I may have made some mistakes. My apology if that really happens. :)

- Mock

Notes from Week #6

Topics

1. Lab5
1. your grades
   If you get 0-5 points on functionality, your program probably doesn't compile. But don't cry. If you can visit my office hours and show me that, with minimal tweaking on your code, you can make it compile and work, you will get some points back.
   
2. how it works
   Even though you didn't get it, you should still make sure you understand how it works. Take a look at the solution. Talk to other people. Visit the TAs or Prof Carlin. We are more than happy to help you. This lab contains several important concepts (for your skills, for the exam, for life, ...)
   
2. Future labs
1. Lab 6 - Modifying the ClickApp program.
2. Lab 7 - Recursively drawing a fractal.
   
3. More on arrays
1. mergeInOrder
   We partially implemented the method mergeInOrder that we introduced last week.
   

   
   /**
    * Merge the sorted array a and b together, putting the elements in correct order
    * 
    * @param a a non-null ascendingly sorted array 
    * @param b another non-null ascendingly sorted array 
    * @return 
    *   a new array of size a.length + b.length containing elements from 
    *   a[] and b[] in ascendingly sorted order.
    */
   private int[] mergeInOrder(int[] a, int[] b) {
     int la = a.length;
     int lb = b.length;
     int[] c = new int[la+lb];
     int i = 0, j = 0, k = 0;
   
     while ((i < la) && (j < lb)) {
       if (a[i] < b[j]) {
         // a wins!
         c[k] = a[i];
         i++;
         k++;
       } else {
         // b wins!
         c[k] = b[j];
         j++;
         k++;
       }
     }
   
     return c;
   }
   

   
   We have not finished this method, yet. Why? Because we only take care of the case where both a and b still have some element(s) left to compare. In case we run out of elements on array a, we will also have to put the rest of elements on array b on the output array c. Or elements on array b could run out first, we also have to take care of that.
   
   Finishing this method is left as an excercise. Email me your solution. The first person who gets it right will get 1 big Hershey's bar (leftover from last Valentine's).
   
   
2. productExcept

Last week I introduced a method called product. The name was a bit misleading so I am renaming it to productExcept. We solved this problem together and came up with this nested-loop solution:


/**
 * Computes a new array where the i-th element is the product of all elements in array a
 * except a[i]. For example, if a = {1, 2, 3, 4} then
 * productExcept(a) = {24, 12, 8, 6}
 *
 * @param a a non-null array of integers
 * @return 
 *    an array b of the same size as a where, 
 *    with n being the size of a,
 *    b[i] = a[0]*...*a[i-1]*a[i+1]*...*a[n-1] 
 *    for every i from 0 to n-1    
 */
private int[] productExcept(int[] a) {
  int la = a.length;
  int[] b = new int[la];
  for (int i = 0; i < la; i++) {
    b[i] = 1;
    // we will compute the value of b[i]
    for (int j = 0; j < la; j++) {
      if (j != i) {
        b[i] = b[i] * a[j];
      }
    }
  }
  return b;
}


This solutions takes quadratic time in the size of input. If we have 100 input elements, it loops about 10,000 passes (not too bad). If we have 10000 input elements, it loops about 100 million passes (quite bad). Is there another solution where it takes linear time to run?

The answer is yes. One idea is to multiply everything together in the first place. And, as we loop through b, we set b[i] = (the product)/a[i]. This solution seems correct, but may have a few problems: i) division by zero, ii) round-off errors in case of floating points, iii) arithmetic overflow.

Is there a good solution without division? This was an interview question I got last year from Google. If you have a good idea for this, email me and you will get 1 big Hershey's bar. If you email me the working code, you will get 2 big Hershey's bars. Supplies are limited :) Act fast.


4. Recursion
1. Tower of Hanoi

We introduced a game called the Tower of Hanoi and presented a rough idea on how to tackle this problem, and how to think recursively.

2. Fractals
1. Sierpinski gasket
   
2. Fractal Tree
   
3. Koch snowflakes

IMPORTANT: Office hours moved!

Tomorrow (2/15/07), Mock's office hours are rescheduled to:

6pm - 9pm
same place (Phelp 1413)

I can stay longer after 9pm as needed. Bring a pillow and sleeping bag if you want.
;)

This change is a result of the votes from the discussion session today, and it is temporary. His office hours for the following weeks will still be the same (12pm-3pm).

Lessons from Lab3 grading

Logistics

• Do not forget to email all the code. Attach the files as attachments. When I grade your program, I download the files into an empty directory and do:
  javac *.java
  
  If, for any reason, there is an error in this step, it means that your program does not compile. This will be very bad for your grade. So it is your responsibility to verify everything. You must test your code before you submit. Once you have submitted, I suggest that you make a (temporary) empty directory, download the attachments into it, and test your program.
  
  This time I was more lenient. Some of you forgot to email the code or were missing some files. I only deducted 10 points and offered you a chance to resubmit.
  
  
  
  
• To submit your lab, you should follow the instruction on this page:
  http://www.whizbangscholar.com/laboratory1.htm#General%20Instructions%20For%20Lab%20Reports
  In particular, you must "put your name and the Lab number (e. g. Lab 1) on the subject line." Otherwise, your submission may not be found.
  
• AlienApp should contain the main method. Otherwise, it will be hard for me to look for your main class. (-5 if AlienApp is not found.)
  [update (2/5)]: Upon the second thought, I think this is unfair since the instruction on the lab sheet did not clearly specify which class should contain the main method. So I gave the 5 points back. If I miss anybody, please visit my office hours.
  
• Do not forget to include the code listing of all classes.
  

Neatness

• Bad handwriting is bad for your grade.
  
• Some of you are confused between UML Diagram (showing containment) and class hierarchy diagram (showing inheritance). Please look into the book. Also, if we ask you to write 2 or more diagrams, please clearly label both of them.
  
• Please use a fixed-width font for code listing. (Courier New is a good choice.) Please also make sure the font size is big enough, but not too big so that the lines get truncated or wrapped around. Do not print-screen the code. The quality is usually poor. Instead, print it out as text.
  
• Color printing not necessary.

Coding Styles

• Please make everything private unless it really needs to be public. If a subclass needs to read a variable, make it protected.
  
• Please limit the lines' lengths to 80 chars (for nice printing and preventing truncation).
• Limit the use of // comment, especially when it makes the line too long. Consider putting comments in another line. Use this style of /* comment */ instead for multi-line comment.
  
• Indentation is important for the readability of your program. You can follow Prof Carlin's style or the book's style. Just pick one and be consistent.
  
• One class per file: each class should be put in its own file.
  

Hall of Fame:

• Very nice diagrams: Alvin Yip, Drew Martin, Christian Banzon
  
• Francois Hebert: an army of 13 aliens
• Steven Pease: 6 aliens with very amazing animation and interactions.

Lab 2 clarification

Refered to: http://www.whizbangscholar.com/EB/010%20Lab%202%20W07%20B.pdf

There is a slight typo in the original lab write-up. On the line that says
public class Alien extends wheels.users.Frame { ... }
It should have been
public class AlienApp extends wheels.users.Frame { ... }

In other words, the Alien class should NOT extend wheels.users.Frame. It does NOT need to extend anything. In fact, when write the Alien class, the header should be simply:
public class Alien { ... }

The AlienApp class, however, needs to "extends wheels.users.Ellipse".

You do not need to know what "extends" mean at this point. It has not been covered yet (but will be soon). If you are curious, read Chapter 3 on Inheritance.

QUESTION: Where should I put my main method?
Answer: The AlienApp class MUST have a main method. The Alien class does not need a main method.

QUESTION: How will my program be graded?
Answer:
We will do the following...

• First, we will compile your program by...
  javac *.java
  If this creates an error, lots of points will be deducted. So, you must check to make sure there is no error at this point. If there is a "warning", minor points may be deducted.
  
  
• Next, we will run AlienApp by
  java AlienApp
  If it doesn't run, or if it says the class is missing, or the main method is missing, your functionality points will be greatly affected (possibly zero!). So, make sure that AlienApp has a main method.
  
  
• We will look at the result, we must see something like the following:
  
  
  That is, it must have 5 aliens on the same window. Note that alien #5 looks like alien #3 because he just winked and unwinked so rapidly our eye could not see.
  
  Your aliens don't have to look exactly like these. You may arrange them in a different ways -- just make sure we can see them all. Also, you can include your creativity by including a nose, a hat, ears, eyeglasses, body, ... whatever. Try to practice with different ways to draw things in wheels.
  
  If your program runs fine in this step, you will get a very good score.
  
  
• We will try clicking on the alien face to see if you have implemented the extra credit.
  
  
• Next, we will look at your code. You should submit only 2 classes:
  Alien.java and AlienApp.java
  If you have more files and they create errors, this may affect your score.
  
  We will look for the 4 methods specified in the lab write-up: moveTo, turnGreen, wink, and unwink.
  
  We will also look to see if you really made alien #5 wink and then unwink.
  
  Be sure to organize your code nicely. At least, you must indent your code, write your name and date at the top, include a short description of the program. Provide some comments.
  

QUESTION: I attempted the extra credit, but couldn't get mousePressed to work. Why?

You should put mousePressed method in Alien class. Also, modify the header of your Alien class to the following:

public class Alien extends wheels.users.Ellipse { ... }

This will make the Alien itself an ellipse which can be clicked by the user. However, it will create an extra red dot at the center of the screen. This is fine. When we click at the red dot, it will turn the alien to green & winked state.

Can you get rid of the red dot? (For the answer, visit my office hours -- Thurs 12-3pm @ Phelp 1413)

Even more fun: try to implement
public void mouseReleased(java.awt.event.MouseEvent e) { ... }

so that the alien only turn green and wink when the user holds down the mouse button. When the mouse button is released, the alien should turn white and unwinked again.