This article is part of the article series "MIT Introduction to Algorithms."
<- previous article next article ->
MIT Algorithms

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:

MIT Algorithms Lecture 15 Notes Thumbnail. Page 1 of 2.
Lecture 15, page 1 of 2.

MIT Algorithms Lecture 15 Notes Thumbnail. Page 2 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.

This article is part of the article series "MIT Introduction to Algorithms."
<- previous article next article ->

Comments

mbhinder Permalink
November 28, 2008, 20:04

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.

November 28, 2008, 20:14

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

redocdam Permalink
November 28, 2008, 20:19

Awesome work. keep it up!

ba7eth Permalink
November 28, 2008, 21:11

Excellent work, awesome website one of my favorites.

Thank you,

November 28, 2008, 21:31

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

Max Heap Permalink
November 28, 2008, 22:06

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

November 28, 2008, 22:26

Max Heap, thanks, fixed now!

RayNbow Permalink
November 28, 2008, 23:06

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

November 28, 2008, 23:12

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.

November 28, 2008, 23:22

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.

November 29, 2008, 08:21

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

November 29, 2008, 16:57

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

Matthew Permalink
December 11, 2008, 05:38

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

Ra'ed Permalink
March 27, 2009, 12:36

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

mohammad Permalink
May 03, 2009, 20:44

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

nagesh Permalink
May 07, 2009, 12:13

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

sadhan Permalink
June 22, 2009, 05:02

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

June 22, 2009, 05:04

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

mumpi Permalink
November 12, 2009, 03:45

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

Nora Permalink
November 14, 2009, 23:47

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,

arvinth Permalink
December 03, 2009, 17:10

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

December 03, 2009, 19:26

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.

arvinth Permalink
December 06, 2009, 11:09

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

arvinth Permalink
December 19, 2009, 03:17

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

December 19, 2009, 08:06

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.

deepa Permalink
November 15, 2010, 19:40

ur work is awesome..

Dibyendu Permalink
October 13, 2011, 04:56

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

Ray Permalink
November 17, 2011, 11:04

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

September 17, 2012, 06:36

thank you.

richa gupta Permalink
January 04, 2013, 20:38

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.

Paul Permalink
February 09, 2013, 20:40

The video says it's private?

Vishal Permalink
February 21, 2013, 00:28

Video seems private. Can you please make it public?

AbhishekSingh Permalink
April 03, 2013, 13:59

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

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Type the word "antispam_108": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.

Advertisements