It's nice to be able to forget things.

BACK: Classes

Introduction

I took this class in Fall of 2017. Right now, I’m just going to put down random notes.

Master’s Theorem

Examples:

Proving Big Theta

Definitions

• In-Place Algorithm: Sorts/whatever in the same data structure (doesn’t allocate new memory). i.e: Insertion Sort is in-place, while merge sort, which creates copies of the array within each recursive call is not in place.
• Initialization, maintenance, termination: is the same thing as induction. see this link

Matrix Chain Multiplication

Drawing out the recursive tree here makes it a lot more clear as to why we need dynamic programming for this problem–similar to drawing it out for fibnoacci.