Follow me on Twitter for my latest adventures!

**33**Comments November 27, 2008

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

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 2^{m} subsequences of x. The running time thus is exponential O(n·2^{m}). 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 memo**r**ization). 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:

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.

## Comments

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:

Thanks for the excellent comment, Rod! I am now downloading the pdf :)

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..?

sadhan, that's the way it is... nothing you can do about.

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.

Can you please share this video with me.

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 :)

## Leave a new comment