Disclaimer: The notes below are fully/partially NOT created by myself. They are from slides and/or wikipedia and/or textbook. The purpose of this post is simply to learn and review for the course. If you think something is inappropriate, please contact me at “ryan_yrs [at] hotmail [dot] com” immediately and I will remove it as soon as possible.
Divide & Conquer
- To solve an instance of size n:
- Split into >=2 subinstances of smaller size. e.g. n/2
- Solve each subinstance recursively
- Combine solutions from 2. to get solution