6.3 Graph Coloring Problem - Backtracking

CORRECTION: at the end of this video, in a MAP, region 1 is also Adjacent to region 4
Graph coloring problem using Backtracking
PATREON : www.patreon.com/bePatron?u=20...
Courses on Udemy
================
Java Programming
www.udemy.com/course/java-se-...
Data Structures using C and C++
www.udemy.com/course/datastru...
C++ Programming
www.udemy.com/course/cpp-deep...

[@scabbage]

I like how he actually took the effort to draw the last level.

[@gannonben2554]

instablaster.

[@kunalakhade5660]

I was like how will I draw the level in the exam paper

[@SandeshMotoVlogs]

@@kunalakhade5660 Indian teachers are like it should look neat no matter whether that's gonna fit in the area/page

[@shaikhtaqueveem6819]

​@@kunalakhade5660 how did you draw...

[@mahadevawasthi8187]

Someone give this man a medal 🥇 . He is better than the lecturar of expensive private universities. Hats off to you legend 🔥

[@gaharavara]

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

[@ayounghosh9218]

I feel like I'm giving my fees to the wrong teachers, my college should hire teachers like him instead

[@anirudhavadhani8586]

same here

[@sanayshah1]

Same same

[@matthieub3973]

What program are you majoring in that you're learning stuff like this? AI or something? That's great!

[@CoderBrains]

Just try this kzbin.info/door/4CwQWuy47lTFP8-RhtF8lw?view_as=subscriber

[@artisingh1944]

damn true

[@chepaiytrath]

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

[@ankursoni8751]

The way you gracefully explain the complex problem is just amazing. Thank you for all your hard work. :)

[@swatisharma9373]

funny thing is my college teacher is making notes from your videos and still could not teach

[@lokeshkandpal6600]

Same🥲😂

[@yhwu4747]

brilliant storytelling of the historical case where the graph coloring can be applied!

[@shivammwarambhey5614]

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.

[@benneal8224]

Your videos are a gift to the world! Thank you

[@LL-ol8gr]

Best CS teacher ever, make every topic bite-able.

[@brettford7521]

Your videos have a lot of educational value, thank you so much for sharing. Currently taking Algorithm Design and Analysis

[@ujwalgupta7457]

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.

[@codeforester]

What an excellent teacher! I feel like I am back in college! Thank you Abdul for educating us.

[@johnlebens6463]

Your videos are the best sir! Thank you for getting me through my algorithms class. Keep up the good work :)

[@ashokindiagaming6064]

A

[@HAAH999]

Thank you for your great effort and helping students around the world.

[@abhijeetiyer1556]

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

[@TridibSamanta]

Great ! You are a great Teacher. Thanks for saving my Design and analysis of Algorithm Paper. #Respect

[@shwetankjoshi3011]

Which university

[@gopeshkhandelwal9823]

sir ,your teaching style is awesome .Really, love your videos

[@c.danielpremkumar8495]

I appreciate your immediate response.

[@sapingeli]

I am a big fan of you, now following everything about algorithms and maths.

[@tejudimple689]

Superb sir....seriously the way you explain and speak is so easy and understandable to any one.....

[@arunachhatkuli2103]

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.

[@ajinkyabhalerao984]

Exactly!

[@maheshmahi06981]

Yes 1 and 4 have connection

[@malaykumar7991]

Thank you sir. 🙂 Your videos are very helpful for papers .

[@MdAsif-zx5wy]

itna zyada student seen kr rha ....bhut accha sir,thanku so much sir for ur help

[@GustavoHenrique-xg4ey]

well explained, good camera, thanks

[@rrMaxwell]

the map printing example was superb professor

[@RS_renovation_10]

Thank you sir for these types of videos it's really very helpful for us ❤️❤️

[@chanduyerragundla2268]

Your an life savior of many btech students in jntu

[@putluruvenkatsabarisainath7009]

good Teacher.Learnt many things.so simple in understanding.

[@mpmukundh]

Please include algorithm sir

[@mansonchallenger1143]

best explanation of backtracking this far

[@anums4590]

Your channel is very helpful

[@anuragvishwa1847]

Sir is, Aamir Khan of Algorithms

[@bavalpreetsingh4664]

thugs of hindustan flops

[@RajVerma-lg3kp]

Bavalpreet Singh lmao 😂

[@ttctoh]

He is Lee CHong Wei of Algorithms

[@KeshariPiyush24]

wanted to like this comment but it is on 69 so not doingXD

[@theonefromtheback]

Best teacher I've seen my teacher is not even close to him!!

[@aryantiwari3823]

even after 100 years , this man will be remembered

[@ssm840]

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?

[@nishant9972]

thanks, wrote the code directly, didn't even need to take any reference or watch it again

[@stith_pragya]

Thank You So Much Abdul Sir..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻 as usual super dooper explanation

[@shikshagarg5855]

Thanks. Very helpful!

[@Nani-ox4ht]

What an explanation sir,,👏👏👏

[@udaykumar5387]

really helpful sir thank you very much

[@lspophale]

voice is so good to understand and skip written part by himself which is not imp thats so better

[@ajaykommalapati9906]

It's really good sir.

