15-451 Algorithms 08/31/11
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
(E.g., the reason for the "-2" above is that that node's left subtree
is empty (height = 0) and its right subtree has height=2). 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 definition 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,B,C,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.