CS 2110 Midterm: CS 2110 Cornell 2012 Fall Examsp1solcs211sp07

• School: Cornell University
• Department: Computer Science
• Course: CS 2110
• Professor: All

Document Summary

There are 6 questions on 6 numbered pages. Check now that you have all the pages. Use the back of the pages for workspace. The exam is closed book and closed notes. A binary tree is nearly balanced if all its nodes are nearly balanced. Prove by induction that the number of nodes in a nearly balanced binary tree of height k is at least fk, the kth fibonacci number. Recall f0 = 0, f1 = 1, and fk = fk 1 + fk 2 for k 2. In the induction step, state the induction hypothesis clearly and indicate exactly where in your argument it is used. You will probably need strong induction, and there will probably be two base cases. There are 2 base cases, k = 0 and k = 1. For k = 0, the only tree of height 0 is a leaf, which has 1 node, and 1 > 0 = f0.