Didn’t take long before a few of them got the invites soon afterwards. I think it takes the Wave team at least a day or two to send an invite once you nominate your friends. Anyway, now we have more interesting stuffs to do.

The first wave: I started a wave on the recipe of the chicken katsu my girlfriend and I cooked last weekend. I might not look like it, but I do cook often enough, and the katsu was really good! Even my girlfriend’s sister, who has a high standard for food, liked it. Well, back to the point, it was kind of fun to write the recipe in Wave. But wait a sec, I can do that just using Google Docs, can’t I? Or even this blog. Well, let’s put that thought on hold for a moment…

The second wave: my girlfriend went online and she started playing with her Wave account. She was initially confused. So we both started a wave (oh, and I shared the katsu recipe wave with her) and started experimenting. This is where Wave really shines. We were able to edit any of the sub-waves together and the changes appear live on the other person’s Wave account. I can see exactly where she’s editing and can even reply to her post before she finished writing. We also played (well, I did) with the playback function. Really cool!

The third wave: well, I am supposed to write an article for this small blog-based publication that my friend is running. Since she has a Wave account too (and, like me, has no idea what to do with it), I suggested that we might want to try writing the article as a wave. My idea would be to write the article (outline and the actual article), brainstorms, and have her editing the article as necessary. Thought that is a neat idea, but we’ll only be able to test that next week since I’m still kind of busy this week. Seems fun though! Imagine live collaboration on an article, bouncing ideas through a wave or gtalk, while writing the article at the same time. Plus, I’ll be able to see her edits appearing live on my wave.

Well, anyway, back to the thought that I put on hold some moments ago: Google Wave equals Google Docs? Is that true? Well, yes and no! Wave can indeed work like Google Docs (well, right now minus the spreadsheet/presentation stuffs, but I bet there will be a gadget to take care of that soon). And that is indeed the point! Wave is Google Docs + GTalk + GMail + wiki! It’s like this all-in-one, all encompassing collaborative solutions. Cool? Hell yeah. Will it work? Only time will tell.

Well, I had fun waving today. But I shall stop here. Still have a presentation to write for Monday and I need to get a draft of it by tomorrow. ):

We will first consider the first variant to arrive at optimum answer.

A simple answer would be to perform brute force search in the array, considering each position as possible starting and ending point. Time complexity: O(n^2). Not very good eh? Can we improve on this? Yes, we can if we use dynamic programming. For many of us, the algorithm came up as obvious, but I realize that it is really not that simple for students new to programming to come up with a correct algorithm. To answer this, I tried to explain the concept behind the algorithm: for each element of the array, we find the maximum value sub-array that ends at that element. This value can either be the value of the element itself (meaning starting at the element and ending at the particular element) or the maximum value sub-array ending at the previous element added to the value of the element. (The latter only occurs if the maximum value sub-array at previous location is not negative.) There you go, we have a recurrence relation: given an array A, let v(k) be the maximum value of any sub-array ending at position k, where k ranging from 0 inclusive to N exclusive, N is the length of the array. Hence we have:

v(0) = A[0]
v(k) = max{v(k-1) + A[k], A[k]} if k > 0

The maximum value will be given by max{v_i} for i from 0 to N-1. To implement this in Java, we make several optimization. Firstly, we can opt for recursive method or dynamic programming. Both will take O(n) time but since we’re using Java, we would rather use dynamic programming since there is no tail call optimization in Java. Then, rather than finding the maximum value using max{v_i} at the end, we keep a running maximum throughout the running of the algorithm and return it. We also note that v(k-1) + A[k] will only be greater than A[k] iff v(k-1) is greater than 0. Here is how the code goes (this is a rather faithful implementation, it uses the same variable names as the recurrence relation above to make it easier to see):

public static int calculateMaxValue(int[] A) {
  int[] v = new int[A.length];
  int max = v[0] = A[0];
  for (int i = 1; i < A.length; ++i) {
    v[i] = A[i];
    if (v[i-1] > 0) {
      v[i] += v[i-1];
    }

    if (v[i] > max) {
      max = v[i];
    }
  }
  return max;
}

This algorithm has O(n) time complexity.

What else can we do to optimize this code? Well, we don’t really need to keep an array of maximum values. We notice that at any point of time, to calculate the value of v(k), we only need the value of A[k] and v(k-1). We just turn an O(n) space requirement to O(1).

public static int calculateMaxValue(int[] A) {
  int max = A[0], current = A[0];
  for (int i = 1; i < A.length; ++i) {
    if (current < 0) current = 0;
    current += A[i];

    if (current > max) max = current;
  }
  return max;
}

