Notes from Week #7

Notes from Week #7
Feb 28, 2007
by Mock

It's the last day of February!

Nobody has attempted my quiz from last week :(
So I had to do it myself, and ate all the chocolate.

Just kidding. Please (actively) participate today and take all my leftover chocolate from the Valentine's Day :)

Outline

1. The blog: why you should check cs10w07.blogspot.com often.
   
2. Solution to the "quiz"
1. Posted online (on the blog).
   
2. Ideas.
   
3. Questions about Homework 1?
1. Top-down stepwise refinement, Algorithms
   
2. See more on the blog.
   
4. Lab grades.
   
1. Why am I so tough on the "CODE DOES NOT COMPILE" situation?
   
2. Programmer-customer analogy
   
5. Recursion
1. Tower of Hanoi
2. More on Fractals

The Blog

Please check this blog often, since it will be the main line of communication between you and me and Shaomei. I will use the mailing list only when I think necessary. I don't want to spam your mailboxes :)

http://cs10w07.blogspot.com

You may find tips and useful info for your exams, homework, or life. (well, not quite, but...)

Solution to the "Quiz"

This refers to the 2 problems I gave in the discussion session last week. The first one is easy -- just to finish up the mergeInOrder method. Here we go:

(TOBEWRITTEN)

The second one takes a little (or a lot?) more thinking. Here is the code:

(TOBEWRITTEN)

The idea is to define two new arrays left[] and right[],
where left[i] = product of everything on the left of i-th cell,
and right[i] = product of everything on the right of i-th cell.

It's easy to compute left[] and right[] arrays in linear time. Now, we can say that the result array b[i] = left[i]*right[i] for all i.

This technique is known as Dynamic Programming. You will learn more about it in your algorithm course.

Question about Hw1

Is there a question? Please see the blog entry regarding this.

An example of top-down stepwise refinement:

When you want to write the mergeInOrder method, you want to come up with an algorithm. So, you start with a very high-level, yet descriptive pseudocode:

mergeInOrder(array A, array B)

1. Make a new array C to be the output.
2. Put contents of A and B onto C, maintaining order.
3. Return C
   

Note that at this first step, your pseudocode sounds like English (or another human language of your choice -- in my case, I sometimes write in Thai). And you may have no idea (yet) how to do Step 2 exactly. This is fine, we will gradually refine it.

Now you can refine the steps to make it more clear, more descriptive. The next step could be:

mergeInOrder(array A, array B)

1. Make an array C of size A.length + B.length.
   
2. Loop until A or B run out of values
   
1. IF current element in A is less than current element in B
   THEN put current element of A in C, proceed A and C
   ELSE put current element of B in C, proceed B and C
3. If A run out first, put the rest of B in C
4. If B run out first, put the rest of A in C
5. Return C
   

This looks more like a code now. So let's put more details on how we keep track of "current elements" in A, B, and C. We probably need some index variables. Let's call them i, j, k.

mergeInOrder(array A, array B)

1. Make an array C of size A.length + B.length.
   
2. Let the integers i = 0, j = 0, k = 0. /* they will be indices of A, B, C, respectively */
   
3. WHILE i < A.length AND j < B.length DO THIS
   
1. IF current A[i] < B[j]
   THEN C[k] = A[i]; increment k, i;
   ELSE C[k] = B[j]; increment k, j;
   
4. /* If A run out first, put the rest of B in C */
1. WHILE (j < B.length) DO THIS
   
1. C[k] = B[j]; increment k, j;
5. /* If B run out first, put the rest of A in C */
1. WHILE (i < A.length) DO THIS
   
1. C[k] = A[i]; increment k, i;

1. Return C

And, we are pretty much done. This piece of pseudocode is very valuable, as we can directly translate it into (almost) any high-level languages: Java, C, Perl, python. It is much easier (and safer) to arrive at a code this way than by just writing a Java code on a blank screen (also known as "Debugging a Blank Screen").

Lab Grades

If your program did not compile on my machine, you probably got 0 or 5 (depending on whether you submitted a reasonably-looking screenshot).

Please visit my office hours. Grade disputes can only be done in person. To see why, please read my reasoning on the web.

In real-life programming, programmers write code, test their code, and ship the code to customers. Customers do not care how great the program run on the programmers' machines. They only care if the program works on their machines. This is why it is a responsibility of the programmers to make sure, and double check to really make sure, that the final version of their code will compile and work as expected. It is important to verify the submission, by making sure that you choose the right method to submit, that your email client has really sent that email, that you have attached all the needed files and nothing more, that you are using the "right" email client to do the job.

For this class, umail is a good choice. We are not too picky if you choose to send it from Gmail, Yahoo Mail, Hotmail, or other places. But if those websites act up, you are using it at your own risk. There was one time when Hotmail, with all its wisdom, truncates the lines in your java files for you if the lines are longer than a certain length. And this makes the code uncompilable. This is not really your fault, but it is your bad luck with Hotmail, which is the risk you have to take for having chosen to use it.

It also makes sense to keep record of your submission. That is, the mail may get lost, and you should be able to retain a credible proof that you did submit it on time. Saving the sent messages can save you a lot of troubles.

In some cases, the customers are just ... well ... dumb. You write a good program. The program works perfectly. But a customer insists that your program crashes his computer. It may turn out that, in fact, the customer happens to be kicking the power cord. It is not your fault at all.

In this case, you should provide a good customer service. Go to him/her in person and show him/her that your program does work. Ask him/her to prove that your program does not work. If you are not at fault (and if the customer is not too dumb), he/she will understand and you will win the argument. :)

For this class, as far as the grading is concerned, your graders are your customers. In real life, the customers may mean your boss, your peers, your professor, the Quality Assurance team, ... etc.

Tower of Hanoi

Take a look in your book, and these great resources:
http://www.cut-the-knot.org/recurrence/hanoi.shtml
http://en.wikipedia.org/wiki/Tower_of_Hanoi

We want to write the following method:

/**
* Prints the step-by-step instruction on how to solve the Tower of Hanoi problem.
* Specifically, tells the user how to move n disks from tower i to tower j, using tower k as a temporary tower.
*
* Assumes i, j, k are all different.
*/
private void solveHanoi(int n, int i, int j, int k);

For example solveHanoi(3, 1, 3, 2) will print the instruction on how to move 3 disks from the first to the third tower. The output will look like:

1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3

How do we write this method? Let's think about an easy case first. If n = 0 (or less than 0), there is nothing to do. Just return without printing anything. If n = 1, we can just move the disk directly from tower i to tower j, so just print i -> j and return.

For all other cases (n > 1), we need to somehow move n-1 disks from tower i to the temporary tower k first, then move 1 disk from tower i to tower j. Finally, we move the n-1 disks we deposited on the temp tower k forward to tower j. Note that the description given here depends on a smaller number of disks. So we can recursively call solveHanoi to solve the problem because n will eventually reach 1 or 0.

The solution looks like:

/**
 * Prints the step-by-step instruction on how to solve the
 * Tower of Hanoi problem.
 *
 * Specifically, tells the user how to move n disks from tower i to tower j,
 * using tower k as a temporary tower.
 *
 * Assumes i, j, k are all different.
 */
private void solveHanoi(int n, int i, int j, int k) {
  if (n <= 0) return;
  if (n == 1) {
      System.out.println(i + " -> " + j);
      return;
  }

  /** we may now assume n > 1 */
  solveHanoi(n-1, i, k, j);
  solveHanoi(1, i, j, k);
  solveHanoi(n-1, k, j, i);
}

Try computing solveHanoi(3, 1, 3, 2) on paper. See if the result looks the same as above.

This problem is a classic example of the use of recursion. It is possible to solve this without recursion, but it is much easier this way.

Sierpinski Gasket

See http://en.wikipedia.org/wiki/Sierpinski_triangle

Let's attempt to write a pseudocode for the following function:

/**
* Draws a Sierpinski Gasket whose 3 corners are p1, p2, p3. Stops when p1 and p2 are "too close" -- having distance less than 3.
* Assumes we have this global variable:
* Graphics2D g2;
* Everything should be drawn onto g2.
*/
private void drawSierpinski(Point p1, p2, p3);

Our strategy will be as follows: we first compute the distance between p1 and p2. If they are too close, then return right away.

If not, then we first draw a normal, boring triangle with vertices p1, p2, p3. Then we subdivide the lines -- finding the midpoints between p1 & p2, p2 & p3, and p1 & p3. Call these midpoints p12, p23, and p13 respectively. Now, we can recursively call drawSierpinski(p1, p12, p13); drawSierpinski(p2, p12, p23); drawSierpinski(p3, p13, p23); And, well, we're done!

How does this work? It works because at each step, we do our job of drawing at this certain resolution, and use recursion to draw the sub-triangles at the finer resolution. Our base case is when the points are too close together. Each step of calling moves the points closer and closer to one another, so eventually it will reach the base case.

As we have convinced ourselves with this idea, we can write the following pseudocode:

private void drawSierpinski(Point p1, p2, p3);

1. Compute distance between p1 and p2.
2. If distance < 3, return;
3. Draw a boring triangle (p1, p2, p3).
4. Compute the midpoints p12, p23, and p13
5. Make recursive calls.
   

Then, we refine it:

private void drawSierpinski(Point p1, p2, p3);

1. double d = squareRootOf( (p1.x-p2.x)^2 + (p1.y-p2.y)^2 );
   
2. IF d < 3 THEN return;
3. /* Draw a boring triangle (p1, p2, p3). */
   
1. Draw line p1 - p2
2. Draw line p1 - p3
3. Draw line p2 - p3
4. /* Compute the midpoints p12, p23, and p13 */
1. /* Compute p12 */
   
1. p12.x = (p1.x + p2.x) / 2.0;
   
2. p12.y = (p1.y + p2.y) / 2.0;
2. blah... (for p23)
3. blah blah... (for p13)
   
5. /* Make recursive calls. */
1. drawSierpinski(p1, p12, p13);
   
2. drawSierpinski(p2, p12, p23);
   
3. drawSierpinski(p3, p13, p23);

and that's pretty much the code! (except for the blah blah part :P)

To print this note, visit:
http://docs.google.com/Doc?id=ddm3gthj_689d8f53