[@dr.p.sridevi2626]

Thank you for your great effort

[@jaslinkaur645]

For the graph colouring problem at 14:55, should not vertex 4 connect to vertex 1? The boundaries connect

[@santoshreddy9963]

same doubt

[@lucifercp4056]

+1

[@jeffmathew6238]

it should...just change the solution accordingly

[@rahulraut2689]

@Abdul Bari In university exam, is required to find all possibility of graph coloring ?

[@mohammedadel8948]

Thank you , I appreciate your help so much

[@vishallondhe7298]

looks little bit like gujarat map, btw nice video appreciate the effort.

[@cvismenu]

very conceptual

[@vishnuvardhans8463]

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

[@hemantsingh6420]

Sir for Network flow and matching lecture video is available or not?

[@danishbhatia1734]

great job sir.

[@amanjain256]

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?

[@aniljami6786]

Yes,but assume that 2nd vertex is completely in between 1 and 4 i.e the small uncovered region is to be covered

[@sonudwivedi4815]

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

[@gnrh123]

Thank you algo king Abdul 🙏

[@garlapatibalu6192]

sir if we are having only 3 nodes and 3 colors how could we do the problem ??

[@danym-98]

Thanks!

[@jackiechoe1841]

Thankyou abdul! great bideo!

[@harishchirati2311]

thank u nice explanation sir

[@unofficialcoder]

very well explained sir

[@adipratapsinghaps]

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

[@adipratapsinghaps]

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

[@bhuveshdhiman2]

@@adipratapsinghaps you can apply greedy algo for this q

[@somilshah7841]

nice explanation :)

[@ggauthamin7420]

Thank u so much sir! really

[@Mithilesh165]

Awesome sir....Thank you....😇😇😇😇

[@c.danielpremkumar8495]

Is there a condition as to whether all the given colours must be used ?

[@deeproy7292]

awesome example on application✌

[@tusharsingh2286]

Tommorrow is my exam and i done prepration by your video 🍀🍀

[@AdarshkiBines]

cam share your exam paper

[@Hindicartoonstory0308]

Sir it is simple graph,how can we do backtracking using tree in complex graph like if there is path between 2 and 4

[@anandbaskaran]

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

[@sadrahakim1272]

awesome. thank you so much

[@aparnazomeeeeee2]

Great explanation ❤️

[@sam111880]

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?

[@bavidlynx3409]

i cant really find any easy to write algoritms. i know hes a great teacher but he aint explining any algoritms

[@onais__]

@@bavidlynx3409 hey, so from where did you do the algo explanation part

[@kshnt9996]

Can you provide lisp programming for the same problem using any search method

[@chandrakanthsagar8886]

Great explanation 🔥

[@ericwang4917]

Can you also do the machine learning algorithm too, and thank you for helping understanding these concept :)

[@sai007]

Sir.. actually how many solutions can obtain at end of the video is 18 or more that?

[@user-su3cl5jh8o]

Thanks for the video!

[@HamsaShehadeh]

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?

[@sushanth6039]

Sir time complexity of this problem?

[@priyankapasupuleti5892]

Nice superb explanation

[@sivaram9654]

*really helpful*

[@SaiKumar-zw9eh]

Sir, firstly thanx for your videos. In the above example, if we draw tree by taking even GREEN and BLUE in the root node then the tree expands very large so would you suggest how to represent such huge trees in exam?

[@GauthamBangalore]

Thank you. It's really insightful.

[@gideonkiplagat4232]

Can you explain how GCP can be used in College/exam Timetabling

[@shreyashdhasade9717]

baeutiful explaination sir

[@user-ic9kf9my9c]

14:13 i'm convinced that ur the best teacher

[@namankhard4270]

Sir it would be much better if you provide algorithms as well because in exams they ask algorithms too.

[@darshanarani9059]

Yes please Sir

[@TusharYadav-es1bq]

he doesnt know them

[@varunrao2135]

@@TusharYadav-es1bq writing the algorithm is trivial if you understand the algorithm well. Understanding algorithm is more difficult

[@Homelander-compV]

@@TusharYadav-es1bq kiddo

[@asmrao3824]

is this also called Constraint Satisfaction problem? CSPs?

[@schaudhari]

Sir please upload Live variable analysis in compiler design thanks

[@user-js9xq1ps3s]

Μεγάλος μάστορας αυτός παιδιά.

[@niteshtiwari1828]

Sir please make videos on TOC.

[@bhaskarchakrawarty6908]

Study From Sanchit Jain @knowledgeGate

[@HelloWorld-zt4ol]

is there any rule to start colouring from specific vertex? or we can start colouring from any vertex?? please reply @Abdul Bari

[@k-ananya9657]

Thank you so much sir, respect and love from Bangladesh ❤️🇧🇩

[@ThuyVu-pv5wd]

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.

[@gateeasycse]

can u explain bounding function

[@amitkumarsrivastava9261]

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

[@youtubesu9358]

Thank you so much.

[@codelover847]

In exam , how are we going to draw the space tree of such a lengthy problem?Please suggest some ways

[@piyushlohani3278]

sir how to determine minimum number of color required to color a graph

[@nurzhanamantay8729]

thanks a lot !