Final exams, part 1: Algorithms

I just finished the first of my final exams. This was for Algorithms, which has a reputation as a nasty class. I didn't find it to be particularly nasty, but I'm sure part of that is because I've had a book on algorithms for years and so already knew about half the material.

The really neat thing about spending this semester abroad is the way grades transfer over, or more accurately the way they do not. As long as we get passing grades, we get credit for the class -- and the classes don't affect our GPA. This is very pleasant. While I'm not going to neglect my education (perish the thought!) I love being able to shrug off the work that doesn't teach you anything.

For example, consider optimal matrix parenthesization: you want multiply a bunch of matrices together, calculating something like ABCDEF (where A, B, C, ... are matrices). Matrix multiplication is associative, so you can do the multiplications in any order and get the same result, but how much calculating you need to do depends very much on the order. Maybe A(B(C(D(EF)))) takes five minutes and (A(BC))((DE)F) takes five seconds -- this could be a very valuable thing to know ahead of time.

To simply go through and solve this by brute force and ignorance for n matrices requires going through something proportional to 2^n possibilities -- probably more trouble than it's worth. But there's a key observation you can make: any part of an optimal solution is an optimal solution to a subproblem. So in the example I gave above, A(BC) is going to be the optimal way to parenthesize ABC. The optimal solution for DEF is going to be (DE)F. And at the highest level, we just need to know where to split the multiplication into the product of two subproblems. This leads to a recursive solution, but it repeats a lot of subcalculations, so by remembering the solutions to problems and not recomputing them, we can make it dramatically faster.

Now, that's the high-level understanding. It's also sufficient to actually write a program to solve the problem, and it will be pretty simple and zippy. But for various (mostly historical) reasons, we have to learn to do this calculation using a system of filling in these weird triangle-shaped tables of numbers. This is more efficient if you really want to write a fast program, and I suppose it's easier to do on paper -- but it's completely unnecessary from the standpoint of understanding what's going on. Indeed, I don't think our lectures ever really mentioned that the whole point of the tables was just efficient memoization.

I never did learn exactly how to use those tables. My grades suffered a little because of it, but I understood the algorithm and managed to keep my morale up by avoiding the triangle tables. I consider that a good bargain.


There is too much emphasis, here and everywhere else I've been, on memorizing how to do some particular kind of problem that will be on the test. If you spend too much time focusing on the details of one particular implementation of one variant of the concept, you lose sight of why the textbook even gave you that example in the first place: as something concrete to generalize from. We had quizzes which ostensibly tested our knowledge of Quicksort, but the thing they tested was very different from what computer scientists mean when they say "Quicksort". Quicksort refers to a whole family of related algorithms, and the thing they all have in common is that they pick a pivot element, put everything smaller on one side and everything larger on the other, then recursively sort each side. This can cover everything from a simple textbook quicksort on up through complicated things like randomized median-of-three partitioning adaptive Quicksort that uses insertion sort for small subarrays and can revert to heapsort on perverse inputs. What we were quizzed on was an example program in the book, and we were expected to memorize everything about it, right down to how it rounded an insignificant number and the order of the arguments to the function. Anything slightly different from this was "wrong", even though this criterion would make a lot of other algorithms textbooks "wrong" as well. Such decisions have to be made in any implementation of the algorithm, but for learning how Quicksort works they are useless details.

Complaints aside, this was a pretty good class. The material was interesting, and it's a pity we didn't get to more of it. The textbook was friendly, or at least as friendly as a thousand-page clunker can be. The professor spoke English well and seemed like he would probably feel more at home in an American classroom. (For all the reputation Americans have for being dumb and lazy, engineering students in the US compare very nicely with our Taiwanese counterparts.) The homework assignments were few, although I hear that this is because homework solution copying is utterly rampant here.

In any case, it's nice to have this done. One down, three to go.