Introduction to Algorithms November 27, 2008

# MIT's Introduction to Algorithms, Lecture 15: Dynamic Programming

<- previous article next article ->

This is the tenth post in an article series about MIT's lecture course "Introduction to Algorithms." In this post I will review lecture fifteen, which introduces the concept of Dynamic Programming and applies it to the Longest Common Subsequence problem.

Dynamic programming is a design technique similar to divide and conquer. Divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. Dynamic programming is applicable when the subproblems are not independent, that is, when subproblems share subsubproblems. A dynamic-programming algorithm solves every subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time the subsubproblem is encountered.

Dynamic programming was systematized by Richard E. Bellman. He began the systematic study of dynamic programming in 1955. The word "programming," both here and in linear programming, refers to the use of a tabular solution method and not to writing computer code.

Dynamic programming is typically applied to optimization problems. In such problems there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.

Dynamic programming can be effectively applied to solve the longest common subsequence (LCS) problem. The problem is stated as following: given two sequences (or strings) x and y find a maximum-length common subsequence (substring) of x and y.

For example, given two sequences x = "ABCBDAB" and y = "BDCABA", the LCS(x, y) = { "BCBA", "BDAB", "BCAB" }. As you can see there are several optimal solutions.

Lecture fifteen introduces dynamic programming via this longest common subsequence problem. It first gives a brute-force, exponential time algorithm for solving it. The idea of algorithm is to check every subequence of x[1..m] (m is the length of sequence x) to see if it is also a subsequence of y[1..n] (n is the length of sequence y). Checking takes O(n) time, and there are 2m subsequences of x. The running time thus is exponential O(n·2m). It is no good for large sequences and the lecture continues with a simplification - let's look at the length of a longest-common subseq and then extend this algorithm to find the LCS itself. The simplified algorithm is recursive in nature and computes the same subproblems. At this moment two dynamic programming hallmarks are stated:

• 1. Optimal substructure: an optimal solution to a problem contains optimal solutions to subproblems.
• 2. Overlapping subproblems: a recursive solution contains a "small" number of distinct subproblems repeated many times.

As the subproblems are overlapping, the lecture introduces concept of memoization algorithm (note that it's not memorization). A better known word for memoization is caching. The subproblems are cached (memoized) so that they are not recomputed over and over again.

The lecture ends with constructing a dynamic programming table for LCS problem and explains how to find a LCS from this table.

You're welcome to watch lecture fifteen:

Topics covered in lecture fifteen:

• [00:20] Dynamic programming.
• [01:47] Longest common subsequence (LCS) problem.
• [03:55] Example of LCS on sequences "ABCBDAB" and "BDCABA".
• [06:55] Brute force algorithm for LCS.
• [07:50] Analysis of brute force algorithm.
• [11:40] Simplification of LCS problem.
• [16:20] Theorem about LCS length.
• [18:25] Proof of the theorem.
• [30:40] Dynamic programming hallmark #1: Optimal substructure.
• [32:25] Example of hallmark #1 on LCS.
• [34:15] Recursive algorithm for longest common subseq.
• [36:40] Worst case analysis of the algorithm.
• [38:10] Recursion tree of algorithm.
• [42:40] Dynamic programming hallmark #2: Overlapping subproblems.
• [44:40] Example of hallmark #2 on LCS.
• [45:50] Memoization algorithm for LCS.
• [48:45] Time and space analysis of memoized algorithm.
• [54:30] Dynamic programming algorithm for LCS.
• [01:01:15] Analysis of dynamic programming algorithm.

Lecture fifteen notes:

 Lecture 15, page 1 of 2. Lecture 15, page 2 of 2.

Have fun with programming dynamically! The next post will be about graphs, greedy algorithms and minimum spanning trees.

PS. This course is taught from the CLRS book (also called "Introduction to Algorithms"). Chapter 15 is called "Dynamic Programming" and covers the topics in this lecture. It also explains the assembly-line scheduling problem, matrix-chain multiplication problem, elements of dynamic programming and optimal binary search trees.

<- previous article next article ->

Your website is awesome. Keep up the good work! I'm from the University of Florida and am taking the course on Data Structures under Dr Sahni.

Thanks, mbhinder. I enjoy doing this and I will keep up the good work! :)

