Lecture 6.



Answering a request from Wednesdays class I gave a brief sketch of how one would prove that our recursive binary search routine is correct. We then looked at two more selected topics from chapter 8 of the text. We verified the solution to a divide and conquer recurrence. We then looked at a recursive, but exponential time, method of computing the Nth Fibonacci number. In contrast we showed how the same quantity could be easily computed non-recursively in linear time.

Next week will begin studying trees. As a short preview I introduced some of the common terminology we use when discussing trees.

The Readings entry for the Trees chapter (Ch. 18) is a Read for the whole chapter.

I promised that I would include some pointers to web sites that may help you with your C++. Here is one that you may find useful and interesting.

Finally, you should all be aware of the sample questions to reinforce the material of the first two weeks, and help you prepare for the first quiz. The questions are posted on the announcements part of the WebCT bulletin board. I have copied and pasted them below.

The first quiz will be in your tutorial during the fourth week of classes. The quiz will be
one hour. Each tutorial will have a different quiz, with questions selected from the
following exercises in your text (and usually modified):

Exercises at the end of Chapters 6 & 8:

6.4, 6.5, 6.6, 6.7, 6.8, 6.9, 6.14, 6.15, 6.16, 6.17, 6.21

8.1, 8.3, 8.9, 8.12, 8.23, 8.24

Posted: Fri - January 21, 2005 at 04:37 PM        

©