Mastering Dynamic Programming - A Real-Life Problem (Part 2)
Vložit
- čas přidán 6. 06. 2024
- 🎬 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:
Source code: github.com/freezing/data-stru...
Myers Algorithm: www.xmailserver.org/diff2.pdf
Introduction to Algorithms by Cormen (affiliate link): www.amazon.co.uk/Introduction...
🔗 Connect with me:
Support me on patreon:
/ techwithnikola
LinkedIn:
/ nikola-stojiljkovic-67...
Join my discord:
/ discord
Visit my blog: techwithnikola.com
Follow me on Instagram:
/ techwithnikola
Follow me on Twitter / X:
/ techwithnikola
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 - Věda a technologie
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...
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!!
Thank you for taking the time to comment. I’m so happy to hear that it was insightful. It is common that people don’t realise how useful DP is in practice. Please consider sharing this video. It would help me grow this channel.
You have an extremely intuitive way of teaching!!
Thanks, I appreciate it. That’s great to hear!
2:39 [2,3,4] is the longest subsequence
Oops! Thanks. In my mind I had an example where LCS was 2, I didn’t realise that 4 should go as well, despite watching it many times :-)
please keep this up love these videos explaining real world stuff
Thank you. Will do. If you have any ideas for future videos please let me know.
Please keep up the good work, need more explanations like this. Also bring-in more real-life problems solved by DSA.
Thank you. I have a few more ideas in mind and will start working on them after holidays!
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.
Glad you've enjoyed it :) It's true that most schools put most efforts into explaining how things work, but very little towards why. Some people, including myself, find it hard to motivate themselves to learn something without understanding why.
Finally!
Thanks for uploading!
:-) sorry it took a while. It’s difficult to find spare time to work on videos. Let me know what you think about this one. I’d really appreciate the feedback.
Cannot wait to watch the sequel
Can't wait for the next DP video. Thanks Nikola! 😀
Glad you liked it! Hopefully I’ll find the time soon to make another video 😀
@@TechWithNikola hey man i need another video! also can you discuss 'target sum' in detail
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.
Fantastic video! It is a really clear explanation on DP :-)
Thanks a lot :)
Good video! I'd love to see a video about the Quine-McCluskey algorithm or more neural network stuff.
Thank you. I've written this down and may cover it at some point, but I can't promise that this will be any time soon.
@@TechWithNikola thank you very much :D
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!
That’s a good point. Thanks for the feedback.
I’m glad to hear you’ve enjoyed the video. Thank you for taking the time to leave a comment (and apologies for the late response)
Very good!
Thank you!
Thank you!
You’re welcome!
You got the subscriber!❤
Thank you ❤️
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.
Glad to hear that you've find my videos clear. I have written this down and I might get to it at some point, but I think it will be a few months from now.
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?
Glad to hear that. You’re welcome. I used Keynote on MacOS for code animations. There is no source code for that.
I also use powerpoint and sometimes Manim. I haven’t used Manim for this video.
Cool stuff
Thank you!
you-made-a-great-video-i-love-it.
I-have-been-trying-to-solve-this-problem-but-i-couldnt.
This-is-really-helpful-thanks.
I-will-learn-more-about-dynamic-programming.
Thank you for the comment. I’m glad it was helpful!
Hello, I'm a new subscriber to your your, I want to thank you because I was able to apply dynamic programming in one of the software solution project in one of my subject and my prof finally approved it since it is not inefficient anymore. If it is okay with you, may I request a video about parallel programming, asynchronous programming, and multi-threading? I tried reading some materials and have asked edge's bing ai and chatgpt to help me understand those techniques of programming(I do not know if it is the correct term for all of them and I am not sure if those are programming paradigms) but your way of explaning things made me understand the logic in those technique. Thank you for your time reading my comment.
Hello, thank you for the subscription and for taking the time to write this comment. It's really appreciated.
That's very exciting. It's not common to use DP in real-life, but I'm very excited when I hear people have done that. I'd like to hear more about your project if you're willing to share.
Regarding videos about parallel programming, async, and multi-threading, I would love to make videos on these topics, and I will. However, I can't promise that this will happen any time soon. The reality is that it takes a long time to make these videos, and I only do it when I have free time, but I have added these topics to my queue.
@@TechWithNikola Thank you for taking you time replying with me, The project I'm currently tasked with is somewhat of a capstone project on web development. I can't really say much since it is a ERP system and each of its module is divided to each group in every block of students. Each group is tasked with handling a single module or section of the system. My group is focused on the Behaviour module. I was able to adjust the time complexity from O(n^3) to O(n) and add a feature that was requested by one of the panelist during the defense. The feature involves Automated Penalty Calculation and Violation Tracking and Management. The first implemented logic was labeled as "inefficient for simultaneous reports" or "slow in handling mass number of reports in one go", the said panelist gave some scenarios where the speed of execution and processing of each feature is detrimental thus our implementation of the request was rejected. I was already studying on how to save information so that it can be used for future references, I've come across solutions like caching but with me and my groupmates knowledge, applying caching is hard specially since the tech stack we are required to use is unfamilliar with us (since it is the first time we are using it). We also thought of using a separate database but that would require changing the architecture of some part and we had an argument with the group tasked for back-end integration, the outcome was we did not create a new one. Then I've come across a topic on dynamic programming on a short on youtube and my search began, a lot of video is complicated and some are hard to replicate but when I've watched you video I was somehow able to replicate and apply somewhat of a hashmap to replicate the memoization.
I can't really talk about a lot of stuff since we are going to transfer a lot of private data (a room full of filefolders).
Really Awesome video! have you any ressources to increase my knowledge on mastering dynamic programming ? website, books ?
Thank you. Unfortunately, I can't recommend a specific book because I haven't read any on this topic. I have mostly learned through solving problems. Let me ask around and I'll let you know.
@@TechWithNikola Thanks for your answer
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?
Answer: because this would take the best of including this 9, or the other one, as the DP table ensures that. :)
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.
Thank you for the comment and feedback. That’s a good point. My initial version did exactly that, but then I also wanted to show full animation and I ended up not saying anything for the duration, so I sped it up.
In retrospect, I think you’re right and the approach I chose can be confusing.
You did it. Thank you. 😢
Finally yeah 😀 you’re welcome.
The python language solution was better may be reason is that I solve dsa in python but it's more simpler to understand for others as well I guess.
That’s a fair point. Thank you for the feedback. I’ll try to use more python. The only downside is that I don’t use the language on a daily basis and I may make mistakes.
6:56 why the LCS would contain 5 or 9? B could have no 9 and A could have no 5
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?
Hey, [2, 3, 4] is the longest. I made a mistake in the video (see the pinned comment that mentions mistakes)