Lecture 20: Dynamic Programming II: Text Justification, Blackjack

MIT 6.006 Introduction to Algorithms, Fall 2011
View the complete course: ocw.mit.edu/6-006F11
Instructor: Erik Demaine
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@sergeykholkhunov1888]

00:00 review of last lecture 05:53 five "easy" steps to DP 08:40 step 1: define sub-problems 09:51 step 2: guess (part of solution) 11:06 step 3: relate sub-problems 13:15 step 4: recurse and memoize or build DP table bottom-up 15:28 step 5: solve original problem 17:05 text justification 35:12 parent pointers 38:50 blackjack

[@gangamanna4647]

Thank u

[@aamike82aa]

Text justification starts at 17:06 Blackjack starts at 38:51

[@mustaghees.b]

aamike82aa I will thank you later

[@maxim9280]

благодарю

[@faiazmahmud6277]

​@@maxim9280no

[@vvfking]

Having this guy as the lecturer in the course I'm taking (Algorithms, design and efficiency) would make the course so much more interesting and easier to follow. Thank you & MIT for these educational videos!

[@TheR971]

I am 3 years late, but damn this is some weird punctuation.

[@abishekkachroo938]

@@TheR971 I am 4 years late but still its weird

[@neuron8186]

@@TheR971 i am 5 years late but still weird

[@chasewarren9702]

@@TheR971 I am 6 years late but still weird

[@coldfire6869]

​​@@TheR9717 years late, pretty weird

[@stefanalexandru2363]

this professor is awesome

[@pulkitsharma828]

Certified genius.

[@siddhartha.saif25]

I love Erik Demaine. He is unbelievable. All great lectures! Thanks Erik.

[@casperdewith]

*caption errors* 5:10 sub-problems we get, → sub-problems, we get 9:11 to counter → to count 10:06 There’s nothing. → There’s nothing- 12:50 n degree → indegree (also at 12:53) 12:57 again the → again, counting the 19:09 an anesthetic → an esthetic 19:36 python → Python (also at 25:16 34:27) 19:39 J minus 1 → j minus 1 32:57 top logical → topological 34:06 [INAUDIBLE] → Can you explain what DP of j would return? 39:20 sheet → cheat 41:33 this → in this case 50:22 BG → BJ (also at 50:24)

[@mitocw]

Thanks for your feedback! We've corrected the captions.

[@julianarezende4849]

I was so demotivated about studying and my exam is tomorrow! Erik excitement motivates me somehow. He's really passionate! :)

[@lucasandrade7421]

Hi, I know its kinda late, but I hope the exam went well for you

[@DIPTANGSHUMISHRA]

@@lucasandrade7421 She has probably forgotten all about the exam at this point.

[@Deepaksingh-ls3xj]

Best one...lecture filled me with lot of energy

[@csl1384]

The "5 Steps" are pedagogical gold

[@tentotheace]

49:15 That's what *he* said.

[@EOh-ew2qf]

literally paused the video to search for comments

[@robertalaverdyan3150]

Excellent. for me watching these lectures is like watching moves : relaxing but very useful and entertaining

[@greagarious44]

He was a child prodigy !! Genius is the word !!

[@stjepanbrkic3215]

+greagarious44 guy became bacc. at age of 14, holy crap

[@skc909887u]

really good insight at 4:30 DP is really finding shortest path in a DAG

[@pablogarin]

It makes sense to cube the result to obtain the badness: you preserve the sign, so you can know if your line is too large or too small...

[@ih9346]

was thinking the same

[@chaddaifouche536]

No, if your line is too large, the result is +∞, the cube is probably simply a choice made after trying some values for the exponent and looking at the esthetics of the results. It ensure that big divergences from the line width are heavily penalized.

[@richardbrks]

So is the optimal solution of a DP the longest or shortest path of a topological sorted DAG? I know Dr. Demaine states shortest at the beginning, but at the end it seems that he meant longest path for the black-jack example? Perhaps it matters if you guess is searching for the MIN or MAX of a series of choices, which i think would be fine since I believe finding the the longest or shortest path is linear time for topo. sorted DAGs.