Voila! We shall continue with the second variant next time. (:

Anyway, a friend of mine is currently applying for jobs in several “big” companies (you know, the Google-Microsoft-Apple kind?). So he was preparing for his interview by hunting quite a few online questions. One of the questions he asked reminded me of a question I used to use to exemplify the kind of questions these companies used in their technical interview:

Given a head pointer to a (possibly very long) linked list of unknown length, devise a method to sample m members at random. Ensure that the method yields equal probability for each element in the linked list to be picked.

Obviously we can traverse the list once to find the length, generate m random numbers from 1 to length of the list and traverse the list another time to pick up these items. A common question would be to prevent you from going through the list more than once. Say the list is very long, the disk I/O you need to get the items from harddisk (even after making sure the items are arranged well that it minimizes cache misses) would make traversal a very expensive operation and hence should be minimized.

The solution I have is inspired by the fact that if the linked list contained m or less elements, I have no choice but to pick all m of them. Hence, the main idea of the solution would be to pick the first m elements and keeping track of k—the number of elements we have seen so far. When we encounter a new element, the new element has an m/k chance of being picked. If it is picked, we dropped 1 of the previously selected m elements at random. We can easily prove that this indeed yields the correct probability via mathematical induction.

Now of course it won’t be fun to implement this in Java or C++, so I decided to use Scheme to code this, just for the fun of it. The solution is surprisingly short and pretty. Here goes:

(define (sample-m lst m)
  (define (helper curr k m-vec)
    (if (empty? curr)
        (if (< k m)
            lst
            (vector->list m-vec))
        (let ((pos (random k)))
          (cond ((<= k m)
                 (vector-set! m-vec
                              (- k 1)
                              (car curr)))
                ((< pos m)
                 (vector-set! m-vec
                              pos
                              (car curr))))
          (helper (cdr curr) (+ k 1) m-vec))))
  (helper lst 1 (make-vector m)))

;;; Let's test this!
(sample-m (build-list 1000 values) 7)

EDIT: I decided to try writing a version for Java as well. Here is the Java code:

public class LinkedListSampler {
  private static Random rand = new Random();
  public static <T> List<T> sample(
      LinkedList<T> list, int m) {
    ArrayList<T> samples = new ArrayList<T>(m);
    int k = 0;
    for (T element : list) {
      int pos = k++;
      if (pos < m) {
        samples.add(element);
      } else if ((pos = rand.nextInt(k)) < m) {
        samples.set(pos, element);
      }
    }
    return samples;
  }
}

EDIT 2: Btw, seriously, the Java code is just for fun. Just imagine that LinkedList does not have a size method, will ya? ;)

Anyway, this one is the cutest! Shit! The cat and the video is just so cute!

