Looking forward to the day when I post on LinkedIn about my journey to my dream company and I attach your channel as a reference for DP, Backtracking, Algos, etc
Even though NITs and prestigious state government colleges have the worst faculty. Without these teachers, I cannot imagine that I could pass the semester exams.
Preparing for upcoming google interviews. Solved an unanswered google problem from geeksforgeeks interview experience with m-colouring optimization algorithm. Had start and end time of meetings in 2 different arrays. Had to compute minimum number of rooms that are required to host all meetings. Start = [9:00,9:40,9:50,11:00,15:00,18:00] End = [9:10,12:00,11:20,11:30,19:00,20:00] So I created objects with start and end time and treated them as graph nodes. And added edges between nodes with overlapping timings. And finally solved it using m-colour optimization problem. The answer is 3. 😄
@@abdul_bari Sir, I assume that I found the right solution. But I need your advice if my approach is right. And if there is any better way of solving this problem?
00:01 Graph coloring problem requires assigning colors to vertices without adjacent vertices having the same color. 01:59 Graph coloring problem can have multiple solutions using backtracking 03:53 Graph coloring problem types and solutions 05:36 Graph coloring without adjacency conditions 08:06 Graph coloring problem has exponential time complexity 09:52 Backtracking algorithm attempts all colors for each vertex 12:02 Graph coloring problem and its applications 13:59 Graph coloring problem explained with map conversion
if you think like that then if 1-4 has boundary then tell me where is the ending boundary of 2 you won't be able to decide hence if you look carefully you will notice that 1's boundary goes up from 2 not below of 2 because below of is 2's boundary not 1's
Please stop posting comments appreciating Abdul Sir. Everyone already knows he is an excellent teacher. However, subject-related or topic-related comments would be far more helpful and actually needed.
Sir, you explained the Graph colouring problem as "the number of ways to colour a graph or given a number of colours, find if its possible to colour the graph". Then you explained about the history with Map colouring. In Map colouring problem, we need to find the minimum number of colours to colour the map with same constraints. These are related but different problems. Nevertheless, I feel that in the Graph colouring we can add a small optimisation - if the number of colours needed are more than the number of colours in a previously seen branch, then also we can stop early(bound).
Sir the last application part was really awesome and made me reason for learning Can you please add applications to all problems to solve in upcoming videos :)
Great video , I am curious not on writing an algorithm for chromatic number but to obtain the chromatic polynomial for the graph. Is there an easy relation one can uses to go from chromatic number to chromatic polynomial for a backtracking algorithm?
Great content as usual-can anyone suggest a good tutorial (novice friendly) for finding the chromatic no of a graph.Does Abdul sir have any videos on this topic in particular?
Should we use the same kind of execution technique for mColouringDecisionProblem and mColouringOptimzationProblem? (Of course, we will terminate once a solution is obtained, nut is there a better method?)
after trying red on the first vertex,do we need to try out Green and blue on the first vertex in the subsequent iterations.Or will 1st vertex always be colored with red only?
I came across this classic Graph colouring problem - uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=129 I have solved it based on the explanation given in this video. You can find my solution here - github.com/GauthamBanasandra/CompetitiveCoding/blob/master/UVa/UVa/Complete%20search/Recursive%20backtracking/Hard/Graph%20coloring/Graph%20coloring.cpp
Someone give this man a medal 🥇 . He is better than the lecturar of expensive private universities. Hats off to you legend 🔥
I like how he actually took the effort to draw the last level.
instablaster.
I was like how will I draw the level in the exam paper
@@kunalakhade5660 Indian teachers are like it should look neat no matter whether that's gonna fit in the area/page
@@kunalakhade5660 how did you draw...
Loved the last part where you told about the origin of this problem, it was something new and really helped to realize why were we doing this : )
Looking forward to the day when I post on LinkedIn about my journey to my dream company and I attach your channel as a reference for DP, Backtracking, Algos, etc
I feel like I'm giving my fees to the wrong teachers, my college should hire teachers like him instead
same here
Same same
What program are you majoring in that you're learning stuff like this? AI or something? That's great!
Just try this ruclips.net/channel/UC4CwQWuy47lTFP8-RhtF8lw?view_as=subscriber
damn true
13:09 Smoothest transition by Abdul Sir so far😅😂. Can't stop going back and checking frame by frame the way sir seems to be in the same place.
Best CS teacher ever, make every topic bite-able.
Even though NITs and prestigious state government colleges have the worst faculty.
Without these teachers, I cannot imagine that I could pass the semester exams.
brilliant storytelling of the historical case where the graph coloring can be applied!
What an excellent teacher! I feel like I am back in college! Thank you Abdul for educating us.
The way you gracefully explain the complex problem is just amazing. Thank you for all your hard work. :)
Thanks!
Your videos are a gift to the world! Thank you
Great ! You are a great Teacher. Thanks for saving my Design and analysis of Algorithm Paper.
#Respect
Which university
funny thing is my college teacher is making notes from your videos and still could not teach
Same🥲😂
Your videos have a lot of educational value, thank you so much for sharing. Currently taking Algorithm Design and Analysis
For the graph colouring problem at 14:55, should not vertex 4 connect to vertex 1? The boundaries connect
same doubt
+1
it should...just change the solution accordingly
Your an life savior of many btech students in jntu
Your videos are the best sir! Thank you for getting me through my algorithms class. Keep up the good work :)
A
Preparing for upcoming google interviews. Solved an unanswered google problem from geeksforgeeks interview experience with m-colouring optimization algorithm. Had start and end time of meetings in 2 different arrays. Had to compute minimum number of rooms that are required to host all meetings.
Start = [9:00,9:40,9:50,11:00,15:00,18:00]
End = [9:10,12:00,11:20,11:30,19:00,20:00]
So I created objects with start and end time and treated them as graph nodes. And added edges between nodes with overlapping timings. And finally solved it using m-colour optimization problem. The answer is 3. 😄
@@abdul_bari Sir, I assume that I found the right solution. But I need your advice if my approach is right. And if there is any better way of solving this problem?
@@adipratapsinghaps you can apply greedy algo for this q
the map printing example was superb professor
Very proud to say that he teaches in my college
Which college
Which college?@@Excommoner
@@MukeshchowdaryVinjamthyagaraja clg of engineering and technology
14:13 i'm convinced that ur the best teacher
It would be helpful if you provide some pseudo code with the examples and explain in terms with the code too 😁😁
PS:- your videos are really helpful
Really Helpful Sir,No one can teach like you ,Thank you sir
In the coloring of the map there must have to connect node 1 to node 4 because these two are adjacent according to this map.
Exactly!
Yes 1 and 4 have connection
best explanation of backtracking this far
ياخي اقسم بالله ودي اكتب شهادة تخرجي باسمك يا اسطورتي
trust me! I Have never watched a lecture video 1.0 X, this was Actually Interesting to watch
Superb sir....seriously the way you explain and speak is so easy and understandable to any one.....
Best teacher I've seen my teacher is not even close to him!!
wow, that explanation was perfect
itna zyada student seen kr rha ....bhut accha sir,thanku so much sir for ur help
00:01 Graph coloring problem requires assigning colors to vertices without adjacent vertices having the same color.
01:59 Graph coloring problem can have multiple solutions using backtracking
03:53 Graph coloring problem types and solutions
05:36 Graph coloring without adjacency conditions
08:06 Graph coloring problem has exponential time complexity
09:52 Backtracking algorithm attempts all colors for each vertex
12:02 Graph coloring problem and its applications
13:59 Graph coloring problem explained with map conversion
Tommorrow is my exam and i done prepration by your video 🍀🍀
cam share your exam paper
15:25
Since 4 is neighbour to 1 between 2 and 5,there should be an edge from 4 to 1 or 1 to 4 at 15:25, right?
Yes,but assume that 2nd vertex is completely in between 1 and 4 i.e the small uncovered region is to be covered
if you think like that then if 1-4 has boundary then tell me where is the ending boundary of 2 you won't be able to decide
hence if you look carefully you will notice that 1's boundary goes up from 2 not below of 2 because below of is 2's boundary not 1's
even after 100 years , this man will be remembered
Sir is, Aamir Khan of Algorithms
thugs of hindustan flops
Bavalpreet Singh lmao 😂
He is Lee CHong Wei of Algorithms
wanted to like this comment but it is on 69 so not doingXD
14:37 there's a common boundary between 1 & 4 also.
Thank You So Much Abdul Sir..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻 as usual super dooper explanation
sir ,your teaching style is awesome .Really, love your videos
Please stop posting comments appreciating Abdul Sir. Everyone already knows he is an excellent teacher. However, subject-related or topic-related comments would be far more helpful and actually needed.
I am a big fan of you, now following everything about algorithms and maths.
15:25 there must be an edge between 1 and 4
But they're not neighboring?
At 14:50, isn't region(1) neighbour to region(4)?
Thank you sir. 🙂
Your videos are very helpful for papers .
Thank you for your great effort and helping students around the world.
voice is so good to understand and skip written part by himself which is not imp thats so better
What an explanation sir,,👏👏👏
Thank you sir for these types of videos it's really very helpful for us ❤️❤️
Actual solution starts at 8:33
Thanks for the time stamp mate. You've just saved my time 😊
how many of you are watchin 1.5x or 2x hit like here
kabi kabhi nhi hamesha lagta hai ki sir ich bhagwan hai.... akash gaytunde
i'm at 1.75x lol xd
thanks, wrote the code directly, didn't even need to take any reference or watch it again
can anyone help me to understand 7:53 math sum proplem how to drive it pls...
Sir, you explained the Graph colouring problem as "the number of ways to colour a graph or given a number of colours, find if its possible to colour the graph". Then you explained about the history with Map colouring. In Map colouring problem, we need to find the minimum number of colours to colour the map with same constraints. These are related but different problems. Nevertheless, I feel that in the Graph colouring we can add a small optimisation - if the number of colours needed are more than the number of colours in a previously seen branch, then also we can stop early(bound).
Sir the last application part was really awesome and made me reason for learning
Can you please add applications to all problems to solve in upcoming videos :)
what a brilliant explanation ❤
15:00 isnt 1 and 4 are neighbor?
I appreciate your immediate response.
I enjoyed your video. Unfortunately at 15:08 you missed an edge, 1-4, in your final diagram.
Nevermind, I see your note in the description :)
Thank you algo king Abdul 🙏
Please include algorithm sir
Thankyou abdul! great bideo!
He is born as tutor
good Teacher.Learnt many things.so simple in understanding.
Sir it would be much better if you provide algorithms as well because in exams they ask algorithms too.
Yes please Sir
he doesnt know them
@@TusharYadav-es1bq writing the algorithm is trivial if you understand the algorithm well. Understanding algorithm is more difficult
@@TusharYadav-es1bq kiddo
@Abdul Bari
In university exam,
is required to find all possibility of graph coloring ?
Great video , I am curious not on writing an algorithm for chromatic number but to obtain the chromatic polynomial for the graph. Is there an easy relation one can uses to go from chromatic number to chromatic polynomial for a backtracking algorithm?
i cant really find any easy to write algoritms. i know hes a great teacher but he aint explining any algoritms
@@bavidlynx3409 hey, so from where did you do the algo explanation part
Can you provide lisp programming for the same problem using any search method
how about the point that dont connect to any other point? what should i color it? a different color that no point got it? or same as any point color?
Sir for Network flow and matching lecture video is available or not?
Very simple and straightforward explanation. I understand backtracking
well explained, good camera, thanks
15:5 also a 1- 4 is present
looks little bit like gujarat map, btw nice video appreciate the effort.
at 7:47, how it is (3^(4+1))/3-1
sum of GP
Great content as usual-can anyone suggest a good tutorial (novice friendly) for finding the chromatic no of a graph.Does Abdul sir have any videos on this topic in particular?
nice video sir
Your channel is very helpful
Μεγάλος μάστορας αυτός παιδιά.
Thank you , I appreciate your help so much
is there any rule to start colouring from specific vertex? or we can start colouring from any vertex?? please reply @Abdul Bari
Should we use the same kind of execution technique for mColouringDecisionProblem and mColouringOptimzationProblem? (Of course, we will terminate once a solution is obtained, nut is there a better method?)
Sir.. actually how many solutions can obtain at end of the video is 18 or more that?
sir if we are having only 3 nodes and 3 colors how could we do the problem ??
after trying red on the first vertex,do we need to try out Green and blue on the first vertex in the subsequent iterations.Or will 1st vertex always be colored with red only?
have to put other colours there too as they are possible solutions
Brilliant Teacher.
Thank you so much sir, respect and love from Bangladesh ❤️🇧🇩
Isn't M - coloring optimization problem solved via dynamic programming since it's an optimization problem?
Sir, this solution won't work for K4(complete graph with 4 vertices) graph
Cant we just Greedily color the graph? Why do we have to go for BackTracking?
At 12:50 RBRB can't be the solution.
Why though? It is a valid solution. Check it out yourself.
Thank you for your great effort
Way better than Boring and upto some extent useless Ravula Lectures.
From 8:44
bài giảng hay lắm ạ, mỗi tội cháu ko nghe thấy gì, may mà có phụ đề tiếng anh.
Can you explain how GCP can be used in College/exam
Timetabling
beautifully explained but it could have been better if it would have explained through code as well
I came across this classic Graph colouring problem - uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=129
I have solved it based on the explanation given in this video. You can find my solution here - github.com/GauthamBanasandra/CompetitiveCoding/blob/master/UVa/UVa/Complete%20search/Recursive%20backtracking/Hard/Graph%20coloring/Graph%20coloring.cpp
awesome example on application✌
Great explanation ❤️