12. Greedy Algorithms: Minimum Spanning Tree
Vložit
- čas přidán 3. 03. 2016
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Erik Demaine
In this lecture, Professor Demaine introduces greedy algorithms, which make locally-best choices without regards to the future.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
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
Sir Erik you are best at teaching.. thankyou for the support...
Erik Demaine is one of the best Instructors!
Really appreciate the MIT resource on this. Erik is an amazing teacher!
correctness for Prim's algorithm 52:01
correctness for Kruskal's algorithm 1:15:35
Perfect Textbook lecture. Thank you
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
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 :***(
What an excellent lecturer! Very clear and concise.
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?)
One of the best teachers
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
First time in my life loving the proofs
That was a valuable lecture... But that chalkboard almost gave me mild asthma 😂
Amazing instructor
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.
Great lecture!
This guy is a pro at writing on a chalkboard.
Erik is a genius !
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.
Wow...!i like his lecture.
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.
33:04 exchange argument (cut and paste argument)
yea the name confuses me, and turns out it is just the exchange argument 😂
@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
@ 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"
awesome
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
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
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 ....
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!!
@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
#besten#Episode#Liebe#Soll#schönen#Highlight#
so cool (y)
Where is recitation 3 lecture?
Sorry, recitation 3 is not available.
@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
this guy is so fucking awesome
wish i could i understand what you say man, i really tried. thanks for the support though.
17:30
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!
@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.
after watch 1 hour of super cool lecture, my brain is still blank .will anyone suggest a brain booster tonic ?:( :)
I think the camera man is the best attentive and hope he’s taking notes too lol
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.
Thanks you MiT now i hate science and hate algorithm and hate myself for failing
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
Lucky, I didn't take those kind of classes.
I wanted to be on those benches! 💔
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...
> tree = directed connected acyclic graph
a ->- b ->- d
└-->- c ->-┘
according to the definition this must be a tree, but it's not
18:00 best way to contract an STD
43:32
seems like nicki minaj has been using prims algorithm to grow her ass
confusing
i cant understand
you are not alone, but exerciese think about out what the condition what the small steps
Itne saare black board.......
Added this comment cause I cant like twice
Thanks Eric
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 !!!