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

ความคิดเห็น • 181

  • @tushaar39
    @tushaar39 6 ปีที่แล้ว +112

    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.

  • @adityanaidu9388
    @adityanaidu9388 6 ปีที่แล้ว +112

    Sir,
    Seriously saying u made algorithm studying soo simple..Thankyou Soomuch

  • @abaf5719
    @abaf5719 4 ปีที่แล้ว +14

    Now I am regrettting why I don’t watch your lectures right from the starting. you made the concepts very simple to understand

  • @gourav1163
    @gourav1163 3 ปีที่แล้ว +11

    I like the way you explain things again as when required

  • @thrilleracaste400
    @thrilleracaste400 2 ปีที่แล้ว +6

    This is one of the best playlist for algorithms. Thank you sir!!

  • @nothingbutlove5421
    @nothingbutlove5421 4 ปีที่แล้ว +1

    algorithms are enlightening and your teaching is God sent

  • @aishu6653
    @aishu6653 ปีที่แล้ว +2

    Sir We have no words to expain how we are feeling after understanding perfect concept .THANKYOU SO MUCH SIR .

  • @trade_head
    @trade_head หลายเดือนก่อน +1

    6 years old content still passed the exams thankyou sir 😊

  • @APpedia
    @APpedia 6 ปีที่แล้ว +24

    nice explanation sir.

  • @anssgul8208
    @anssgul8208 3 ปีที่แล้ว +1

    You are a among the top teachers in the world...

  • @roushangiri4722
    @roushangiri4722 4 ปีที่แล้ว +7

    Never knew algorithm can be so fun to learn!

  • @tanmaykapil5362
    @tanmaykapil5362 5 ปีที่แล้ว +6

    just amazing sir,
    waiting for the java course on udemy.

  • @eva42sh
    @eva42sh 2 ปีที่แล้ว +1

    thank you Mr Abdul for allocating your time for making these awesome educational videos

  • @abhishekkamble3975
    @abhishekkamble3975 ปีที่แล้ว +1

    This man build the future of engineers....💯

  • @subramaniyanvg6367
    @subramaniyanvg6367 ปีที่แล้ว +1

    The real guru for data structures

  • @rajalakshmigiri6615
    @rajalakshmigiri6615 3 ปีที่แล้ว +3

    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

  • @sheetalsharma7587
    @sheetalsharma7587 ปีที่แล้ว +1

    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

  • @adwaithms6202
    @adwaithms6202 ปีที่แล้ว

    5 years later......... Awesome❤️

  • @ruturajjadhav963
    @ruturajjadhav963 5 หลายเดือนก่อน

    You teach better than my Professor......!

  • @harshuke
    @harshuke ปีที่แล้ว

    No words to say How good teacher you are

  • @rishabgupta3419
    @rishabgupta3419 5 ปีที่แล้ว +3

    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.

  • @akmalziyad3052
    @akmalziyad3052 6 ปีที่แล้ว +5

    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

    • @priyakk6504
      @priyakk6504 6 ปีที่แล้ว

      Superb Vids thanks sir

  • @harshgohel9626
    @harshgohel9626 4 ปีที่แล้ว +1

    Really great algorithm series ever, I request you to make course on java if possible.

    • @gourav1163
      @gourav1163 3 ปีที่แล้ว +2

      Already On Udemy bRo

  • @indra16
    @indra16 4 ปีที่แล้ว

    no one is better then you sir on YT

  • @mgnfy-view
    @mgnfy-view 10 หลายเดือนก่อน +26

    Pro tip: Watch the video at 1.25x playback speed! ⏩

    • @musicmysoul6060
      @musicmysoul6060 5 หลายเดือนก่อน

      1.95 is better

    • @Jerryt.c
      @Jerryt.c 4 หลายเดือนก่อน +6

      2X is preferred 😂

    • @numanali8545
      @numanali8545 4 หลายเดือนก่อน +2

      No.... watch at normal speed to fully grasp if it's ur first time...for revision u can speed up

    • @Gekroherika
      @Gekroherika หลายเดือนก่อน

      3X is fine

    • @GSEDITZAMV
      @GSEDITZAMV 22 ชั่วโมงที่ผ่านมา +1

      ​@@Jerryt.curgency 😂

  • @harshavardhan3527
    @harshavardhan3527 5 ปีที่แล้ว +3

    thanks a lot sir ! my results are out and i made it

  • @Jerryt.c
    @Jerryt.c 4 หลายเดือนก่อน +6

    No need to read comments, focus on video 💀

  • @Han-ve8uh
    @Han-ve8uh 4 ปีที่แล้ว +6

    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.

    • @liveshkumar7322
      @liveshkumar7322 3 ปีที่แล้ว

      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.

    • @theunusual4566
      @theunusual4566 7 หลายเดือนก่อน

      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.

    • @Han-ve8uh
      @Han-ve8uh 7 หลายเดือนก่อน +1

      @@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)

    • @theunusual4566
      @theunusual4566 7 หลายเดือนก่อน

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

    • @Han-ve8uh
      @Han-ve8uh 7 หลายเดือนก่อน +1

      ​@@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

  • @ranisaritharmca7771
    @ranisaritharmca7771 3 ปีที่แล้ว +1

    Great work. Simple and nice explanation sir. Thank u very much sir.

  • @GavinLon
    @GavinLon 5 ปีที่แล้ว +1

    Another great tutorial.Just given you another thumbs up!

  • @NiveditJainBCSE
    @NiveditJainBCSE 5 ปีที่แล้ว

    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.

  • @jayeshkulkarni7768
    @jayeshkulkarni7768 2 ปีที่แล้ว

    abdul bari sir always to save me!! 😄😃 thank you sir!!

  • @ramjitiwari8910
    @ramjitiwari8910 4 ปีที่แล้ว +1

    Best teacher 😃

  • @Rahulkumar-ss3ik
    @Rahulkumar-ss3ik 4 ปีที่แล้ว

    Abdul Bhai aap vhut aacha Kam KR raha hai

  • @tobecontinued745
    @tobecontinued745 6 ปีที่แล้ว

    sprrbbb explanation.. and hatsoff to ur way of teaching..

  • @yardfonirmal9610
    @yardfonirmal9610 4 ปีที่แล้ว +19

    Could you please provide Algorithm in the form of pseudo-code.
    That would be helpful

    • @karanveersingh5535
      @karanveersingh5535 3 ปีที่แล้ว

      Exactly

    • @ok_7566
      @ok_7566 3 ปีที่แล้ว +1

      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!

  • @khalidsaifullah7690
    @khalidsaifullah7690 2 ปีที่แล้ว

    কাকা আপনি সেরা ❣️

  • @SaumyaSharma007
    @SaumyaSharma007 3 ปีที่แล้ว +2

    Thank you very much Sir 👍👌🔥.
    Long live Sir 🌟🙏

  • @love_in_nature8616
    @love_in_nature8616 2 ปีที่แล้ว +1

    Happy teachers day sir..!

    • @abdul_bari
      @abdul_bari  2 ปีที่แล้ว

      Thanks Dear,
      God Bless You.

  • @KANKSHMusic
    @KANKSHMusic ปีที่แล้ว +2

    You're great sir

  • @rizaabriol7122
    @rizaabriol7122 2 ปีที่แล้ว

    Thank you😊 I learned a lot. Now I can answer my assessment.

  • @kashinathmagadum8336
    @kashinathmagadum8336 6 ปีที่แล้ว +2

    Tqqqqq tqq soo much sirrr
    This same qun appear in previous qun paper tqqqq sir

  • @pawanchouhan3239
    @pawanchouhan3239 ปีที่แล้ว

    verry good sir u made thiss very easyy

  • @sonalghotane5492
    @sonalghotane5492 5 ปีที่แล้ว +2

    Thank you sir!!
    I understood everything wat u thought🌸

  • @ahmedelrawy6385
    @ahmedelrawy6385 ปีที่แล้ว +1

    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

  • @Satvikshukla0007
    @Satvikshukla0007 4 ปีที่แล้ว

    Very nice explanation sir

  • @snehakathare572
    @snehakathare572 6 ปีที่แล้ว +1

    Excellent .....! explanation .
    Thank u so much sir

  • @yashgangrade5460
    @yashgangrade5460 6 ปีที่แล้ว

    nice explanation sir you have solved all my doubts

  • @stutisflairs9622
    @stutisflairs9622 2 ปีที่แล้ว +1

    Sir you can first merge B and C and then A and D

  • @padaladileep5906
    @padaladileep5906 4 ปีที่แล้ว

    Please make some videos on design patterns too..

  • @preritpradeep
    @preritpradeep 4 ปีที่แล้ว

    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?

    • @abhinashjena216
      @abhinashjena216 ปีที่แล้ว

      How does your time complexity become 95 in 5-way merging for this problem!

  • @mohammedadel8948
    @mohammedadel8948 2 ปีที่แล้ว

    Thank you for your efforts

  • @mahendrasahu7493
    @mahendrasahu7493 6 ปีที่แล้ว +1

    great explanation sir.

  • @GopikaAddala
    @GopikaAddala 5 หลายเดือนก่อน

    Sir can we use the ascending order of elements

  • @rohiniswathi4360
    @rohiniswathi4360 หลายเดือนก่อน

    sir, can we merge [5,2] and then [6,3] and the total time is 16 which is less than 31

  • @USER-SANATANI952
    @USER-SANATANI952 5 ปีที่แล้ว +1

    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

  • @sovereignstandards
    @sovereignstandards 2 ปีที่แล้ว +1

    Thank you Sir

  • @utkarshchandra9787
    @utkarshchandra9787 3 ปีที่แล้ว

    great explanation

  • @pradipmohalkad1108
    @pradipmohalkad1108 4 ปีที่แล้ว

    Very nice explain sir

  • @sratnamanjari244
    @sratnamanjari244 5 ปีที่แล้ว

    Sir 🙏....explanation superb👌

  • @harigovind11
    @harigovind11 5 ปีที่แล้ว

    Sir isn't using min heap implementation better to merge n sorted lists ?

  • @nishant5249
    @nishant5249 4 ปีที่แล้ว

    thanks a lot sir for such a good explanation .

  • @rutuja7293
    @rutuja7293 5 ปีที่แล้ว

    Excellent explanation 👌👌

  • @huchchayyamkelur6842
    @huchchayyamkelur6842 2 ปีที่แล้ว

    Sir for some string we don't get reduced number of bits why?

  • @agnishbrahma4858
    @agnishbrahma4858 7 หลายเดือนก่อน

    Uncle! What is the Time Complexity?

  • @dishamodi2509
    @dishamodi2509 2 ปีที่แล้ว

    Can't we merge as A and C first ...then B and D and then combine this both the combinations?

  • @harshith_takkala
    @harshith_takkala 3 ปีที่แล้ว +1

    thankyou sir !

  • @amankumarkashyap400
    @amankumarkashyap400 5 ปีที่แล้ว +1

    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.

    • @sadhlife
      @sadhlife 4 ปีที่แล้ว

      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

  • @gunjanshinde396
    @gunjanshinde396 2 ปีที่แล้ว

    Is code of this all (Greedy) algorithm are required for College examination ???

  • @kiranshinde03
    @kiranshinde03 2 ปีที่แล้ว

    Very nice sir ji ❤️😊

  • @sheelstera
    @sheelstera 5 ปีที่แล้ว +1

    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

    • @sheelstera
      @sheelstera 5 ปีที่แล้ว +1

      @@abdul_bari Alright thank you so much

  • @dhruvanshrautela7507
    @dhruvanshrautela7507 3 ปีที่แล้ว

    is it the same as Optimal Reliability Allocation, I wanted to study about it.

  • @EngineerBolte
    @EngineerBolte 5 หลายเดือนก่อน +1

    Watch at 1.75x

  • @rachanamunot483
    @rachanamunot483 5 ปีที่แล้ว

    Sir,the sum you have calculated, is it same as M.R.T (Mean Retrieval Time) ?

  • @revanthreddy8970
    @revanthreddy8970 5 ปีที่แล้ว

    Very gud explanation sir
    Thank u so much sir

  • @manishayadav1136
    @manishayadav1136 5 ปีที่แล้ว

    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

  • @rishikabhati4383
    @rishikabhati4383 2 ปีที่แล้ว

    Thank You So Much Sir :)

  • @blacklotus5953
    @blacklotus5953 6 ปีที่แล้ว

    youve helped me so much thank you sir

  • @tahatemuri8170
    @tahatemuri8170 4 ปีที่แล้ว +1

    With respectfully what is the real world scenario for this? It seems to be a piece of cake just 1+1=2...

  • @jackmiller2518
    @jackmiller2518 2 ปีที่แล้ว

    thank you so much sir

  • @vishalrana4526
    @vishalrana4526 5 ปีที่แล้ว

    Sir, What is ordering paradigm?

  • @kushwanthkapa2041
    @kushwanthkapa2041 2 ปีที่แล้ว

    what is time complexity of m way merge sort?

  • @rachanamunot483
    @rachanamunot483 5 ปีที่แล้ว

    Is it same as Optimal storage on tapes method?

  • @satyanarayanmohanty3415
    @satyanarayanmohanty3415 4 ปีที่แล้ว

    Simply awesome.

  • @chaitanyatupsamudre6059
    @chaitanyatupsamudre6059 4 ปีที่แล้ว

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

    • @abhishekbanerjee6140
      @abhishekbanerjee6140 4 ปีที่แล้ว

      I also have the same doubt. Do you know the answer now?

    • @nirmalaryal6446
      @nirmalaryal6446 3 ปีที่แล้ว +1

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

    • @abhishekbanerjee6140
      @abhishekbanerjee6140 3 ปีที่แล้ว

      @@nirmalaryal6446 Aaah okayy. Makes sense man. Thanks!

  • @bhaskargg6018
    @bhaskargg6018 4 ปีที่แล้ว

    Thanks a lot Sir

  • @hhh48222
    @hhh48222 3 ปีที่แล้ว +1

    Awesome 🔥❤️

  • @shahzadikhan8356
    @shahzadikhan8356 4 ปีที่แล้ว

    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.

    • @abhishekbanerjee6140
      @abhishekbanerjee6140 4 ปีที่แล้ว

      Can you explain why we have to add 9 and 7 to 16? I cant understand

  • @deepakakela6189
    @deepakakela6189 6 ปีที่แล้ว

    impressive sir!!!!!!!!

  • @29_rahulv6
    @29_rahulv6 2 ปีที่แล้ว

    super keep going🔥🔥🔥

  • @dineshhannurkar
    @dineshhannurkar 6 ปีที่แล้ว

    Hello Sir,
    can u make a video on optimal storage on tapes and single source shortest paths

    • @dineshhannurkar
      @dineshhannurkar 6 ปีที่แล้ว

      Ok, thanku sir I will try to understand..

  • @sumeet602
    @sumeet602 6 ปีที่แล้ว +1

    I wish you were my college professor.

  • @saurabhgupta1595
    @saurabhgupta1595 3 ปีที่แล้ว

    Thanks

  • @sheerinafzal7291
    @sheerinafzal7291 5 ปีที่แล้ว

    How can we do this for ternary tree??

  • @rajdeepkarmakar9713
    @rajdeepkarmakar9713 2 ปีที่แล้ว

    minheap priority queue
    se bhi ho sakta

  • @akhil1845
    @akhil1845 6 ปีที่แล้ว

    sir is optimal storage on tapes and optimal merge pattern are same?

  • @AbdulRaheem-rt4pp
    @AbdulRaheem-rt4pp 5 หลายเดือนก่อน

    1.5 is preferred

  • @AnitShrestha
    @AnitShrestha 5 ปีที่แล้ว

    Thank you.

  • @kasyapdharanikota8570
    @kasyapdharanikota8570 3 ปีที่แล้ว

    sir can you please also provide the pseudocode for these algorithms?

    • @Ron-yt2sp
      @Ron-yt2sp 3 ปีที่แล้ว

      u will find it in geeksforgeeks

  • @ashwinverma2030
    @ashwinverma2030 2 หลายเดือนก่อน

    2x is preferred.