Wish I could sit in that room, answer your questions, get a frisbee :-) but it's still good. Thank you MIT for providing this level of education for free. If I grew up to earn sufficient money, I will surely donate so that you continue with this good work forever.
Thank you very much! This was the first clear explanation of this topic. I highly recommend it to those who are studying "advanced algorithms" on coursera.
fuck have an exam next week with this topic. The professor only gave us a week to understand the material. Of course doable for smarties and exceptions but as a normal person. So intimidating.
Very straightforward and clear explanation and illustrative examples. It made me understand this interesting subject! You did in an hour and 20 minutes what my teacher didn't in 2 hours!
at 56:14 , one student asked a question about why don't we consider path s -> c. Sirinivas said when you don't have a particular edge from s to c, you can use skew symmetry to argue s->c and c->s cancelled out each other. I don't get his answer. We are considering f(S, T), why does c->s get involved and cancel s -> c?
Honestly, the camera guys need to pay attention to the lecture. When he asks about something that's on the board, don't point the camera at Srini. Point it at the BLACKBOARD, so that the viewer can also try to answer the question.
a super short proof of the Theorem at 40:49: 0=f(V,V)=f(s,V)+f(t,V)+f(V-s-t,V) ({s}, {t}, V-s-t are disjoint sets). Since f(V-s-t,V) = 0 (by conservation property), f(s,V)+f(t,V)=0. i.e. f(s,V) = -f(t,V) = f(V,t)
The proof at 1:03:00 seems a bit odd. he has broken up the RHS term in the parenthesis into 2 parts( but the rules he gave earlier break the LHS term in the parenthesis )
The MIT site has (pdf) documents for the lectures which you might enjoy. You may also pause the video. You may want to have side by side windows on your computer to see both at the same time.
What was the point of disallowing self edges and cycles (u,v), (v,u) at 22:58? I'm not really sure I understand the difference between net-flow and positive-flow and the impact of the professor's assumption on the following definitions/constraints and therefore proof.
Self edges cause accumulation of flow which is not allowed. You can think of this as the amount of flow coming into a vertex must equal the amount of flow leaving it (like Kirchhoff's law for current flowing through wires). Cycles are accommodated by adding an intermediate edge so as to preserve that there was a direction of flow (the capacities remain the same along the newly added edges). This modification helps when we form Residual Networks as then we have the possibility of alternating (2 way) edges. Both these assumptions help significantly in proving the theorems discussed in the video.
I have a doubt in the flow conservation formula. f(u,v) is 0 only for all edges between u and v right. If there's an indirect edge then we take it also as 0 right. In the case how f(s,t) also should be equal to 0 right as there's no direct edge between s and t?
+snlgrg If the next video (14. Incremental Improvement: Matching) isn't visible as the top recommend video in the top right column, see this playlist to see it and the rest: ruclips.net/p/PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp
What did that student mean at ruclips.net/video/VYZGlgzr_As/видео.html?? We did consider c at f(d,c) which is -1 . Not sure what did he mean with his question.
Yup. Thanks. It’s pretty overrated. If you go to Amazon, most of the reviewers are trying to sound smart and are just parroting each other. Then there are a bunch of negative reviews from people who are unhappy about damage to the copies they got. And then finally, there are some very well-thought-out and well-written criticisms of the book which really should be heeded. Amazing how mediocrity gains such credibility.
At the time point ruclips.net/video/VYZGlgzr_As/видео.htmlm40s we can see some numeric summation and the graph diagram at once. That is helpful. Then after that we rarely see them both at the same time, which is not helpful. MIT does provide the pdf at their website for more clarity. Their is a unfortunate combination of red chalk, handwriting, and excess camera movement. There is a simple summation of values, positive and negative and the explanation does not reflect that simplicity. Looking at the pdf document and the video simultaneously is useful. MIT might consider full screen pip (picture in picture) and chalkboard centric view simultaneously for ease of viewing.
its unbelievable he managed to extend a simple 20 minute topic (at max ) and lecture it for 1 hour and 22 minutes. im in 1h15min and still havent seen a defn about ford fulkerson method which he tries to explain. completely trash. if you want to learn the algorithm, dont waste your time on this video, watch ucdavis, idk.
Kanka 6 sene olmuş ama ben senin kadar köylü bir adam görmedim. Dersin ana konusu zaten ford fulkerson algoritması değil, adam algoritmanın çalışma mantığının altında yatan sebepleri ve teoriyi anlatıyor bazılarının da kanıtlarını veriyo. Bir sike sap olabildin mi çok merak ettim bu kafayla
Cut -> 46:45
Residual Graph -> 1:08:10
Augmenting Path -> 1:18:10
thanks mate haha
Thanks!!
You dropped this, 👑
thanks bruh
Not all heroes wear capes
Wish I could sit in that room, answer your questions, get a frisbee :-) but it's still good. Thank you MIT for providing this level of education for free. If I grew up to earn sufficient money, I will surely donate so that you continue with this good work forever.
I don't know how I would survive algorithm classes in my school without these MIT lectures.
hookers and cocaine my friend
Watching it fit previous diagrams and rounding numbers is interesting
Only video about network flow I was able to understand - thanks MIT.
You're rocking it, Srinivas 🎉
The lecture is phenomenal!! Thank you very much MIT for making this course open-source to the public !!
The Frisbee of true Computer Science!
Thank you very much! This was the first clear explanation of this topic. I highly recommend it to those who are studying "advanced algorithms" on coursera.
fuck have an exam next week with this topic. The professor only gave us a week to understand the material. Of course doable for smarties and exceptions but as a normal person. So intimidating.
if anyone's want to jump directly on finding cuts, @ 1:07:00 he starts to explain how you find min-cut
thank you very much
Very straightforward and clear explanation and illustrative examples. It made me understand this interesting subject! You did in an hour and 20 minutes what my teacher didn't in 2 hours!
I felt the electric 📐 angle on it. A great lecturer.
Love his enthusiasm!
Studying this alongside CLRS really really helps
He actually threw frisbee at students at an MIT lecture. That's hilarious....
A huge thanks and kudos to Professor Devadas.
at 56:14 , one student asked a question about why don't we consider path s -> c. Sirinivas said when you don't have a particular edge from s to c, you can use skew symmetry to argue s->c and c->s cancelled out each other.
I don't get his answer. We are considering f(S, T), why does c->s get involved and cancel s -> c?
I don’t know 🤷♀️. I just say in real life you need electricity or telephone poles.
Honestly, the camera guys need to pay attention to the lecture. When he asks about something that's on the board, don't point the camera at Srini. Point it at the BLACKBOARD, so that the viewer can also try to answer the question.
Thanks MIT for these great lectures!
a super short proof of the Theorem at 40:49:
0=f(V,V)=f(s,V)+f(t,V)+f(V-s-t,V) ({s}, {t}, V-s-t are disjoint sets).
Since f(V-s-t,V) = 0 (by conservation property), f(s,V)+f(t,V)=0. i.e. f(s,V) = -f(t,V) = f(V,t)
That's the proof I come to as well when I try to come up with the proof on my own. Any idea why he uses a different method?
How does the sum at 28:40 even work? The sum of flow values outgoing from all vertices except source and sink equals zero?
1:12:48 esidual network base on flow
Thank you very much.
Perfect, thanks !
That's a very nice explanation !
at 51:36, doesn't it break flow conservation since one of the nodes has 2 going in but 3 goes out?
Great Lecture! Wonderful!
The lecture is really good but the movement of the camera is making me dizzy.
Excellent explanation.
This is great. Thank you
at 42:14
why f(s,V)=f(V,V)-f(V-s,V)?
because V-{s} and {s} are disjoint sets. By the third property, we have f(s,V)+f(V-s,V)=f(V,V)
Amazing class!
Please, show me upper graph when you explain residual graph network flow, I didn't know that how it works.
Cut 47:00
The proof at 1:03:00 seems a bit odd. he has broken up the RHS term in the parenthesis into 2 parts( but the rules he gave earlier break the LHS term in the parenthesis )
you can always negate and break the LHS, same deal
my teachers never gave me frisbees
Informative!! I am eating information like never before :)
Cool class
Mr. Cameraman focus on the BOARD more than on the teacher.
The MIT site has (pdf) documents for the lectures which you might enjoy. You may also pause the video. You may want to have side by side windows on your computer to see both at the same time.
i think the camera panning is automated right? seems like there is some tracking going on... If so that is pretty amazing
videofountain k
@@raynoldcsya8317 yeah imagine them holding the camera and track the board and professor for over 1 hour... a lot of endeavors
I saw Erik on the seat when camera zoom out
What was the point of disallowing self edges and cycles (u,v), (v,u) at 22:58? I'm not really sure I understand the difference between net-flow and positive-flow and the impact of the professor's assumption on the following definitions/constraints and therefore proof.
Self edges cause accumulation of flow which is not allowed. You can think of this as the amount of flow coming into a vertex must equal the amount of flow leaving it (like Kirchhoff's law for current flowing through wires). Cycles are accommodated by adding an intermediate edge so as to preserve that there was a direction of flow (the capacities remain the same along the newly added edges). This modification helps when we form Residual Networks as then we have the possibility of alternating (2 way) edges.
Both these assumptions help significantly in proving the theorems discussed in the video.
How does f(u, v) work in skew symmetry when (u,v) are not connected by an edge?
It would be 0 = -0 since we define any (u,v) with no explicitly given capacity as 0
46:46 cut
I have a doubt in the flow conservation formula. f(u,v) is 0 only for all edges between u and v right. If there's an indirect edge then we take it also as 0 right. In the case how f(s,t) also should be equal to 0 right as there's no direct edge between s and t?
is it related to gomory hu's algorithm?
How would you claim that using bottleneck value as the flow will always be correct ?
His bag is actually a 4-dimensional container
Can somebody Plz provide me the link to the next lecture, which is continuation of this one.. !!
+snlgrg If the next video (14. Incremental Improvement: Matching) isn't visible as the top recommend video in the top right column, see this playlist to see it and the rest: ruclips.net/p/PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp
What did that student mean at ruclips.net/video/VYZGlgzr_As/видео.html??
We did consider c at f(d,c) which is -1 . Not sure what did he mean with his question.
I think there is a small mistake at the end in the example.
Edge from c-> t should be 0:2
Min-cut example part not clear.
What's CLRS?
Yup. Thanks. It’s pretty overrated. If you go to Amazon, most of the reviewers are trying to sound smart and are just parroting each other. Then there are a bunch of negative reviews from people who are unhappy about damage to the copies they got. And then finally, there are some very well-thought-out and well-written criticisms of the book which really should be heeded. Amazing how mediocrity gains such credibility.
At the time point ruclips.net/video/VYZGlgzr_As/видео.htmlm40s we can see some numeric summation and the graph diagram at once. That is helpful. Then after that we rarely see them both at the same time, which is not helpful. MIT does provide the pdf at their website for more clarity. Their is a unfortunate combination of red chalk, handwriting, and excess camera movement. There is a simple summation of values, positive and negative and the explanation does not reflect that simplicity. Looking at the pdf document and the video simultaneously is useful. MIT might consider full screen pip (picture in picture) and chalkboard centric view simultaneously for ease of viewing.
I don't know about others but I don't like these kind of teachers
its unbelievable he managed to extend a simple 20 minute topic (at max ) and lecture it for 1 hour and 22 minutes. im in 1h15min and still havent seen a defn about ford fulkerson method which he tries to explain. completely trash.
if you want to learn the algorithm, dont waste your time on this video, watch ucdavis, idk.
Kanka 6 sene olmuş ama ben senin kadar köylü bir adam görmedim. Dersin ana konusu zaten ford fulkerson algoritması değil, adam algoritmanın çalışma mantığının altında yatan sebepleri ve teoriyi anlatıyor bazılarının da kanıtlarını veriyo. Bir sike sap olabildin mi çok merak ettim bu kafayla