diff options
| author | mo khan <mo@mokhan.ca> | 2021-11-21 15:26:51 -0700 |
|---|---|---|
| committer | mo khan <mo@mokhan.ca> | 2021-11-21 15:26:51 -0700 |
| commit | 771a9582dd36e81e5de81a914766c18860691f3f (patch) | |
| tree | c91c5bbf4f38426d494dead3930c06f8ee165a33 /README.md | |
| parent | 575b7cbdbefca2aab2ce004465b126d0e1b89d36 (diff) | |
add some notes on dynamic programming
Diffstat (limited to 'README.md')
| -rw-r--r-- | README.md | 20 |
1 files changed, 16 insertions, 4 deletions
@@ -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: |
