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