Reminder that you must complete the pre-reading before each class.

On this page:
✔️ Pre-reading for Tuesday 7/6
✔️ Pre-reading for Wednesday 7/7 & Thursday 7/8

---

Pre-Reading for Analyzing Recursive Algos, Tuesday

Essential Questions

✔️ What is a recurrence relation and why is it useful?
✔️ How do we derive a recurrence relation from code?
✔️ How do we solve a recurrence relation to get the time complexity of a function?

Read/Watch/Review

Notes:

• A lot of the pre-readings will mention induction. If you’re unfamiliar with induction, please read this introduction before continuing.
• The first reading below is a textbook chapter. You may choose to read the textbook chapter OR the three articles beneath it.
  • They all give relatively the same information, with the textbook going more in-depth and having better-explained examples.
• Don’t be overwhelmed by the proofs– you won’t be doing formal proofs in this class, but you should understand how to confirm with yourself that your answers are correct for when we do practice problems.

Before attending class, please complete the material below:

• Read Chapter 10: Recurrences
  • You can ignore sections 10.4.3-10.4.5
• Read Recurrence Relation
• Read Solving Recurrence Relations (Part I)
• Read Solving Recurrence Relations (Part III)
  • Purposely skipping Part II
• Watch Recurrence Equations Overview (6 min)
• Watch Recurrence Relations Discrete Mathematics (15 min)

---

Pre-Reading for Recursive Backtracking, Wednesday & Thursday

Essential Questions

✔️ What is a recursive backtracking and when is it useful?
✔️ How do write code that does recursive backtracking?

Read/Watch/Review

• Read Recursive Backtracking I
• Watch The Backtracking Blueprint: The Legendary 3 Keys To Backtracking Algorithms (14 min)
• Watch Backtracking (Think Like a Programmer) (13 min)