[@sir1cyr]

"But that's what dynamic programming is for -- you don't have to think." (21:58)

[@sirnawaz]

In that context, it makes so much sense. In fact, I'd say it is such a relief, as you don't have to think about all the things!

[@davemartin157]

Erik Demaine is clearly brilliant. I believe occasionally his teaching to commoners could be improved with more time spent in advance so that he doesn't correct his algorithms midway through, but I is plausible that, for the good of humanity, his time may be better spent on his research.

[@bjdooi]

if he didn't have the opportunity to constantly reinforce his foundations and find new ways of looking at things he knows, he wouldn't be able to accomplish as much. Exercising your foundations is extremely important for anyone trying to make advancements in anything. So in a way, him teaching is tied directly to his research

[@isbestlizard]

dynamic programming in 5 easy steps that silicon valley don't want you to know!

[@apoozeo1715]

Name of the red book on the table at 41:55 please? Is it Skiena's Algorithm Design manual?

[@EstebanFilardi]

Hehe, I don't think it's a book. It's the "box" container of the big cards he uses.

[@tririverwangyi]

The "latest" Word as of 2013 does not have smart line justification. Now it's 2019 Word still does not have it. From time to time I have to delete/change a word to make the next line not too ugly...

[@kevnar]

Black-haired girl was on time this class.

[@CRBarchager]

No. Came in at 2:54

[@user-hs7qg5tt8t]

hahahhahhhhhhhha~~

[@ogunsadebenjaminadeiyin2729]

Racist. lolzz hahaahhaha.

[@TrungNguyen-ff7dw]

@@ogunsadebenjaminadeiyin2729 how's that racism? can you explain me?

[@martinharris4416]

75% boys in class be like

[@biuku]

16:46 -- Text justification 38:50 -- Blackjack

[@akarshrastogi3682]

Somewhere in India, I mention to my mom, do you know who this guy is? He's a prodigy, now he teaches at MIT and I can't wait to watch each of his lectures, here on my laptop. Thank you MIT, Eric, the Internet and Computer Science in general for existing and making all of this possible.

[@siaahmadi413]

I wonder how you'd handle the value of Ace in the blackjack algorithm

[@LT1FirebirdSLP]

Parent Pointers begins at 35:17

[@maninandadeepmedicharla6213]

this guy is brilliant !!

[@brunonegraozica5459]

I would love to see an implementation of the "Text Justification" algorithm

[@antoniodingyi]

Give it a try: leetcode.com/problems/text-justification/

[@csl1384]

20:48 "why cubed? who knows". I wonder if this is to penalize big badness in an exaggerated way compared to small badness (so that, say, a badness of 2 is not twice as bad, but 8 times as bad as a badness of one). It seems to me that the effect of this is to favour justifications with a large number of lines that are just a little bit bad, over justifications with a few very bad lines. It sort of reminds me of the different error/objective functions in machine learning, if you know what I mean. The exponent (the 3) could be regarded as a (meta?) parameter of sorts, and it might even make sense to apply machine learning to text justification, where the optimal value for this exponent is learned from a large number of texts that were manually justified.

[@skillfullSwaroop]

thanks for the 05:53 - five "easy" steps to DP

[@hardikchawla645]

Great explanation

[@eepassion9720]

40:28 that Hoodie Shirt meaning MIT :) for who curious

[@awesomedude824]

I was so proud of myself for figuring that one out XD

[@CyberMew]

How does the equation become MIT? Edit: ah ok a quick google on Pv/nr shows the reasoning in a Quora post

[@KirollosSamyHakim]

For the text justification problem, I guess that it'd be more efficient in practice to work with prefixes rather than suffixes. Because as the user types new words we can extend our solution from n words to n+1 words easily just guess where the last line begins and minimize over all the possibilities. That wouldn't be possible with the suffixes as for each new word typed we would have to start from scratch.

[@turinreza]