(Watch the other 10 videos from YouTube’s Chrome channel.

I have finally decided to get this book. Have been struggling quite a bit with some more complex probability for mathematical and systems modeling and for my research. So I thought getting more rigorous grounding would help. Seems that a lot of people are recommending this book, so I thought I’ll give it a try. Will update after I completed at least several chapters of the book. (Well, the book itself won’t arrive for another week or so.)

public interface ClosureIntReturnInt {
  public int invoke(int arg1);
}

@Test
public void testNaiveClosure() {
  final int a = 1; // This must be final!
  ClosureIntReturnInt addA =
      new ClosureIntReturnInt() {
    public int invoke(int v) {
      return v + a;
    }
  };

  assertEquals(3, addA.invoke(2));
}

This is obviously not a very good solution. So my first instinct would be to genericize the closure interface. Sure enough, it simplifies the problem by quite a bit. Here is my genericize Closure interface:

public interface Closure0Arg<R> {
  public R invoke();
}
public interface Closure1Arg<R, A1> {
  public R invoke(A1 arg1);
}
public interface Closure2Args<R, A1, A2> {
  public R invoke(A1 arg1, A2 arg2);
}
.
.
.

Sure enough, this works fine and it becomes much easier to use. It is of course still inconvenient for people who came from functional programming world. The problem is: (1) there is no universal Closure, that means you have to keep track of the Closure type as type annotation, many, including me would love to ditch the cumbersome type annotation; (2) you have to write the interface for each number of arguments (much better than writing for each argument type of course, but still…).

Of course, OTOH, this is the best you can do while maintaining static checking ability. Here is an example usage:

@Test
public void testClosure1Arg() {
  Closure1Arg intToString =
      new Closure1Arg<String, Integer>() {
    public String invoke(Integer v) {
      return v.toString();
    }
  };

  assertEquals("5", intToString.invoke(5));
}

A sharp reader would have noticed several (not-very-correct?) things happening here. First, we eliminate the generic from intToString type annotation. This does not change the semantics of the code and make the code looks cleaner; however, it does create an “unchecked” warning with the Java compiler. Secondly, we utilize autoboxing freely in this implementation. Since we are utilizing generics, R, A1, …, An must all be objects. This is obviously undesirable and ugly. However, due to autoboxing, this is no longer an issue (except performance-wise).

So far, this is really the best we can do while preserving static type checking. However, if we ignore additional security provided by static type checking, we can go a step further: we can introduce a Closure base class; the rest of the closures interface (Closure1Arg, etc.) will become an abstract class that extends the Closure class. This is where all the interesting stuffs are happening. Here is the source code for the Closure class.

public class Closure<R> {
  @SuppressWarnings("unchecked")
  public R invoke(Object... args) {
    Class[] classes = new Class[args.length];
    // This is okay since generic type annotation
    // is stripped after compilation. We only
    // need to find invoke method with
    // the right number of params.
    Arrays.fill(classes, Object.class);

    try {
      // Search for correct invoke method
      // and execute it.
      Method method =
          this.getClass().getMethod(
              "invoke", classes);
      return (R) method.invoke(this, args);
    } catch (Exception e) {
      // TODO: handle exceptions correctly.
      // ClosureException is a runtime exception.
      throw new ClosureException("Error", e);
    }
  }
}

// e.g. of ClosureNArg abstract class.
public abstract class Closure1Arg<R, A1>
    extends Closure<R> {
  public abstract R invoke(A1 arg);
}

This code completely sacrifices static checking. Now we can simply have each closures to be stored in variables of Closure type. When invoke is called, the method from the base class (above) is called. It will find the correct (i.e. more specialized) invoke method (declared in the concrete anonymous object derived from the subclass) to call based on the type of the arguments to invoke. Here is how we can use it:

@Test
public void testClosure1() {
  Closure<Integer> addOne =
      new Closure1Arg<Integer, Integer>() {
    public Integer invoke(Integer arg) {
      return arg + 1;
    }
  };
  assertEquals(3, (int) addOne.invoke(2));
}

@Test
public void testClosure2() {
  Closure<Double> add =
      new Closure2Args<Double, Double, Double>() {
    public Double invoke(Double a, Double b) {
      return a + b;
    }
  };
  assertEquals(7.5, add.invoke(4.2, 3.3));
}

Sweet! Now this is neat! Of course, we have ignored much of the static checking and replace them with dynamic, runtime checking. I have removed much of the exception checking code in Closure<R> base class to save space and focus on the meat. Again, I’d draw readers’ attention to several important code fragments:

1. We catch most of the checked exception and replaced them with unchecked runtime exception to make the usage much cleaner, this follows more closely to dynamic, interpreted language rather than static language (as with Java);
2. We readily suppress warning with @SuppressWarnings (heh!);
3. The code, arguably, takes a bit of performance hit, so users who are more concerned about performance should probably not use this (squeezing performance usually means messier code; closure is for elegance, not mess);
4. You may want to write simple script to autogenerate ClosureNArgs (N from 0 to however many arguments you think is reasonable; I personally generate up to 7 arguments);
5. You probably want to generate closures for void return value as well; that would make things messier (much messier) though. It is probably easier to return null instead.
6. Here, I opt to go for clean ClosureNArgs subclasses. Others may opt to add some ugliness to the subclasses and make the base class cleaner (and likely result in faster closure code). I will likely experiment with this further, and try to implement variable binding as well.

I found it very interesting to implement Closure in Java; hope you do too. :)

EDIT: This is interesting, wonder how I missed this earlier: Closures for the Java Programming Language (v0.5).

EDIT 2: I simplified Closure&ltR> a little bit more. The simplification is a result of stripping of the generic type annotation after compilation. So the base class need only hunt for invoke method with the right number of parameters.

Kids & Computers

Today’s ACM TechNews includes an article on CMU trying to buck trends of having few women in Computer Science. I agree wholeheartedly.

