Lecture 13

We finished algorithm analysis, working through the examples

• recursive, half-size sub-problems: binary search (mergesort was done last class)
• recursive, n-1 size sub-probelms: towers of Hanoi, min of values in a list
• Karatsuba's multiplication algorithm.

We also did a brief introduction to NP.

Towers of Hanoi demo

• Dynamic Drive