For blackjack, if you use suffix don't you start from the end where i is from # to 0? Say for example for 52 cards (standard) what happens if and when the algorithm decides that the first hand starts at card 2 but you need 4 cards to deal with? Doesn't that mean that hand is scrapped since you only have 2 cards to start a hand?. And when you actually follow the output of the algorithm the first hand will actually use 4 cards instead of 2 and the output is meaningless since the first hand has started with 4 cards in reality instead of 2 (meaning everything shifted over by 2 cards and you can't use the output anymore) that the algorithm thought would be discarded? Isn't this the reverse?

[@laurietsao8733]

OMG, basic strategy is to hit soft 18 vs 9 or T. Victor erred on both hands. Casing the entire deck makes much more for baccarat, not blackjack. And in reality you'd double, split, and change the number of hands. It gets more interesting if you have partial omniscient information, say suborderings of cards.

[@eknuds]

I was thinking about these problems. My background in desktop publishing as the network administrator in my college newspaper tells me that there would have to be character by character kerning(min and max) and a hyphenation database to properly be able to break words up. Blackjack, there could be a weighted probability. Ten or below, always hit. 21, never hit. Fifteen, maybe 0.5 probability of hitting.

[@nagesh71086]

Did the camera person change or something? I got headache after a while, not because of Erik or the content, but heavy camera movement!

[@vaibhavbansal7470]

Can someone pls explain to me why, in the Shortest Path example, total time is written as O(VE) when #subproblems = O(V^2) and time per subproblem = indegree of the vertex. I am thinking it should be O(E.V^2). Can somebody pls explain ?

[@strongark]

V^2 is just an initial rough estimation of Erik. When moving forward to recursive algo, at each step (or each vertex), the algo just tries with all incoming edges of that vertex (not all edges, that's why it's not V^2). Because the total number of edges is E, so we have O(V*E) as a more accurate estimation for this algo

[@sakcee]

@Mit Opencourseware, is the homework, labs and other handouts available for this lecture

[@mitocw]

All materials for this course are available on ocw.mit.edu/6-006F11. Best wishes on your studies!

[@sudhanshudey758]

Thanks for this wonderful idea of open source education! No wonder you are the best engineering institute in the world both in terms of quality of studies and in terms of kindness and compassion for students all over the world. May you continue to give such high quality educational content forever !! :))

[@sudhanshudey758]

You are truly great!

[@abhishekganesan7081]

25:55 ; How is the time complexity 2^n, if we try to fit in every word into the a single line, then abort and repeat?

[@egor.okhterov]

For every word out of n words we have to consider a choice of whether the current word starts a line. If a word starts a line we can denote it as '1'. If it continues some line, we think of '0'. So we can think of all the words as a binary string: 0100011101. Each bit corresponds to our choice for that word. n-word text corresponds to some binary n-bit string. There are 2^n possible binary strings, so there are 2^n possible choices to split the n-word text.

[@AlanKao-fc4km]

Is it possible that we reduce the runtime of text justification to O(n) by memorization, like we do with fibonacci number ?

[@spicy_wizard]

for the text justification, i cant see where the memoization happens. To me, DP(i) is a recurrence function that elaborates the subproblems and min(dp for j in range(...)] is just gonna calculate all the possible new lines. I guess we are to maintain a memo table in the course of bottom up actions which are automated at the end of recurrence? is the job of the memo table to record the dp of i onwards that might have repeated in the course of elaboration？

[@toebel]

The memo is just there to store the return value of the recursive calls. Once you have the recursive case, the only thing you need to do to make it a "full" dp solution is use a memo to avoid recomputing the same subproblem more than once

[@chaddaifouche536]

@@toebel Yes, or use the topological order you identified to do a bottom-up fill of your memo and change your recursive calls to read your memo table instead.

[@fgfanta]

I have a hard time finding how "page width" is actually computed in badness(i, j).

[@naveenrawat6278]

It is fixed for all pages. You don't compute it.

[@shrreyabehll2727]

at 49:00 , why is the range from(i+4,n)? what does 4 in i+4 signify?

[@minh_tran]

