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
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 though NITs and prestigious state government colleges have the worst faculty. Without these teachers, I cannot imagine that I could pass the semester exams.
I'm sorry Sir, but printing press example is not suitable for the solved example. You demonstrated how to manually and iteratively (without using simple maths such as combination formulae) look for number of ways to colour the graph with given set of colors. As per your own declaration , it falls in type 1 problem but a printing press only needs to know whether or not they can colour the graph with given set of finite N number of colors (if mixing is not allowed). That is clearly your Type 2 N-colouring decision problem! If mixing is allowed, then they don't even need to know anything. Press created the map so they know already how many bisections they made of the graph which will be the number of times they will have to sequentially print each colour one after another. And also since they can mix the colors to make infinite shades of colors, they don't need to find out how many ways to fill colors in these bisections. They will start with 1 colour and then keep filling another shade after another shade till it is completely filled. They would already know how many fills they need to do, as again they know already the number of vertices/bisections in the map.
Also I would appreciate if you could add a section in the end or a small link to the mathematical solution to the problem, where instead of manual selection (which you termed backtracking) a proper combination formula is used to explain. We just need to subtract adjacency condition from all possible solutions. All possible solution is [nCr x (n-r)ˆr ] Now need to subtract adjacency combinations from it.
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?
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
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 :)
Bari sir visited our college im really gratefull for that, but unfortunately the students were not cooperating with him, so he eventually left the class
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).
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?
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?
Obviously we can count the distinct minimal coloring's and we know the chromatic polynomial value for that and the fact it is zero for smaller colors. But is that enough information to generate the chromatic polynomial. I can do it out mathematically but now i am looking for a algorithm i can program. I have a backtracking algorithm similar to what your doing in this video. But i not so sure the most efficient and best way to go about obtaining the chromatic polynomial from all this information i can obtain. (in the optimal currently known algorithms !)
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?
![[UA] NAVI проти G2 Esports | Blast Premier Fall Final](http://i.ytimg.com/vi/QWlIm4FGESQ/mqdefault.jpg)
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 ua-cam.com/channels/4CwQWuy47lTFP8-RhtF8lw.html?view_as=subscriber
damn true
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...
funny thing is my college teacher is making notes from your videos and still could not teach
Same🥲😂
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
Someone give this man a medal 🥇 . He is better than the lecturar of expensive private universities. Hats off to you legend 🔥
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
Thanks!
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
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
Great ! You are a great Teacher. Thanks for saving my Design and analysis of Algorithm Paper.
#Respect
Which university
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.
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
Your videos are a gift to the world! Thank you
brilliant storytelling of the historical case where the graph coloring can be applied!
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
Please include algorithm sir
Your videos have a lot of educational value, thank you so much for sharing. Currently taking Algorithm Design and Analysis
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
Abdul bari :- Zindaabad
Engneering colleges:- Murdabad (The end)
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.
Best CS teacher ever, make every topic bite-able.
I'm sorry Sir, but printing press example is not suitable for the solved example. You demonstrated how to manually and iteratively (without using simple maths such as combination formulae) look for number of ways to colour the graph with given set of colors. As per your own declaration , it falls in type 1 problem but a printing press only needs to know whether or not they can colour the graph with given set of finite N number of colors (if mixing is not allowed). That is clearly your Type 2 N-colouring decision problem!
If mixing is allowed, then they don't even need to know anything. Press created the map so they know already how many bisections they made of the graph which will be the number of times they will have to sequentially print each colour one after another. And also since they can mix the colors to make infinite shades of colors, they don't need to find out how many ways to fill colors in these bisections. They will start with 1 colour and then keep filling another shade after another shade till it is completely filled. They would already know how many fills they need to do, as again they know already the number of vertices/bisections in the map.
Also I would appreciate if you could add a section in the end or a small link to the mathematical solution to the problem, where instead of manual selection (which you termed backtracking) a proper combination formula is used to explain. We just need to subtract adjacency condition from all possible solutions.
All possible solution is [nCr x (n-r)ˆr ]
Now need to subtract adjacency combinations from it.
can anyone help me to understand 7:53 math sum proplem how to drive it pls...
@abdul Bari : can u Plz start including code snippet also in Ur videos? Everytime I need to follow other sites for code.
Your videos are the best sir! Thank you for getting me through my algorithms class. Keep up the good work :)
A
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
baari kon jaat ?
@Abdul Bari
In university exam,
is required to find all possibility of graph coloring ?
algo's link : ua-cam.com/video/3DcG72v2_n0/v-deo.html
He is born as tutor
Can you provide lisp programming for the same problem using any search method
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?
Thank You So Much Abdul Sir..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻 as usual super dooper explanation
Thank you sir. 🙂
Your videos are very helpful for papers .
the map printing example was superb professor
Cant we just Greedily color the graph? Why do we have to go for BackTracking?
The way you gracefully explain the complex problem is just amazing. Thank you for all your hard work. :)
best explanation of backtracking this far
voice is so good to understand and skip written part by himself which is not imp thats so better
Very proud to say that he teaches in my college
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
What an excellent teacher! I feel like I am back in college! Thank you Abdul for educating us.
Thank you , I appreciate your help so much
Your an life savior of many btech students in jntu
14:37 there's a common boundary between 1 & 4 also.
Can you also do the machine learning algorithm too, and thank you for helping understanding these concept :)
Can you explain how GCP can be used in College/exam
Timetabling
Sir can you add application to all problems in upcomming videos please
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 :)
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 :)
Thank you algo king Abdul 🙏
Bari sir visited our college im really gratefull for that,
but unfortunately the students were not cooperating with him, so he eventually left the class
Sir, this solution won't work for K4(complete graph with 4 vertices) graph
Thank you sir for these types of videos it's really very helpful for us ❤️❤️
Thankyou abdul! great bideo!
14:13 i'm convinced that ur the best teacher
You missed 1-4 in map problem
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 if we are having only 3 nodes and 3 colors how could we do the problem ??
Tommorrow is my exam and i done prepration by your video 🍀🍀
cam share your exam paper
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
really helpful sir thank you very much
What an explanation sir,,👏👏👏
Isn't M - coloring optimization problem solved via dynamic programming since it's an optimization problem?
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
🙏 Thank You Sir❤❤🫶❤❤🥳🥳💕💕
please make tuturial on red black tree
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.
looks little bit like gujarat map, btw nice video appreciate the effort.
15:5 also a 1- 4 is present
Superb sir....seriously the way you explain and speak is so easy and understandable to any one.....
Sir for Network flow and matching lecture video is available or not?
Algolegend
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.🤔🤔
Obviously we can count the distinct minimal coloring's and we know the chromatic polynomial value for that and the fact it is zero for smaller colors. But is that enough information to generate the chromatic polynomial. I can do it out mathematically but now i am looking for a algorithm i can program. I have a backtracking algorithm similar to what your doing in this video. But i not so sure the most efficient and best way to go about obtaining the chromatic polynomial from all this information i can obtain. (in the optimal currently known algorithms !)
Sir, this is working in sequence number means 1,2,3..... Like this
Or
This is working with the adjacent
Way better than Boring and upto some extent useless Ravula Lectures.
will there be a direct path from node 1 to node 4 in Map to graph. Anyone help me in understand.
Sir apki clothing item koi kharidta bhi h price bohut kam ni h 😅😂
At 14:50, isn't region(1) neighbour to region(4)?
Controlling parameter is no of node,state space tree,bounding function backtracking
is there any rule to start colouring from specific vertex? or we can start colouring from any vertex?? please reply @Abdul Bari
Thank you for your great effort and helping students around the world.
Sir mere clg me bomb blast kr do padhana ni ata unhe. 😩
Thanks.
awesome. thank you so much
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?
in that map vertex 1 should connect to vertex 4
dear sir please take some compicated problem....this is very easy ....please explain compicated one
Sir,1is adjacent with 4 also.but,you are not mentioned there
well explained, good camera, thanks
why can't you say the formula for mcoloring optimization problem
Why doesn't sir upload more videos we need more videos for various topicss
Hello, how many chromatic number of (c7) power 2 ????
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 , explanation with algorithm would have been better
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
thanks a lot !
siema kto z preoi?