Lecture 5.



Continuing from where we left off on Monday, we saw how to perform a worst case complexity analysis of our Binary Search routine. This involved solving a recurrence relation. We used the technique of expanding the recurrence until we could guess at the solution. We then verified that our guess was correct, using induction.

Divide and Conquer is an extremely important concept in algorithm design. We revisited the maximum contiguous subsequence sum problem and showed how it could be solved using a recursive divide and conquer algorithm. We then solved the recurrence relation representing the cost of the algorithm, namely O(N log N).

As we will encounter frequently encounter expressions involving exponents and the log function, I have attached a page summarizing the rules we use when manipulating these functions. This pages was extracted from the published web notes for the book Data Structures and Algorithms in Java
by Goodrich and Tamassia.

I will be keeping track of the parts of the text that are relevant to our class this term. By the end of Fridays lecture we will have covered all the material that I plan to cover in Chapters 6 and 8. The detailed breakdown is:

Readings:

Read : Required reading. Covered in lectures (more or less). Sample questions and tests are based on this material.

Optional: Not central to the course. Reading this material should not be too difficult and would nicely support the required material.

Skip: This material would require more effort to understand than the optional category above. Note: this does not mean that there is anything wrong with the topics covered in these sections, rather this material is tangential to the course this term.

Chapter 6. Read all of it.


Chapter 8.
8.1 – 8.2 Read
8.3 Optional
8.4 Skip
8,5 Read
8.6 Skip
8.7 Skip

I will keep a cumulative list of readings in the new Readings category of this blog.

UsefulMath.pdf

Posted: Wed - January 19, 2005 at 02:00 PM        

©