Awesome work. keep it up!

Excellent work, awesome website one of my favorites.

Thank you,

Thanks redocdam and ba7eth! I am happy that you like my articles!

The last entry in the set of optimal solutions in your example should be "BCAB" :-)

Max Heap, thanks, fixed now!

The video of this lecture (at Google) seems to be cut short at 17:26.

RayNbow, holy smokes! I did not notice it (as I have local copies of videos on my computer). I am uploading a new version right now! It will be up in a few hours. Sorry about that.

Nice post. I remember this book from grad school. Known as the bible of algorithms, and it is condescendingly titled an "introduction." Dynamic programming was a fascinating topic. I really should refresh my knowledge of algorithms. The complexity level in CRUD apps in the real world lies mostly in architecture and design, not algorithms.

Here's an interesting article on Richard Bellman and the birth of Dynamic Programming.

An excerpt:

"An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical.

The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation.

What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities."

I love your website. Thanks so much for putting this up! It has been very helpful.

The Prof. gave at the end of lecture15 a hard exercise .... small space & recontruct LCS
I mean program homework and he gave hint: D & C
Divide & Conquer QUIZ
can you send the answer to this Quiz to me
Thanx for ur cooperation

i want to thank you for making these valuable lectures available online and want to thank the lecturer as well.

i just wants to say thx to whom, who had made this possible for me to view all these lectures available online .......

I have been following this lecture series and its awesome to say the least. However, the sound volume of this one is terrible.I tried streaming through Vlc player and increase the volume but no use. any ideas..?

wow!!!! i am th first timer but just bowled out by your site..good works..keep it up

I love your website. It's very useful for us. I am from Argentina. I have downloaded the video of this lecture in MP4 format (at Google) but I can't see it, possibly there is something wrong.
Thanks,

hi... ur web site is awesome...specially ur explanation on Chrome rocks...thanks a lot.. one thing about this lecture 15 is the audio tht come along. its too feeble to hear Dr Leiserson. I tried some few other places (including MIT OCW page) to get this video with a gud audio in particular...but not fortunate enough.. can u tell me some way to "amplify" or to make it loud..? thanks in advance.
-Arvinth

Hi arvinth. I used ffdshow's audio capabilities to amplify. Do you know what ffdshow is? It's a set of video and audio codecs, and when you run your video, it's used as primary decoder for both audio and video streams. Then I just set the master volume to something like 150% of original and all was good.

Thanks man...tht was a gr8 help to me.. now i have done something usefull with "ffdshow".... thanks again...

hai , one more question to put here.. currently i m looking 4 making karaoke mp3 s ( any audio format ) how much would ffdshow will help me in this.? i searched some tools but they r not helping.. will it end up in writing one karaoke software for my own using Filter algorithms? please help whether ffdshow can be used or i should go for some other tools.?

arvinth, ffdshow is just a video codec, it has nothing to do with karaoke. What you are looking for is avisynth. It's a video programming language and you will be able to make karaoke with it.

ur work is awesome..

Awesome Work. I read CLRS & ur notes before start the lecture video. Keep rocking man...

Thanks a ton for so much work. It is gonna help me finish my masters- paper on Algorithms. Thanks a ton. I've bookmarked this site/page. :) God Bless you. <3

thank you.

This is Richa from IIT BHU.
I want to learn dynamic programming and tried to access this video. But I dont have right to access it.
I really want to understand the basics of dynamic programmings.

The video says it's private?

Video seems private. Can you please make it public?

Please make the video accessible to me. I am Btech student from IIIT_Delhi and want to learn Dynamic programming.. please :)