I've just utilised Kruskal's algorithm to solve a real-world problem we were facing at the company I work at. It is a very simple and elegant algorithm to implement. As of writing, it's solved our requirement of finding a spanning tree of a connected cyclic graph containing around 80 nodes, but we may have future instances with even more nodes (hundreds!). In our setup, none of the edges have weights so it just picks a random edge each time, effectively producing an arbitrary spanning tree upon each invocation of the problem, which is fine for what we need it for. Excellent video!
The proof of the greedy choice property is incorrect. You can’t exchange any edge crossing the cut with e to get the MST but you have to find the edge that is part of the cycle when you add e. And this uses the property of a cut that if an edge that crosses a cut is part of a cycle then there’s another edge of that cycle that crosses the cut too. And this cycle edge may or may not be the current edge we’re trying to exchange in the Tree.
Corporations pay employees as little as possible: the greedy choice. But if all corporations paid employees abundantly, they'd make more sales when the public has more disposable income, and they'd be richer in the long run. The locally optimal solution is not always the best.
Thank You. Sir, you are an amazing teacher. Thank you for your videos, they are so clear and easy to understand. However, I'm a little confused still about the running time of Prim's. Would anyone be able to explain how you can decrease a key in a Fibonacci heap in constant time? If you were implementing prim's with a regular min-heap, would the running time change from O(Vlog(V) + E) to O(Vlog(V) + Elog(V)) to reflect the slower decrease key operation? (normal heaps, as I understand, take log(n) time to decrease the value of a key, correct?)
Its correct proof the optimal substructure only by cut y paste that show in Cormen in programming dynamic chapter, if T* = T contracting a edge, and T = w(edge) + T*, suppose that T is minimum, if T* is not minimum, I can copy a minimum spanning tree T** here and, we get a T not is minimum, what is a contradiction.
@30:38 he says a crossing edge is defined by whether or not it has a vertex in V and the other vertex not in V. Did he mean to say a vertex is in S and the other is not in S?
What an excellent teacher. However, I'm a little confused still about the running time of Prim's. Would anyone be able to explain how you can decrease a key in a fibonacci heap in constant time? If you were implementing prim's with a regular min-heap, would the running time change from O(Vlog(V) + E) to O(Vlog(V) + Elog(V)) to reflect the slower decrease key operation? (normal heaps, as I understand, take log(n) time to decrease the value of a key, correct?)
Yes. Given that you are using an adjacency list: Fibonacci Heap Priority Queue -> O(|V|.log|V| + |E|) Min-Heap Priority Queue -> O((|V|+|E|)log|V|) If you are using a matrix instead of adjacency list, for every V you will loop through all vertices instead of just its degree, however, you still perform operations only when there is an edge. So: Min-Heap -> O(|V^2| + (|V| + |E|) log |V|) -> O(|V|^2 + |E| log |V|). Fibonacci Heap -> O(|V|^2 + |V| log |V|) -> O(|V|^2). |V| -> # of Vertices |E| -> # of Edges
No he deletes the edge AND merges the vertices, so it's still a single spanning tree. He says that like literally seconds later - "Contraction preserves connectivity"
If I understand your question, you're asking if both U and V are part of the MST. Answer is yes, because if edge e={u,v} is part of the MST then both vertex U and vertex V has to be part of the MST. Also for your second question "which paths do not include edge e={u,v}?", the answer it that there can be many paths which do not include that edge. Those paths a higher cost than the path edge e={u,v} is part of, and therefore does not create a MST.
doesn't the picture @ 19:20 says that the graph is cyclic? But spanning trees are acyclic. Looks like a case of a bad example, or am I missing something?
I'm preparing for my PhD algorithm qualifying exam and this video helps me to understand the proof. However, signs are too much and they can be more simplified. Also, class notes helped but the graphs are not in the class notes which could be so much useful to understand the proof easier.
Since the last lecture, Eric has been trying to emphasize that purple is better than blue. Whereas in lecture 10 Srinivas said blue is better than purple. Interesting...
@17:00 onwards, if an edge(red) from 1st part ends in 2nd part, then the graph would not be an MST...but we have already supposed it to be a MST with e being an edge.... Please clarify this doubt....!
I believe that Professor Demaine made a slight error at 36:25 relevant to your question in his writing of a proof that every least weight edge that crosses a cut of an (undirected) graph is part of a minimum spanning tree of that graph. Just before that, he talked about how, given a possibly different minimum spanning tree, T*, there was a unique path from u to v in T* and that that unique path also must cross the cut, but then he did not use that lemma in writing the proof. In his proof, he wrote that we could choose any edge e' in T* that crosses the cut. I think he meant to put a further condition on e' that it must also be one of the edges in the path from u to v within T*. That way, removing e' disconnects the subgraphs containing u and v, and then adding e reconnects them without creating a cycle.
how can i get acces to more lessons and PDF files , i am a student at a german university " RWTH aachen and i am interesed in having the textbooks to read please
See the course on MIT OpenCourseWare for more course materials (lecture notes, exams with solutions, assignments with solutions, recitations) at ocw.mit.edu/6-046JS15.
Yeah thnx I have checked , but some of them are limited , I don't have full access , for exemple I want operating system concepts , there is only notes , but no full lecture
It's for the benefit of the students, it takes time to write it by hand, time they also need to write notes at a pace that allows them to continue to pay attention while also understanding what they are writing. This stuff requires thought to understand, and even MIT students need time to grasp new information.
My university banned teachers from using PowerPoint during math/science lectures. It eliminates demonstrating the entire thought process and pace behind the critical thinking needed to learn and solve these concepts.
Prim's algorithm starts 42:20
Kruskal's algorithm : 1:06:00
you the best!
thank you...that's what I'm looking for
Love ya
Inorder to understand why/how Prim's works you need to see the before part of this video as well.
Careful he's a lord
correctness for Prim's algorithm 52:01
correctness for Kruskal's algorithm 1:15:35
I've just utilised Kruskal's algorithm to solve a real-world problem we were facing at the company I work at. It is a very simple and elegant algorithm to implement. As of writing, it's solved our requirement of finding a spanning tree of a connected cyclic graph containing around 80 nodes, but we may have future instances with even more nodes (hundreds!). In our setup, none of the edges have weights so it just picks a random edge each time, effectively producing an arbitrary spanning tree upon each invocation of the problem, which is fine for what we need it for.
Excellent video!
If the edges have no weight than any search algorithm (dfs, bfs) will find a spanning tree
Erik Demaine is one of the best Instructors!
Really appreciate the MIT resource on this. Erik is an amazing teacher!
Sir Erik you are best at teaching.. thankyou for the support...
Im in the top 500 universities, and still finding youtube helping me more then my prof....
Professors are always excellent researchers, but not always good teachers.
@@cosmic_gate476 yeah thats so true :***(
I really enjoy this professor. Thank you MIT and Professor Demaine.
Regards from The University of Toledo.
Wow. This guy is good. Very impressed with this lecture.
yeah dude is a genius
I really like the old style by using chalks and blackboards especially their snappy sounds
That was a valuable lecture... But that chalkboard almost gave me mild asthma 😂
First time in my life loving the proofs
Perfect Textbook lecture. Thank you
Totally Impressed with U sir , why i find u so late... u are fanstastic teacher
yeh sab chutiyapa desi page par karna
just cant stop laughing ....
One of the best teachers
This guy is a pro at writing on a chalkboard.
@27:05 in what situation is w(T') < w(T* - e)? Isn't w(T') = w(T* - e)?
Before he wrote that he said that T' is the minimum spanning tree of a graph with G/e nodes.
So by definition w(T')
@@archidar1 thx i've been looking for this
The proof of the greedy choice property is incorrect. You can’t exchange any edge crossing the cut with e to get the MST but you have to find the edge that is part of the cycle when you add e. And this uses the property of a cut that if an edge that crosses a cut is part of a cycle then there’s another edge of that cycle that crosses the cut too. And this cycle edge may or may not be the current edge we’re trying to exchange in the Tree.
What an excellent lecturer! Very clear and concise.
Amazing instructor
man I wish I went here );
ok
Two years later! I completed my B.S. in Computer Science ya'll!
good
@@eeee8677 congratulations!
@@eeee8677 way to go!!
Corporations pay employees as little as possible: the greedy choice. But if all corporations paid employees abundantly, they'd make more sales when the public has more disposable income, and they'd be richer in the long run. The locally optimal solution is not always the best.
Does anyone know which microphone this professor is using? really crisp and clear! thanks!
It was most likely a wireless lav microphone from Sony. Not sure what exact model... it was seven years ago.
Thank You. Sir, you are an amazing teacher. Thank you for your videos, they are so clear and easy to understand. However, I'm a little confused still about the running time of Prim's. Would anyone be able to explain how you can decrease a key in a Fibonacci heap in constant time? If you were implementing prim's with a regular min-heap, would the running time change from O(Vlog(V) + E) to O(Vlog(V) + Elog(V)) to reflect the slower decrease key operation? (normal heaps, as I understand, take log(n) time to decrease the value of a key, correct?)
33:04 exchange argument (cut and paste argument)
yea the name confuses me, and turns out it is just the exchange argument 😂
Its correct proof the optimal substructure only by cut y paste that show in Cormen in programming dynamic chapter, if T* = T contracting a edge, and T = w(edge) + T*, suppose that T is minimum, if T* is not minimum, I can copy a minimum spanning tree T** here and, we get a T not is minimum, what is a contradiction.
Erik is a genius !
@30:38 he says a crossing edge is defined by whether or not it has a vertex in V and the other vertex not in V. Did he mean to say a vertex is in S and the other is not in S?
Of course he did
Thanks you MiT now i hate science and hate algorithm and hate myself for failing
What an excellent teacher.
However, I'm a little confused still about the running time of Prim's. Would anyone be able to explain how you can decrease a key in a fibonacci heap in constant time? If you were implementing prim's with a regular min-heap, would the running time change from O(Vlog(V) + E) to O(Vlog(V) + Elog(V)) to reflect the slower decrease key operation? (normal heaps, as I understand, take log(n) time to decrease the value of a key, correct?)
Yes.
Given that you are using an adjacency list:
Fibonacci Heap Priority Queue -> O(|V|.log|V| + |E|)
Min-Heap Priority Queue -> O((|V|+|E|)log|V|)
If you are using a matrix instead of adjacency list, for every V you will loop through all vertices instead of just its degree, however, you still perform operations only when there is an edge. So:
Min-Heap -> O(|V^2| + (|V| + |E|) log |V|) -> O(|V|^2 + |E| log |V|).
Fibonacci Heap -> O(|V|^2 + |V| log |V|) -> O(|V|^2).
|V| -> # of Vertices
|E| -> # of Edges
@@yosrym93 bro be honest are you a robot
It's was a shock for me and a good push too knowing that even professors at MIT need to look to a paper while building a proof!
Wow...!i like his lecture.
@ 25:41 isn't that T* was cut to two subtrees since he was deleting the edge instead of merging it? can we say two trees is a spanning tree then?
No he deletes the edge AND merges the vertices, so it's still a single spanning tree. He says that like literally seconds later - "Contraction preserves connectivity"
Great lecture!
wish i could i understand what you say man, i really tried. thanks for the support though.
Are both vertices sets from the example starting @ 14:20 supposed to be connected on the spanning tree, with paths that do not include the edge e?
If I understand your question, you're asking if both U and V are part of the MST. Answer is yes, because if edge e={u,v} is part of the MST then both vertex U and vertex V has to be part of the MST.
Also for your second question "which paths do not include edge e={u,v}?", the answer it that there can be many paths which do not include that edge. Those paths a higher cost than the path edge e={u,v} is part of, and therefore does not create a MST.
doesn't the picture @ 19:20 says that the graph is cyclic? But spanning trees are acyclic. Looks like a case of a bad example, or am I missing something?
Spanning tree must be acyclic but that doesn't mean the graph has to be
Graph is cyclic and spanning trees are not
Where is recitation 3 lecture?
Sorry, recitation 3 is not available.
Lucky, I didn't take those kind of classes.
I'm preparing for my PhD algorithm qualifying exam and this video helps me to understand the proof. However, signs are too much and they can be more simplified. Also, class notes helped but the graphs are not in the class notes which could be so much useful to understand the proof easier.
complain more
Since the last lecture, Eric has been trying to emphasize that purple is better than blue. Whereas in lecture 10 Srinivas said blue is better than purple. Interesting...
awesome
after watch 1 hour of super cool lecture, my brain is still blank .will anyone suggest a brain booster tonic ?:( :)
@17:00 onwards, if an edge(red) from 1st part ends in 2nd part, then the graph would not be an MST...but we have already supposed it to be a MST with e being an edge....
Please clarify this doubt....!
if you delete edge e (and the components are still connected), you are in essence creating a new MST with a min red edge
#besten#Episode#Liebe#Soll#schönen#Highlight#
this guy is so fucking awesome
I think the camera man is the best attentive and hope he’s taking notes too lol
18:00 best way to contract an STD
I wanted to be on those benches! 💔
> tree = directed connected acyclic graph
a ->- b ->- d
└-->- c ->-┘
according to the definition this must be a tree, but it's not
@38:05, what if u and u' are connected by a path that includes e' ?
I believe that Professor Demaine made a slight error at 36:25 relevant to your question in his writing of a proof that every least weight edge that crosses a cut of an (undirected) graph is part of a minimum spanning tree of that graph. Just before that, he talked about how, given a possibly different minimum spanning tree, T*, there was a unique path from u to v in T* and that that unique path also must cross the cut, but then he did not use that lemma in writing the proof. In his proof, he wrote that we could choose any edge e' in T* that crosses the cut. I think he meant to put a further condition on e' that it must also be one of the edges in the path from u to v within T*. That way, removing e' disconnects the subgraphs containing u and v, and then adding e reconnects them without creating a cycle.
What's the thing with the frisbee?
Each time someone gives a valid answer/proposal on one of the professors questions, they get a frisbee, although it used to be pillows!
how can i get acces to more lessons and PDF files , i am a student at a german university " RWTH aachen and i am interesed in having the textbooks to read please
See the course on MIT OpenCourseWare for more course materials (lecture notes, exams with solutions, assignments with solutions, recitations) at ocw.mit.edu/6-046JS15.
Yeah thnx I have checked , but some of them are limited , I don't have full access , for exemple I want operating system concepts , there is only notes , but no full lecture
Not every class has lectures. Generally what you see on the site is the resources they have.
17:30
43:32
seems like nicki minaj has been using prims algorithm to grow her ass
so cool (y)
Added this comment cause I cant like twice
Thanks Eric
Itne saare black board.......
i cant understand
you are not alone, but exerciese think about out what the condition what the small steps
confusing
Why is my professor so shit, he literally reads of slides.. And doesn't even make sense doing it
This guy writes too much
too much writing. Why didn't he use a powerpoint
powerpoint kills actual thinking.
Such online lectures were my motivation to learn the cursive writing (not native speaker) and fast writing.
It's for the benefit of the students, it takes time to write it by hand, time they also need to write notes at a pace that allows them to continue to pay attention while also understanding what they are writing.
This stuff requires thought to understand, and even MIT students need time to grasp new information.
My university banned teachers from using PowerPoint during math/science lectures. It eliminates demonstrating the entire thought process and pace behind the critical thinking needed to learn and solve these concepts.
worst 1 hr i ever spent !!!
16:29