Because initially both player are dealt with 4 cards in total

[@georgefei]

Could someone help me understand why the number of subproblems is n for both text justification and blackjack?

[@dhaval12593]

Well, the way I would think this is in the worst case we can have only one word per line ( given each word is line length long) and hence at amximum we can have n subproblems...

[@direitoemtela]

I'm watching this video at 2x speed and it just looks like Erik had waaaay too much coffee before coming to the lecture.

[@siouxperirish]

Also very accurate fast-chalk technique

[@jayeshsonkusare3087]

You sure it's coffee and not lsd?

[@adhoc3018]

@@jayeshsonkusare3087 ?

[@shauryahanda2901]

could any one guide me which book to use for this topic cause cormen is actually not taking up these algos

[@mitocw]

From the syllabus: "For the student who finds books helpful, we also suggest: Miller, Bradley, and David Ranum. Problem Solving with Algorithms and Data Structures Using Python. 2nd ed. Franklin, Beedle & Associates, 2011. ISBN: 9781590282571." See the course materials on MIT OpenCOurseWare for more information at ocw.mit.edu/6-006F11.

[@ChathuraJayalath]

Its a Portal t-shirt.. man i love that game :D

[@PinkuDebNath]

Nice lecture! But still did not understand shortest path :(

[@ytuser659]

But how do we add memoization to the recursive text justification algorithm?

[@chaddaifouche536]

As he said, adding memoization is an automatic process : you write the recursive version, putting your result in a variable whose value you return at the end of your recursive function, then you take this version and add a global dictionary, at the start of your function you check if the answer for your argument is already in the dictionary and returns it if it is, at the end of your function, you add the return value to your dictionary with the argument as key. In Python, there's even a decorator @cache in functools to do it automatically on any function.

[@shibyurehash5205]

anyone have idea why does in degree(v)+1 come from, to be exact, the "+1" come from?, I have thought about it quite for some time, still unable to figure it out.

[@cerlaneL]

Shibyu Rehash In event that there is 0 edge, u=v=s, that is the "+1" I believe.

[@BorisChiou]

Super exciting~~~ I like this~ haha

[@srikantaggarwal6016]

Well shouldnt the j vary from i+1 - n in the text justification problem ?

[@AbstractAbsorption]

In Python notation, the lower bound for range is inclusive, the upper bound is exclusive.

[@brunonegraozica5459]

I didn't understand the "suffixes", at 25:00. what is that for?

[@dhaval12593]

I think it means given an array of words say words[] and u fit in 0 to i words in line 1 (say for example) and the sub problem is reduced to remaining words in array words[] ( suffix ) which fill in the remaining lines.

[@egor.okhterov]

Consider some array a[4] = { 2, 15, 42, 13 }. Here are all of the suffixes of that array: a[0..3] = { 2, 15, 42, 13 } a[1..3] = { 15, 42, 13 } a[2..3] = { 42, 13 } a[3..3] = { 13 }

[@inferious777]

An algorithmic problem I was trying to solve required Dynamic Programming (Kickstart 2020 Plates) as the optimal solution. Scratched my head so much looking at the solution and time complexity thinking : "isnt this just brute force?".

[@Kevin-ux5xf]

What is wrong with packing as many words as you can into each line of text? Isn’t that how word processors are supposed to work?

[@researchandbuild1751]

Cubed..i wonder if its rule of thirds?

[@janmichaelaustria620]

51:30 "You can do it, its not that hard" Statement for every DP solution ever LMAO!

[@JanacMeena]

35:16 - Parent Pointers

[@isaacweaver2188]

At 33:23 shouldn't the run time actually be O(n(n+1)/2) instead of O(n^2)? If you think about it as starting with i = n - 1 and working backward to i=0, then the for loop iterations in the min statement will look like this: range(n, n+1) - 1 iteration range(n - 1, n+1) - 2 iterations range(n - 2, n+1) - 3 iterations ... range(0, n+1) - n iterations The runtime should just be the sum of integers 1 to n, which by induction is n(n+1)/2 which is significantly faster then n^2

[@junzhai1715]

usually we don't worry about constant factors in big O notation. O(n(n+1)/2)=O(n^2)

[@isaacweaver2188]

@@junzhai1715 Where's the constant factor? O(n(n+1)/2) = O((n^2)/2+n/2)

[@junzhai1715]

@@isaacweaver2188 O(0.5*n^2+0.5*n) the constant factor 0.5 does not matter in the big O notation. Also 0.5*n grows slower than n^2, so it can be removed.

[@nikoladd]

List of remaining items is called "tail". It's a thing in functional programming.

[@MeLawenity]

tail is second item onwards, suffix is more general

[@nikoladd]

@@MeLawenity no. It's everything after the named variables. I.e. the remainder.

[@sonduongvan7010]

49:48 to 50:12 Can someone explains me why j equal to i + 4 + #hits +#dealer-hits? Thank you

[@sonduongvan7010]

@@yicheng1991 I still can't understand. i is the number of cards played now, isn't it? So, I think i include 4 cards played at begin of the game. Unless each round we play at least 4 card, we don't need plus 4 to i. It's my way of understanding Blackjack's rule, is it wrong?

[@sonduongvan7010]

@@yicheng1991 If i doesn't include 4 original cards, j also doesn't include them. But j=i+4+#hits+#dealer-hits => j includes 4 played cards. It's a little conflict.

[@sonduongvan7010]

@@yicheng1991 OK I understood it. i, or j, or whatever passed into BJ() functuion is the number of cards played of previous 'rounds'. Your answers are usefull for me. Thank you!

[@mohitrao7800]

Can somebody explain, Why was 1 added to indegree(v)? At one point he says it's for memorization(12:55) and then at another point he says it's account for 0 edges(10:25). Great lecture! Thanks Erik and MIT.

[@anujsingh2836]

total count including 0.

[@mistadeji]

it's coming from the base case. remember your recursion should have a base case. In a case when you compute shortest from point S to point S. the length of that path is zero because you didnt do any work and your recursive algorithm can just return zero

[@brooklyna007]

Professor: " This talk will be about DPs and BJ with some text justification." Interviewer: "What about BJs?" Professor: "About BJ, (as I said at 49:15) if I've already busted, I can't hit again" Interviewer: "But what is the general starting point?" Professor: "Well the base case for a 2x3^2 problem is 18 but as I said at 49:18 : maybe I take another hit , maybe I take another hit again, maybe I take another hit again. At some point I go over 21 and then you have got to stop the for loop." Interviewer: "What exactly are we talking about? Weed? Young women?" Professor: "Absolutely not. THIS IS COMPUTER SCIENCE! (/SPARTA) =D"

[@ramnathtejachekka7090]

Okay, now my question is what to do with the infinite loop on Erik's T-shirt!!

[@seansmith1685]

King

[@benyaminbeyzaie301]

Did any one has taken notes from these lectures?

[@mitocw]

Lecture notes are available on MIT OpenCourseWare at: ocw.mit.edu/6-006F11. Best wishes on your studies!

[@benyaminbeyzaie301]

@@mitocw Thanks!

[@cskcsk6370]

Did he explain what he means by badness? Is it just me where I feel he just brushed very vaguely on these subjects? Is that the intent?

[@EscapedConvict2007]

I think he explained "badness" very clearly, he even wrote the formula on the blackboard.

[@anshprakash1778]

What is DAG?

[@prathmeshbhadekar121]

Directed Acyclic Graph

[@JanacMeena]

38:52: Blackjack

[@AdarshGupta-dk5py]

Why word's strategy is not better

[@ianhart8037]

Good old chalk talk

[@jdkoz98]

This is so far over my head wow lol

[@giovaniventrue3420]

Why cubed? Who knows.

[@kb3khs]

That text justification recurrence is really hard to follow. I see a for statement with no body.

[@Anythingforfreedom]

Do MIT students ever ask questions?

[@kaushiksurikuchi]

Actually the "shortest paths in some DAG" perspective for dynamic programming could be a very slippery slope

[@Taabro]

How so?

[@chrysistef4514]

You realize that those of you who understand have SUPERPOWERS 😅🤪

[@ShubhamSinghYoutube]

Ah, Counting cards.

[@fouchimiousmane1119]

This doesn't really help much. How would you define badness?

[@acestrike40]

any 50.004 students?

[@researchandbuild1751]

I dont get it...sorry..

[@TheMasonX23]

I thought everyone at MIT knew how to play blackjack... :P

[@adhishmalviya2408]

Bolo siyavar ram chandra ki jai!

[@adhishmalviya2408]

This is what i said when I finally got it..

[@txm2124]

In text justification problem, shouldn't the number of ways to arrange n words be 2^(n-1) ?

[@ChrisLeeX]

+Tushar Mehta Yes. It is one of the many errors in this lecture.

[@victoro1152]

+Tushar Mehta No. Because your words must be "consecutive". So you basically think: Should I take the first word? the first 2 words? the first 3 words?...or the first n words?

[@kenichimori8533]

Prober Proof

[@grad201187]

I dont understand this! :(

[@joebrady9829]

Watch the first 20 videos for the class

[@ariabanazadeh1016]

Youre a bitch

[@applepuddings795]

Please take lectures

[@kennethhom2935]

The explanation for the Text Justification Algorithm wasn't convincing. The professor missed step 5 in solving the original problem. The lectures need to show the pseudocode at the very end so that we can verify it for ourselves. dp[j] + some random function Isn't an acceptable solution. You have to break it down into a concrete definition otherwise it does not help.

[@GucciJohanne]

maybe pick a demonstrator that isn't glued to their ipad tetris game

[@moeinkasraei2114]

اهل مدرسه را به اهالی مدرسه پاس می دهند ،مگر خودشان اینرا نمی خواهند واهل تحقیق همدیگر را می شناسند

[@Frankhuaylinosvelasquez]

Those 5 guys who until this moment gave their dislikes I believe they are taking courses at high school. Btw, this professor is amazing! He motivated me much more that I usually used to be doing.

[@florianwicher]

"I didn't realize that all problems can be expressed as DAGs" - You can describe all finite state machines as DAGs, no?

[@iliasp4275]

can't belive he said "the n-word" so many times and got away with it

[@mystmuffin3600]

49:17 😳

[@NickKravitz]

Pretty poor demonstration of the BlackJack game. Eric took a dealer hit on 17 which is not allowed. Victor incorrectly stood on soft 18 against a 9 and 10. An intuitive explanation of why the dealer has an advantage is that he gets to go last i.e. if both player and dealer bust the player busts first and loses. The cheating method of a perfect information deck was accomplished in the 1970s by a cheat swapping in his own pre-arranged shoe for the dealers. This resulted in the card shoes being chained to the BlackJack table. On the upside Eric has great handwriting. fun lecture overall.

[@nick1f]

If the player does not see one card of the dealer, he will not know if his two cards are better. I think the advantage of the dealer is not that the player may bust first. If the player gets two cards that total 21, he does not receive double his money - he gets less and this is the house advantage. Many years ago I simulated a blackjack game where the player was playing using the same rules as the house and in the beginning I did not understand why in long term the player always loses.

[@ariabanazadeh1016]

Its not about playing black jack!!

[@cla2008]

how is this different from original word greedy approach? this is the greedy approach. just take as much as you can on one line and recurse

[@CyberMew]

That’s the original way Microsoft did it. This DP way looks at all possible combinations to get the best

[@mikewakefieldgeller4164]

11 minutes in ..any questions? No.

[@Hadoren]

Yeah unfortunately this was really confusing. No code examples, no clarity, just random babble that left me utterly confused.

[@dscheme4427]

lol, super nerds front-row

[@applepuddings795]

Such lectures are never free people pls young people if u are plannig to go for any university then also u have to pay like I am paying

[@pablogarin]

hearing "DP" and "BJ" in a video made me wonder if I was watching the wrong kind of video :V