15-451 Algorithms 9/01/04 RECITATION NOTES ======================================================================= The plan for today is to engage the class in solving several homework-style problems. PROBLEM #1: Balance factor, part 1 Given a binary tree, the "balance factor" at a node is the height of the left subtree minus the height of the right subtree. E.g., 0 o / \ 2 o o -2 / \ 1 o o -1 / \ 0 o o 0 Say we want to find the balance factors at all the nodes (this will tell us how "well-balanced" the tree is at various places). How can we do this quickly? Hint: in many cases it helps to compute more information than you need, in order to make the computation easier. Solution: in addition to computing the balance factor, let's also compute the height. We can compute the pair (height, balance-factor) for a node x by recursively computing it for the left child and the right child and then using the results to construct the pair for x. Another natural algorithm is to first compute the heights of all the nodes and then make a second scan to compute the balance factors given the heights. Running time is O(n), where n is the number of nodes. This idea of computing *more* information than we were asked to, in order to make our computation easier, will come up later when we talk about Dynamic Programming. PROBLEM #2: Balance factor, part 2 There's a balanced search tree data structure called "AVL trees" that keeps all balance factors between -1 and +1. We're not going to talk about this particular method in class, but the high level idea is that if you required the tree to be *perfectly* balanced, then each insert might force you to make all sorts of changes in the tree to maintain your invariant; but, by allowing this slight amount of slop, you can do the updates with only a constant factor extra work. [We'll see this as a general kind of technique: getting a fast algorithm by relaxing the requirements a little]. But, the question I want to focus on now is: what does having all balance factors between -1 a and +1 say about the *height* of the tree? Can we guarantee a height of O(log n) for an n-node tree? Easier: instead of looking at h(n), let's define n(h) to be the *minimum* number of nodes in a tree of height h. E.g., if we can show that n(h) > 2^{h/2}, then that means a tree of n nodes can have height at most 2*lg(n). Ideas? If tree has height h, then one of subtrees of root has height h-1 (by defn of height) and the other has height at least h-2 (by the balance property). So, n(h) > n(h-1) + n(h-2). This is Fibonacci..., but as a crude bound, we have n(h) > 2*n(h-2). Every time h goes down by 2, we multiply by 2. So this gives us n(h) >= 2^{h/2} if we define a single root with no children as having height 0 (to get the base case). PROBLEM #3: complex multiplication In computing airflow over a wing or other scientific simulations, one often has to multiply complex numbers or complex matrices. We can think of a complex number (or matrix) as a pair (A,B) where we define multiplication as: (A,B) * (C,D) = (AC-BD, AD+BC) Think of A..D as abstract entities for which addition is fast but multiplication is slow. Notice that the above computation requires 4 multiplications and 2 additions. Can you think of a way to do this with just 3 multiplications (and perhaps more additions)? (Might be good to have students work in pairs and think about this for a few minutes). Solution: There are several solutions. Here is one: - first compute x = (A+B)*(C-D). This takes one multiplication. It gives us AC-BD (which we want) but unfortunately with -AD+BC also. - then compute y = AD, z = BC. This takes two multiplications. - output (x+y-z, y+z). This only requires additions. Note: this was discovered by Gauss circa 1800.