Mastering Dynamic Programming - A Real-Life Problem (Part 2)

🎬 Mastering Dynamic Programming: Part 2 - Let's Solve a Real-Life Problem 🎬

In the previous video, I talked about the basics of dynamic programming. I often get comments how dynamic programming is not useful in real-life. While it's true that most people don't use it on a daily basis, it's wrong to diminish its value.

Most of us use software that is uses dynamic programming to some extent on a daily basis, we just forget, or maybe we are not even aware of it. This is why I want to talk about two real life problems.

In this video, I will walk you through the fundamentals of the Git Diffing algorithm used to find differences between two files. It is based on the Longest Common Subsequence, which is well-known algorithm in dynamic programming.

🔑 Key Takeaways:

📌 Learning about real-life use-cases
📌 Understanding the fundamental principles behind Git Diffing Algorithm
📌 Understanding the Longest Common Subsequene Algorithm
📌 A step-by-step explanation of how to find the LCS, not just its length.

Dynamic programming is like a puzzle-solving technique, and this video is your ultimate guide to fitting the pieces together. Get ready to elevate your coding skills and witness the art of optimization in action.

🚀 If you found this video helpful, don't forget to like, share, and subscribe for more tech tutorials!

🔗 If you enjoy trhis video, please like, share, and subscribe for more enlightening tutorials. Join the dynamic programming journey today!

Useful links and resources:

🔗 Connect with me:

Support me on patreon:

LinkedIn:

Join my discord:

Follow me on Instagram:

Follow me on Twitter / X:

Timecodes:
00:00 - Intro
00:57 - Longest Common Subsequence Problem
03:12 - Greedy Approach
04:10 - Dynamic Programming Approach
09:14 - LCS DP Implementation
10:18 - LCS Reconstruction Idea
11:40 - LCS Reconstruction Implementation
12:46 - Text Diff Idea
14:50 - Outro

[TechWithNikola]

Mistakes in the video:

- At 02:39 the LCS is [2, 3, 4] and its length is 3 (not 2 like I say in the video). Apologies for this mistake. Thanks @davidkumari1420 for pointing this out.
- I suspect there will be more...

[puneetkumarsingh]

This is mind blowing stuff! I have now known about the LCS problem for about 4 years. But it had never occurred to me it had such a common use case. I use Gitlab on a daily basis in my job which has this diff feature used whenever we create a new merge request. But I never pondered how it worked under the hood. Really thank you for posting this!!

[SadgeZoomer]

2:39 [2, 3, 4] is the longest subsequence

[wenhanzhou]

I rarely use DP explicitly in my proffesion, but in real life, I use the principle of saving the checkpoint of important tasks so I avoid redoing stuff. For difficult problems, I work backwards, asking myself, can I start by solving a simpler problem to begin with? After recursively working a couple of steps backwards, I end up with a super simple task, and the rest just follows effortlessly.

[samarth]

You have an extremely intuitive way of teaching!!

[uaua-qmgp]

Love the practical example in the end. Well done!

[dyutisharma]

Please keep up the good work, need more explanations like this. Also bring-in more real-life problems solved by DSA.

[khalidben]

Cool stuff. I used git for longer but never thought that this algorithm was used in it. This is an eye opener. I have to say that our faculties failed in this regard, they would ask to implement and understand the logic of the algorithm but they never talk about the use cases. Knowing why is really great.

[bot-bot]

Can't wait for the next DP video. Thanks Nikola! 😀

[e-k]

amazing content! happy to give the 1000th thumbs up

[ujjwalaggarwal]

please keep this up love these videos explaining real world stuff

[rafa_br]

Good video! I'd love to see a video about the Quine-McCluskey algorithm or more neural network stuff.

[Daniel-sywo]

Great video!!! One nit pick is that around 9:45 you mention that if the “last” elements are equal then we pick them. I was confused because I thought you meant the last elements in the list (eg. a[-1] in python), and I assumed I wasn’t understanding the syntax. Turns out you meant the last as in the previous elements. Words can be ambiguous sometimes but maybe it’s just that Im not a native speaker. Awesome job explaining though!

[korigamik]

This is really cool! Can you tell us what you use for animations and highlighting the code in the video? Maybe share the source code?

[megaxlrful]

Fantastic video! It is a really clear explanation on DP :-)

[pedramhaqiqi]

Could you help me understand the case where there is an existing 9 before the one in B, and why we "dont need to consider numbers past that in B" therefore it is in the optimal solution?

[DoChDev]

Overall a great video, but I have one point for improvement: The animation starting at 13:42 is not in sync with your spoken explanation, which I found confusing. For example when you said "... to start with the first line in the longest common subsequence", the animation already showed the added and deleted lines.

[mathijsstevens]

Could you make a video on the cutting stock problem? There are other video's about it but none of them seem te be as clear to me as your video's.

[codinginterview]

I don't think DP is hard until I see this real life example, LOL

[CurtisCanby]

In the first example with longest common subsequence, where A=[1, 2, 3, 4] and B=[2, 3, 4, 5]

You didn’t mention 2, 3, 4 as the longest common subsequence. You had 2, 3 as the longest. Is 2, 3, 4 not the longest?