Lecture 17

We finished chapter 13. Specifically

• Built and analyzed two recursion trees.
• Did another example of a tree induction proof involving rank.

Recap of the key definitions for the rank proof. If T is a tree with root r, then the rank of T is (a) zero if r has no children, (b) 1+q if r has two children both with rank q, (c) otherwise, the maximum rank of the children. Claim: a tree of rank q has at least 2^q leaves.

Announcements

• Midterm 2 will be on Tuesday, Nov 6th, in class. Report any conflicts to Margaret NOW. If you need a DRES room, book it NOW.
• Honors homework 2 is now posted, due 9 November.