summaryrefslogtreecommitdiff
path: root/README.md
diff options
context:
space:
mode:
authormo khan <mo@mokhan.ca>2021-11-21 15:26:51 -0700
committermo khan <mo@mokhan.ca>2021-11-21 15:26:51 -0700
commit771a9582dd36e81e5de81a914766c18860691f3f (patch)
treec91c5bbf4f38426d494dead3930c06f8ee165a33 /README.md
parent575b7cbdbefca2aab2ce004465b126d0e1b89d36 (diff)
add some notes on dynamic programming
Diffstat (limited to 'README.md')
-rw-r--r--README.md20
1 files changed, 16 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: