From f5330397a71840404356f35fc42cb11d4befd366 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 24 Oct 2021 16:10:47 -0600 Subject: add some notes --- README.md | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) diff --git a/README.md b/README.md index d4e42d8..531d7ea 100644 --- a/README.md +++ b/README.md @@ -718,3 +718,25 @@ When you have completed this objective, you should be able to * [ ] Study Section 35.5 of the textbook. * [ ] Do Exercises 35.5-2 and Problem 35-3 from the textbook as part of Assignment 4. + +# Divide-and-Conquer + +We solve a problem recursively, applying three steps at each level of the +recursion. + +1. Divide the problem into a number of subproblems that are smaller instances of the same problem. +1. Conquer the subproblems by solving them recursively. If the subproblem sizes + are small enough, however, just solve the subproblems in a straightforward + manner. +1. Combine the solutions to the subproblems into the solution for the original problem. + +When the subproblems are large enough to solve recursively, we call that the +*recursive case*. Once the subproblems become small enough that we no longer +recurse, we say that the recursion "bottoms out" and that we have gotten down to +the *base case*. + +## Recurrenes + +Give us a natural way to characterize the running times of divide and conquer +algorithms. A *recurrence* is an equation or inequality that describes a +function in terms of its value on smaller inputs. -- cgit v1.2.3