Week 1: Induction & Limits

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations

Lecture Recap

Algorithmic Thinking: Examples & Concepts

This week, the lecture introduced you to some first algorithms. So far, the examples have mostly been fun thought-experiments (if you don’t fully understand Star-Search, don’t worry ;) ) but have hopefully given you a sense of the differences design choices can make. One elegant and powerful example was presented with Karatsuba’s multiplication algorithm, which we also look at in the exercise. Secondly, with Pasture Break you saw how different strategies for defining the search domain lead to vastly different runtimes.

Proof by Induction

Perhaps most importantly, the proof by induction was introduced as one of the fundamental proof patterns. Although it might feel like cheating at first, proofs by induction allow us to prove statements of the form $\forall n\geq k(P(n))$ for some $k\in \mathbb{N}$ without needing to exhaustively list them all.

Exercise

In this week’s exercise we will:

• briefly discuss Karatsuba’s Algorithm and Pasture Break,
• practice proofs by induction, and
• practice some limits as a warm-up for next week.