study divide and conquer

1 files changed, 265 insertions, 0 deletions

diff --git a/notes.md b/notes.md
index 049f92c..dcc1a74 100644
--- a/notes.md
+++ b/notes.md
@@ -518,3 +518,268 @@ the rate of growth in determining computational efficiency for large inputs.
 * User friendliness
 
 Algorithms give you a language to talk about language behaviour.
+
+# 2.3 - Designing algorithms
+
+
+algorithm design techniques:
+
+* incremental approach (insertion sort)
+* divide and conquer
+
+2.3.1 - The divide-and-conquer approach
+
+they break the problem down into several subproblems that are similar to the original
+problem but smaller in size, solve the subproblems recursively, and then combine
+these solutions to creat a solution the original problem.
+
+Involves three steps at each level of the recursion:
+
+1. Divide: the problem into a number of subproblems that are all 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.
+
+The `merge sort` algorithm closely follows the divide-and-conquer paradigm.
+
+* Divide: dive the `n`-element sequence to be sorted into two subsequences of
+  `n/2` elements each.
+* Conquer: Sort the two subsequences to produce the sorted answer.
+* Combine: Merge the two sorted subsequences to produce the sorted answer.
+
+The recursion "bottoms out" when the sequence to be sorted has length 1.
+Every sequence with length 1 is already sorted.
+
+The key operation of merge sort is mergin two sorted sequences in the
+"combine" step.
+
+`MERGE(A, p, q, r)` where `A` is an array and `p`, `q`, and `r` are indices into
+the array such that `p <= q < r`.
+
+Merging takes `𝚯(n)` time.
+
+```plaintext
+MERGE(A, p, q, r)
+
+n1 = q - p + 1
+n2 = r - q
+let L[1..n1+1] and R[1..n2+1] be new arrays
+for i = 1 to n1
+  L[i] = A[p+i-1]
+for j = 1 to n2
+  R[j] = A[q+j]
+L[n1+1] = ∞
+R[n2+1] = ∞
+i = 1
+j = 1
+for k = p to r
+  if L[i] <= R[j]
+    A[k] = L[i]
+    i = i + 1
+  else A[k] = R[j]
+    j = j + 1
+```
+
+```plaintext
+A: [2, 4, 5, 7, 1, 2, 3, 6]
+    k
+L: [2, 4, 5, 7, ∞]
+    i
+R: [1, 2, 3, 6, ∞]
+    j
+
+A: [1, 4, 5, 7, 1, 2, 3, 6]
+       k
+L: [2, 4, 5, 7, ∞]
+    i
+R: [1, 2, 3, 6, ∞]
+       j
+
+A: [1, 2, 5, 7, 1, 2, 3, 6]
+          k
+L: [2, 4, 5, 7, ∞]
+       i
+R: [1, 2, 3, 6, ∞]
+       j
+
+A: [1, 2, 2, 7, 1, 2, 3, 6]
+             k
+L: [2, 4, 5, 7, ∞]
+       i
+R: [1, 2, 3, 6, ∞]
+          j
+
+A: [1, 2, 2, 3, 1, 2, 3, 6]
+                k
+L: [2, 4, 5, 7, ∞]
+       i
+R: [1, 2, 3, 6, ∞]
+             j
+
+A: [1, 2, 2, 3, 4, 2, 3, 6]
+                   k
+L: [2, 4, 5, 7, ∞]
+          i
+R: [1, 2, 3, 6, ∞]
+             j
+
+A: [1, 2, 2, 3, 4, 5, 3, 6]
+                      k
+L: [2, 4, 5, 7, ∞]
+             i
+R: [1, 2, 3, 6, ∞]
+             j
+
+A: [1, 2, 2, 3, 4, 5, 6, 6]
+                         k
+L: [2, 4, 5, 7, ∞]
+             i
+R: [1, 2, 3, 6, ∞]
+                j
+
+A: [1, 2, 2, 3, 4, 5, 6, 7]
+                            k
+L: [2, 4, 5, 7, ∞]
+                i
+R: [1, 2, 3, 6, ∞]
+                j
+```
+
+We must show that this loop invariant holds prior to the first iteration of the
+`for` loop of lines 12-17, that each iteration of the loop maintains the
+invariant, and the invariant provides a useful property to show correctness when
+the loop terminates.
+
+Initialization:
+
+Prior to the first iteration we have `k = p`, so that the subarray `A[p..k-1]`
+is empty.
+
+```plaintext
+for k = p to r
+```
+
+Maintenance:
+
+To see that each iteration maintains the loop invariant,
+we loop until we have reached the end of both `L` and `R`.
+
+```plaintext
+for k = p to r
+  if L[i] <= R[j]
+    A[k] = L[i]
+    i = i + 1
+  else
+    A[k] = R[j]
+    j = j + 1
+```
+
+Termination:
+
+When we reach the sentinal value for both L and R we stop.
+
+```
+MERGE-SORT(A,p,r)
+if p < r
+  q = [(p+r)/2]
+  MERGE-SORT(A,p,q)
+  MERGE-SORT(A,q+1,r)
+  MERGE(A,p,q,r)
+```
+
+Analyzing divide-and-conquer algorithms
+
+When an algorithm contains a recursive call to itself, we can often describe its
+running time by a `recurrence equation` or `recurrence`, which describes the
+overall running time on a problem of size `n` in terms of the running time on
+smaller inputs.
+
+We can then use mathematical tools to solve the recurrence and provide bounds on
+the performance of the algorithm.
+
+```plaintext
+Recursion Tree
+
+              -----------------
+              |1|2|2|3|4|5|6|7|
+              -----------------
+              /               \
+        ---------           ---------
+        |2|4|5|7|           |1|2|3|6|
+        ---------           ---------
+        /       \           /       \
+    -----       -----      -----    -----
+    |2|5|       |4|7|      |1|3|    |2|6|
+    -----       -----      -----    -----
+    /   \       /   \     /   |     /    \
+   -     -     -    -    -    -     -    -
+  |5|   |2|   |4|  |7|  |1|  |3|   |2|  |6|
+   -     -     -    -    -    -     -    -
+```
+
+Running time:
+
+`T(n)`
+
+Analysis of merge sort
+
+2.3-1: Using Figure 2.4 as a model, illustrate the operation of merge sort on the array `A = [3,41,52,26,38,57,9,49]`.
+
+```plaintext
+              -----------------------
+              |3|41|52|26|38|57|9|49|
+              -----------------------
+               /                  \
+      ------------             ------------
+      |3|41|52|26|             |38|57|9|49|
+      ------------             ------------
+      /          \              /         \
+    ------     -------       -------     ------
+    |3|41|     |52|26|       |38|57|     |9|49|
+    ------     -------       -------     ------
+   /     \     /      \     /       \    /     \
+  -      --   --      --   --       --   -     --
+ |3|    |41| |52|    |26| |38|     |57| |9|   |49|
+  -      --   --      --   --       --   -     --
+```
+
+2.3-2: Rewrite the MERGE procedure so that it does not use sentinels, instead
+stopping once either array `L` or `R` has had all its elements copied back to
+`A` and then copying the remainder of the other array back into `A`.
+
+```plaintext
+MERGE(A, p, q, r)
+
+n1 = q - p + 1
+n2 = r - q
+
+for i = 1 to n1
+  L[i] = A[p+i-1]
+
+for j = 1 to n2
+  R[j] = A[q+j]
+
+i = 1
+j = 1
+k = p
+
+while i < q and j < r
+  if L[i] <= R[j]
+    A[k] = L[i]
+    i = i + 1
+  else
+    A[k] = R[j]
+    j = j + 1
+  k = k + 1
+
+for k = k to r
+  if j >= r
+    A[k] = L[i]
+    i = i + 1
+  else
+    A[k] = R[j]
+    j = j + 1
+```