work on exercises

1 files changed, 52 insertions, 0 deletions

diff --git a/notes.md b/notes.md
index 17129e5..d56c196 100644
--- a/notes.md
+++ b/notes.md
@@ -266,3 +266,55 @@ for j = 2 to A.length
     i = i - 1
   A[i+1] = key
 ```
+
+Loop invariants:
+
+* initializtion: it is true prior to the first iteration of the loop.
+* maintenance: if it is true before an iteration of the loop, it remains true
+  before the next iteration.
+* termination: when the loop terminates, the invariant gives us a useful
+  property that helps show that the algorithm is correct.
+
+Similar to mathematical induction, where to prove that a property holds, you
+prove a base case and an inductive step.
+
+
+Pseudocode conventions:
+
+* Indentation indicates block structure
+* Looping constructs `while`, `for`, and `repeat-until` and `if-else`
+  conditional construct have interpretations similar to those in C.
+* compound data is organized into objects which are composed of attributes.
+
+2.1-1: Illustrate the operation of INSERTION-SORT on the array `A = {31,41,59,26,41,58}`
+
+```plaintext
+a. [31, 41, 59, 26, 41, 58]
+     x   i
+b. [31, 41, 59, 26, 41, 58]
+     x   x   i
+c. [31, 41, 59, 26, 41, 58]
+     x   x   x   i
+d. [26, 31, 41, 59, 41, 58]
+     x   x   x   x   i
+e. [26, 31, 41, 41, 59, 58]
+     x   x   x   x   x   i
+e. [26, 31, 41, 41, 58, 59]
+     x   x   x   x   x   x
+```
+
+2.1-2: Rewrite the INSERTION-SORT procedure to sort into non-increasing instead
+of non-decreasing order.
+
+* non-increasing: descending
+* non-decreasing: ascending
+
+```plaintext
+for j = 2 to A.length
+  key = A[j]
+  i = j - 1
+  while i > 0 and A[i] < key
+    A[i+1] = A[i]
+    i = i - 1
+  A[i+1] = key
+```