Man, I am happy 3B1B did this contest. I've been clicking on all of the contest videos I could find and the youtube algorithm now understood to suggest videos like yours. Short, simple and well visualized. Well done.
"To fix the problem, we'll avoid it." LOL - best way to deal with any problem! Seriously, great video and I'm not really a computer guy. But you got my vote!
In the "real world", politicians and megacorporations just "move problems" by pretending to solve the problem like with EVs: either way, CO2 will be made, so do you do it with coal or gas?
In elementary school my teacher was having a hard time with something like this. There was 24 students and she wanted to set us up in deak groups of 4 but wanted groups who could get along. I suggest everyone write a list of everyone else they could get along with and we made a freinf graph then did something similar by hand to find the happuest arrangement Of course this made 2 problems arise however 1. Relationships change 2. Kids getting along means they are more talkative and pay less attention
That’s an even harder problem, because you’re trying to find a maximum set of copies of K4 all of whom are disjoint, and who are subgraphs of your original happy graph. Which in turn makes me wonder if there are actually good solutions to these harder problems.
One of my favorite algorithms! Jack Edmonds once told the story of how he invented it. He had a conference talk scheduled but no results to present. While scrambling late into the night before the talk, he had the idea of the blossom ("Heureka, you shrink!") and worked out the whole algorithm.
The video was great, but I sometimes didn't visually recognize fast enough which parts of the graphs changed colors. Obviously I can just rewind, but for the future, you should pick your colors a bit more carefully. A simple fix would be to give static elements (matches, exposed vertices) a dark color and then give your animations (BFS, augmenting paths) very bright colors. In general, it is visually easier to discern by brightness than by color value. So a bright blue and a dark blue can be easier to distinguish than a medium blue and a medium purple. edit: you could also work with outlined vs. filled nodes if your animation tool supports that without much extra effort
That's actually something I explicitely thought about when creating the video, but it's clear (from your feedback and also as I watch the video again) that the contrasts are not good enough. I'll try to pick the colors more carefully in the next videos, and also maybe add some visual cues (maybe like particle effects) when the colors aren't clear enough by themselves. Thanks for the feedback!
@@YTomS Additional effects obviously also help, but they are additional effort. Just switching the color palette doesn't cost anything, so try that first. It should be sufficient for most circumstances.
Part of the problem is that there is no way to change the speed of the visualization vs. the speaking. To visualize some of the sequences of changes especially that starting at 2:37, you need to slow the visualization, which distorts the speaking--though it's still completely intelligible.
I don't usually have a problem following courses in English, with various accents, but for this video I had to turn up the volume considerably and read the subtitles.
Hi Tomas! It's a fantastic video. Entertaining to watch. And I learned clearly. Would you like to make a video on how u made those graphics look so effortlessly simple? I would be a very good education to me. Thanks, Madhukiran :)
Thanks for the kind words! All of the animations were created using Manim and the source code is in the description, if you'd like to take a look. It is a bit of a mess though, a better resource is the official Manim documentation. I'd recommend you take a look at it if you're looking to create some animations on your own: docs.manim.community/en/stable/index.html
@@YTomS I've noted down the link. Not immediately, but I'll definitely learn the techniques to create videos with animations like yours. There is a playlist created by Derek Banas on AFTER EFFECTS. Please take a look. I feel your's and his' are very important for me to make videos of ur standard. Finally content is the king, but when there are so many videos on yt on majority topics, good animations is the right way to attract attention of viewers. U did a gr8 job. I've thoroughly enjoyed watching. Please continue to make high quality content
Hi Tomas, How did you identify a blossom? It seems there is no need to track the entire cycle to notice that -- -- a cycle is formed when the return edge meet an already visited vertex -- and that the cycle has odd number of edges It seems an odd alternating cycle i.e. a blossom is automatically by the presence of a B edge (i.e. edge of type-B) between 2 vertices of same level (level determined by BFS, incrementally for neighbor nodes, with start vertex at level 0) -- if odd level, the B edge wud be a matched edge -- if even level, the B edge wud be an unmatched edge This feels more easier than tracking a cycle and whether it is odd or even. Please reply with the algo u have used. Thanks for reading :)
The code in the video is mostly pseudocode, so there might be some details missing. There are also some uglier parts of the code that I intentionally excluded because it takes away from the idea od the algorithm. If you're interested in a proper implementation, there are a few in various languages on GitHub.
Hi Tomas, Please see if u wud like to consider this suggestion. The animations are gr8 but too fast. Since I've to listen to u, understand the concept, as well as follow the animation... I'm getting confused if it's animating quickly I feel u cud slow down the animation speed a little more... ...and also add an arrow to indicate the direction of flow along the edges, apart from the flow of colors The audience can avoid multiple pauses and playbacks then, I think so :)
@4:44 Hi Tomas, Shouldn't this be the correct code as per the blossom concept? if found_blossom(): contract_blossom ----------> flag=false if find_augmenting_path != []: switch_augmenting_path flag=true if flag=false: return []
We should teach this in our elementary school math class! Your video makes it sound that easy. I implemented this algorithm before, and it took me two weeks. Pure respect for making it very easy to understand!
There's a huge difference between maximum matching and maximal matching, finding the former is NP hard, latter is quite easy, you seem to have them mixed up. The theorem you point to is about maximal matching, which is reasonable because the theorem doesn't hold for maximum matching (only one direction holds)
The link seems to be pointing to a wrong resource, I corrected the issue (also, there was a typo). Also, if I, at any point, said maximal, then I meant maximum and that was also a mistake. Regardles of that, finding maximum matching is definitely not NP hard, as the linked paper states. Where do you think the theorems are mistaken?
