Materials

The raw slides (pdf) and annotated slides from lecture are available for you to take notes on or review.

Topics

• Analyzing the counting problem
• Solving a recurrence with tree-method and intuition
• Example: multiplication, the schoolbook way
• Divide & Conquer: multiplication via Karatsuba’s algorithm
• Analysis of Karatsuba’s recurrence