3.3 Optimal Merge Pattern - Greedy Method
ฝัง
- เผยแพร่เมื่อ 29 ต.ค. 2024
- What is Merging?
What is Optimal Merge Pattern Problem ?
It useful for Huffman Coding
PATREON : www.patreon.co...
Courses on Udemy
================
Java Programming
www.udemy.com/...
Data Structures using C and C++
www.udemy.com/...
C++ Programming
www.udemy.com/...
Sir, I must say. You are a very good teacher. You really have got that teacher spirit. With the help of your lectures on algorithms, I was able to study for my exams and my exam went really good today. Thank You sir for your determined efforts. If you could make lectures on other subjects like DBMS and OS, that would be very helpful, as they are imp subjects for CSE people. Nevertheless, Thanks Again. Keep teaching in excellency.
Sir,
Seriously saying u made algorithm studying soo simple..Thankyou Soomuch
Now I am regrettting why I don’t watch your lectures right from the starting. you made the concepts very simple to understand
I like the way you explain things again as when required
This is one of the best playlist for algorithms. Thank you sir!!
algorithms are enlightening and your teaching is God sent
Sir We have no words to expain how we are feeling after understanding perfect concept .THANKYOU SO MUCH SIR .
😂
6 years old content still passed the exams thankyou sir 😊
nice explanation sir.
You are a among the top teachers in the world...
Never knew algorithm can be so fun to learn!
just amazing sir,
waiting for the java course on udemy.
thank you Mr Abdul for allocating your time for making these awesome educational videos
This man build the future of engineers....💯
The real guru for data structures
Why always my professor's example and urs are same one🤔🤔..Is she watched ur video and took cls for us....Good explanation sir....Hope I'll score more in DSA
Thank you sir aaj mera university ka paper tha aur yhi same question aaya tha value tak same thi 😊 205 ans muje yaad tha 10 marks pkee shukria
5 years later......... Awesome❤️
You teach better than my Professor......!
No words to say How good teacher you are
hello sir...just wanna thanks,really your videos are amazing.....sir please uplaod a course on python...with your teaching methodologies it would be fun to learn python.
Bahot badhiya kar rahe ho aap
Thank you
Keep it up jaldi revenue dikhna start nahi hoga bas aap videos banate rahiye better aur better.
You will get benefits inshallah
Superb Vids thanks sir
Really great algorithm series ever, I request you to make course on java if possible.
Already On Udemy bRo
no one is better then you sir on YT
Pro tip: Watch the video at 1.25x playback speed! ⏩
1.95 is better
2X is preferred 😂
No.... watch at normal speed to fully grasp if it's ur first time...for revision u can speed up
3X is fine
@@Jerryt.curgency 😂
thanks a lot sir ! my results are out and i made it
No need to read comments, focus on video 💀
Rather than just accepting an algorithm as it is (in this eg, it's always merge 2 smallest groups), how do we prove that this merge pattern is indeed optimal? I think the hardest thing given a new problem is not being sure if a greedy approach indeed solves the problem, and if decided to solve using greedy approach, how to know what the best strategy is, and whether doing local best every step really leads to global best.
the only way is to try this approach on some sample problems and check your answer manually. Otherwise if you can you can also try to prove it using mathematical induction.
Consider files with the following number of records: 2, 3, 5, and 10. Optimal way to merge them would be to merge the files with 2 and 3 records first (cost = 5), then merge this with the file with 5 records (cost = 10), and finally merge this with the file with 10 records (cost = 20). The total merging cost is 5 + 10 + 20 = 35.
A non-optimal way of merging could be: First merge files of size 5 and 10 (merging cost = 15), then merge this with the file of size 3 (new merging cost = 15 + 18 = 33), then merge the result with the file of size 2 (total merging cost = 33 + 20 = 53)s
But the Optimal Merge Pattern strategy will follow a different route:
First, merge files of size 2 and 3 (merging cost = 5) -> 2+3
Then, merge this with the file of size 5 (new merging cost = 5 + 10 (2+3+5) = 15)
Finally, merge this with the file of size 10 (total merging cost = 15 + 20 (2+3+5+10) = 35)
With this strategy, we've reduced the total merging cost from 53 to 35 and hence, the optimal merge pattern is more efficient. The concept here is to always pick the smallest sizes to merge first, which reduces the cumulative cost.
@@theunusual4566 Could you explain why cumulation?
You provided 3 calculation examples, the 1st one had no cumulation, the 2nd and 3rd have. That inconsistency is confusing.
In the last example, i also see 2 inconsistencies.
The pattern you seem to do is pick 1 of the 2 input file sizes (which one?), then add it to the output merged size to get merging cost.
So 1st inconsistency is i expected your first step to be 2+ (2+3) OR 3 + (2+3).
I also expected your last step to be 15+ (10+15)
@@Han-ve8uh 1st do not have, Coz that's the first step .
2nd and 3rd Has Coz, some steps or some work was done prior to 2 {STEP 1} and 3 {STEP 2, 3}
For ex, Consider files with different number of Lines in it, any think how would those be merged, You would get idea.
@@theunusual4566
Thanks i fully understand now. Part of confusion could be because i read your reply in the narrow notification window instead of from the full screen below the video, so it messed up the formatting which is very important.
I got confused because I did not realize which sums are adding across steps (that's where cumulation comes from), and which sums are adding across 2 files within a step.
A single phrase to summarize this whole thing is Shortest Job Next in queueing theory (en.wikipedia.org/wiki/Shortest_job_next).
Analogy is when we treat the total merge cost as the total waiting time for all jobs to complete, and size of each item to merge, as the waiting time of the job
Great work. Simple and nice explanation sir. Thank u very much sir.
Another great tutorial.Just given you another thumbs up!
The last part where multiplication is show serves as a good proof that why we are taking a minimum number first. I say represent it as a mathematical function and take partial derivates.
abdul bari sir always to save me!! 😄😃 thank you sir!!
Best teacher 😃
Abdul Bhai aap vhut aacha Kam KR raha hai
sprrbbb explanation.. and hatsoff to ur way of teaching..
Could you please provide Algorithm in the form of pseudo-code.
That would be helpful
Exactly
You need a min heap and a structure designed with freq, left child right child and also char as one field it is quit ecomplex tbh once someone shows you can do it but very difficult to come up without any pre exposure!! at least to me it was!
কাকা আপনি সেরা ❣️
Thank you very much Sir 👍👌🔥.
Long live Sir 🌟🙏
Happy teachers day sir..!
Thanks Dear,
God Bless You.
You're great sir
Thank you😊 I learned a lot. Now I can answer my assessment.
Tqqqqq tqq soo much sirrr
This same qun appear in previous qun paper tqqqq sir
verry good sir u made thiss very easyy
Thank you sir!!
I understood everything wat u thought🌸
Hello professor the last merge example isn't the optimal merge pattern in it there is another one which results in 190 total not 210
And also in Huffman code you didn't use the same merge pattern of optimal merge thanks very much I just want to understand
Very nice explanation sir
Excellent .....! explanation .
Thank u so much sir
nice explanation sir you have solved all my doubts
Sir you can first merge B and C and then A and D
Please make some videos on design patterns too..
The time complexity for m-way merging is O(m+n+p+q+... size of all lists).. In the last example, 5-way merging would have given a time complexity of 95, whereas 2-way gave a complexity of 205. So why do we prefer 2-way merging over m-way?
How does your time complexity become 95 in 5-way merging for this problem!
Thank you for your efforts
great explanation sir.
Sir can we use the ascending order of elements
sir, can we merge [5,2] and then [6,3] and the total time is 16 which is less than 31
sir, if size of two lists are same then can we add them one by one with previous terms. if this done thenrequired time will be 210
Thank you Sir
great explanation
Very nice explain sir
Sir 🙏....explanation superb👌
Sir isn't using min heap implementation better to merge n sorted lists ?
thanks a lot sir for such a good explanation .
Excellent explanation 👌👌
Sir for some string we don't get reduced number of bits why?
Uncle! What is the Time Complexity?
Can't we merge as A and C first ...then B and D and then combine this both the combinations?
thankyou sir !
But if we go for n-way merging than we can have O(n1 + n2 + n3 ....... + np) which will be better than this two at a time merging.
the comparison function for merging might not be O(1) then, so that'll be multiplied in the overall time complexity as well. it depends on the scenario
Is code of this all (Greedy) algorithm are required for College examination ???
Very nice sir ji ❤️😊
Hello @Abdul Bari,
Thank you so much for this.
Your explanation on the topic was so smooth that I chose to remember it like a television story and just forgot about the constraints in the optimal merge problem. In previous greedy problems (Knapsack and job sequencing), there were constraints and a target; here the target is minimal merge time; but what is the constraint here? Can I say that "the 2 way merge" (i.e. cannot take more than 2 lists at a time) is the constraint? Request your thoughts on this.
Regards
Sheel
@@abdul_bari Alright thank you so much
is it the same as Optimal Reliability Allocation, I wanted to study about it.
Watch at 1.75x
Sir,the sum you have calculated, is it same as M.R.T (Mean Retrieval Time) ?
Ok👍
Very gud explanation sir
Thank u so much sir
in first example when we take (B)5 and (C)2 which is 7 and then 7 with (D)3 which is 10 then 10 and (A)6 that is 16 which is minimum cost.........31 minimum cost is wrong ans
Thank You So Much Sir :)
youve helped me so much thank you sir
With respectfully what is the real world scenario for this? It seems to be a piece of cake just 1+1=2...
thank you so much sir
Sir, What is ordering paradigm?
what is time complexity of m way merge sort?
Is it same as Optimal storage on tapes method?
Simply awesome.
In optimal merge pattern,
6,5,2,3 we can select (6+2) and (5+3) it will give 8+8 = 16 more optimal , is this correct ??
I also have the same doubt. Do you know the answer now?
@@abhishekbanerjee6140 In above example accoring to your solution first (6+2) give 8 and (5+3) give 8 and now to merge both we get (8+8) =16 but in Total it will be 8+8+16=32 and by doing with optimal merge pattern it will be 31.
@@nirmalaryal6446 Aaah okayy. Makes sense man. Thanks!
Thanks a lot Sir
Awesome 🔥❤️
Can't it be like 5+2=7
Then 6+3=9,
7+9=16
Lastly, 16+9+7=32?
That's greater than 31 but I'm asking this because you said there isn't any other way. Hope to get a reply sir.
Can you explain why we have to add 9 and 7 to 16? I cant understand
impressive sir!!!!!!!!
super keep going🔥🔥🔥
Hello Sir,
can u make a video on optimal storage on tapes and single source shortest paths
Ok, thanku sir I will try to understand..
I wish you were my college professor.
Thanks
How can we do this for ternary tree??
minheap priority queue
se bhi ho sakta
sir is optimal storage on tapes and optimal merge pattern are same?
ohh ok SIR
thank u sir
@@abdul_bari Okay Thank you sir for free knowledge.
1.5 is preferred
Thank you.
sir can you please also provide the pseudocode for these algorithms?
u will find it in geeksforgeeks
2x is preferred.