add some notes on dynamic programming

2 files changed, 69 insertions, 4 deletions

diff --git a/README.md b/README.md
index 6c65d2e..e481060 100644
--- a/README.md
+++ b/README.md
@@ -242,15 +242,27 @@ It’s time to submit the problem set for Assignment 1 on the course home page i
 
 ## Unit 3: Dynamic Programming and Longest Common Subsequence
 
-Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to sub-problems. Why do we call it programming? In fact, programming in this context refers to a tabular method, not to writing computer code. The term dynamic programming was first coined by Richard Bellman in the 1950s, a time when computing programming was an esoteric activity practiced by so few people as to not even merit a name. Back then programming meant planning, and “dynamic programming” was conceived to optimally plan multistage processes.
+Dynamic programming, like the divide-and-conquer method,
+solves problems by combining the solutions to sub-problems.
+Why do we call it programming? In fact, programming in this context refers to a tabular method,
+not to writing computer code. The term dynamic programming was first coined by Richard Bellman in the 1950s,
+a time when computing programming was an esoteric activity practiced by so few people as to not even merit a name.
+Back then programming meant planning, and "dynamic programming" was conceived to optimally plan multistage processes.
 
 Why do we need dynamic programming?
 
-Divide-and-conquer algorithms partition the problem into disjoint sub-problems, solve the sub-problems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming applies when the sub-problems overlap—that is, when sub-problems share sub-sub-problems. In this context, a divide-and-conquer algorithm does more work than necessary and efficient!
+Divide-and-conquer algorithms partition the problem into disjoint sub-problems,
+solve the sub-problems recursively, and then combine their solutions to solve the original problem.
+In contrast, dynamic programming applies when the sub-problems overlap—that is,
+when sub-problems share sub-sub-problems.
+In this context, a divide-and-conquer algorithm does more work than necessary and efficient!
 
-The basic idea behind dynamic programming is eliminating overlapping recursive calls by using more memory to keep track of previous values.
+The basic idea behind dynamic programming is eliminating overlapping recursive
+calls by using more memory to keep track of previous values.
 
-I recommend that you to watch this video from http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/15
+I recommend that you to watch this video from:
+
+* [ ] Watch http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/15
 
 This unit will address the following topics of interest:
 
diff --git a/notes.md b/notes.md
index db9c506..7598d56 100644
--- a/notes.md
+++ b/notes.md
@@ -1469,3 +1469,56 @@ f(n) =  n
 | tight bound | theta |
 
 Useful when you cannot get the exact polynomial for a function.
+
+## Dynamic Programming
+
+Dynamic Programming means tabular programming or Dynamic Planning. This term was
+created before coding style programming was a thing.
+
+This is a design technique used to solve a class of problems.
+
+Example: Longest Common Subsequence (LCS)
+
+Important in computation biology like finding commonalities in two DNA strings.
+
+Given two sequences `x[1...m]` and `y[1..n]`, find *a* longest sequence common to
+both. "a", not "the" LCS.
+
+
+```plaintext
+x: A B C B D A B  | BDB
+y: B D C A B A    | BAB
+                  | BDAB
+                  | BCAB
+                  | BCBA
+                  = LCS(x, y)
+                   * functional notation but not a function it's a relation.
+                   * classic misuse of notation
+```
+
+Brute force algorithm for solving this algorithm.
+  * check every subsequence of x from 1..m (`x[1..m]`) to see if it's also a subsequence of `y[i..n]`
+  * analysis check:
+    * Q: How long does it take me to see if it's a subsequence of y?
+    * A: The length of y which is `O(n)`.
+    * Check = `O(n)`
+    * Q: How many subsequences of `x` are there?
+    * A: 2^m subsequences of `x`
+    * running time: `O(n*2^m)` (exponential time = slow!)
+
+Simplification:
+
+1. Look at length of `LCS(y, y)`.
+2. Extend the algorithm to find LCS itself.
+
+Notation: `|s|` denotes length of seq s.
+
+
+15.1 Dynamic Programming
+
+Dynamic Programming, like the divide and conquer method, solves problems by
+combining solutions to subproblems.
+
+Divide and conquer algorithms partition the problem into disjoint subproblems,
+solve the subproblems recursively, and then combine their solutions to solve the
+original problem.