However, before we even get there, computer science is seriously in need of polished publicity. I have talked with several undergraduates and high school students recently and encouraged them to take up computer science. In general, most of them were impressed when they heard that I majored in Computer Science. They thought that it is pretty cool as a major. However, when I asked them whether they are considering (especially the high school students) to major in computer science, the response I got was roughly this: no. “Why not?” They replied back that computer science involve lots of programming and they think that programming is hard, really hard. They also strongly equate computer science with programming and only programming. I do believe that programming is not easy, especially at the beginning, but it is not harder than, say, solving difficult physics questions, or designing chemistry experiment to confirm a hypothesis. (I was lucky to be introduced to programming, with LOGO and Basic—yes, Basic, unfortunately—in late elementary school; but most of these people have never touched any programming language before.) Few of them also think that programming is geeky, something that I would never refute; I think being geeky is cool.

Furthermore, even if programming were taught in schools before university, I have a strong feeling that they are being taught wrongly. Instead of being taught to appreciate the beauty of programming (recursion, abstraction, closure, memoization, etc.), teachers were more focused on getting the syntax right. That, in itself, is not too bad. However, the choice of language really do reveal the weakness of the method. Teaching C++ or Java as a first programming language is definitely not a good idea. These languages are very thick with syntax. Example to the point, I have seen loops being taught as a syntax; as for its concept, teachers keep reiterating that it is used to make a particular code loops over and over until the condition turns to become false. The explanation is correct. On the other hand, such explanation rarely extract the awe and understanding of the power of loop construct.

(Granted, at high school level, I am only familiar with Cambridge ‘A’ Level syllabus for Computing, which uses C/C++, I might have too narrow a viewpoint, or even outdated.)

So the first thing we should straighten out is to clean up the way programming should be taught to students. I would start with Javascript (hey, something that can be applied right away on their own websites is cool and fun!), Python, or Scheme. (Yes, you’re right, I think type system only make teaching programming more convoluted without offering much direct benefits.) Picking good teachers is no longer optional. The aim should be to make students appreciate computer science as a diverse, exciting, and fun field. It should definitely not be aimed to teach students to be proficient in one (or, worse, two) programming language. Probably introducing them at younger age would make it even more effective, as students get higher exposure to it and the curriculum gets more refined as it is harder to teach the younger students. (In fact, it is probably more rational to teach visual programming technique. About half a year ago, I watched a Google Tech Talk on tangible functional programming, where the concept of value, pair, and function/lambda is translated into intuitive visual system that allows even stronger form of composability.)

Certainly, putting some into good publicity will not hurt. Though I do think that we should put more effort into integrating computer science into early education (just like other sciences) to let the younger generation figures out how suitable is the major for themselves, before the stigma attached to CS becomes too deeply rooted in them.

Acknowledgment: Photo was published by shapeshift under Creative Commons (Attribution & Share-Alike); link to flickr page.

This guy is my hero on web performance technique, so I was real happy when this video was published recently in googletechtalks YouTube channel (check out the channel, it has many, many other interesting videos).

In this tech talk, he built up upon the previous tech talk (which I happened to watch live, but could not find it online) and talk about how you can take advantage of parallel Javascript downloads while maintaining any coupling you have between external scripts and inline scripts that you have. One of the techniques involve a modification of John Resig’s degrading script tags. He also mentioned problems with iframe preventing onload events to be fired earlier. Finally, he made clear how you could flush your data early to ensure that you utilize chunked transfer. The last bit was particularly interesting. It has been in my mind recently and I have experimented quite a bit with PHP to perform this. Soon I’m going to try to figure out whether a Python (non-Apache) web server can perform similarly (I believe so). I already wrote a testing web server (based on HttpServer class).

In PHP/Apache case, there were quite a few difficulties in making sure that chunked transfer is performed. One is to make sure that you have enough data (and specifically flush PHP output buffering otherwise). Another involves figuring out Apache’s limitation on sending a single chunk (you have to have enough data before Apache agree to push these data; worse still, if you activate gzipping, the data must exceed the minimum gzip window). Of course, the most interesting problems would be to figure out how to structure the page to ensure that you get the most out of chunked transfer. In another word, you would want to transfer as much dumb data (that can be generated real fast) as possible to utilize the time taken for the server to generate the difficult content as efficiently as possible (at that time, the browser can start downloading CSS, some images, and maybe some Javascript). Also note that the browser will start partial rendering of the page; however, the rest of the page will only be rendered when the rest of the data comes (which can be very long when you’re unlucky). So you need to make sure that the page renders fine with partial data.

Souders’ talk revealed several more considerations that escape my own experiments in this. One is that some proxy server will buffer chunked transfer; the effect of which is that the user will get the entire page in a single monolithic transfer. Also, some browsers (Chrome and Safari) will not start partial render unless there’s enough data (2KB for Chrome, and 1KB for Safari).