13. Incremental Improvement: Max Flow, Min Cut

[@karansvnit]

Cut -> 46:45 Residual Graph -> 1:08:10 Augmenting Path -> 1:18:10

[@Kr4cKHe4D]

thanks mate haha

[@volimsamopare6946]

Thanks!!

[@Dontonethefirst]

You dropped this, 👑

[@wickshawn3994]

thanks bruh

[@ivanmartinezmorales3483]

Not all heroes wear capes

[@anmol9096]

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.

[@ilyakopyl]

I don't know how I would survive algorithm classes in my school without these MIT lectures.

[@matajuan366]

hookers and cocaine my friend

[@brendawilliams8062]

Watching it fit previous diagrams and rounding numbers is interesting

[@MatthewYe]

Only video about network flow I was able to understand - thanks MIT.

[@anishbhanushali]

if anyone's want to jump directly on finding cuts, @ 1:07:00 he starts to explain how you find min-cut

[@Davio88]

thank you very much

[@nguyenthanhdat93]

The lecture is phenomenal!! Thank you very much MIT for making this course open-source to the public !!

[@adrianbona]

You're rocking it, Srinivas 🎉

[@mikhailosiko]

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.

[@M4D4F4K4.]

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.

[@djtiner1]

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!

[@brendawilliams8062]

I felt the electric 📐 angle on it. A great lecturer.

[@BlackHermit]

The Frisbee of true Computer Science!

[@robinranabhat3125]

Studying this alongside CLRS really really helps

[@matthewrister]

Love his enthusiasm!

[@junzhai1715]

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)

[@jacobsalzberg8579]

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?

[@xinli6243]

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?

[@brendawilliams8062]

I don’t know 🤷‍♀️. I just say in real life you need electricity or telephone poles.

[@SphereofTime]

1:12:48 esidual network base on flow

[@mystmuffin3600]

How does the sum at 28:40 even work? The sum of flow values outgoing from all vertices except source and sink equals zero?

[@asian1599]

at 51:36, doesn't it break flow conservation since one of the nodes has 2 going in but 3 goes out?

[@ryanc7840]

A huge thanks and kudos to Professor Devadas.

[@subhamraj2500]

Cut 47:00

[@ivanserranohernandez434]

Thanks MIT for these great lectures!

[@avinashpatil8816]

He actually threw frisbee at students at an MIT lecture. That's hilarious....

[@F1mus]

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.

[@varunnarayanan8720]

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?

[@jeongminyoun5388]

Please, show me upper graph when you explain residual graph network flow, I didn't know that how it works.

[@mostafaomar5441]

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.

[@arjunsingh2183]

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.

[@omercreateswords]

at 42:14 why f(s,V)=f(V,V)-f(V-s,V)?

[@junzhai1715]

because V-{s} and {s} are disjoint sets. By the third property, we have f(s,V)+f(V-s,V)=f(V,V)

[@studyup6106]

46:46 cut

[@shubhamtomar95]

How does f(u, v) work in skew symmetry when (u,v) are not connected by an edge?

[@sambennet1138]

It would be 0 = -0 since we define any (u,v) with no explicitly given capacity as 0

[@adityakohli5160]

That's a very nice explanation !

[@dipenbhuva2061]

Informative!! I am eating information like never before :)

[@h4vret]

Excellent explanation.

[@shreemaypanhalkar451]

Thank you very much.

[@malharjajoo7393]

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 )

[@viveksengupta]

you can always negate and break the LHS, same deal

[@amsainju]

The lecture is really good but the movement of the camera is making me dizzy.

[@jenuno2]

Perfect, thanks !

[@foreveralice8311]

Great Lecture! Wonderful!

[@OmarAhmed-od9rf]

What did that student mean at kzbin.info/www/bejne/jIq9eJ-dr9eSd9U?? We did consider c at f(d,c) which is -1 . Not sure what did he mean with his question.

[@aybrl]

This is great. Thank you

[@khailai5204]

Amazing class!

[@rifathasan6017]

is it related to gomory hu's algorithm?

[@malharjajoo7393]

How would you claim that using bottleneck value as the flow will always be correct ?

[@yujeong8373]

Cool class

[@osmankhalid2005]

Min-cut example part not clear.

[@RayvinLai]

I saw Erik on the seat when camera zoom out

[@snlgrg]

Can somebody Plz provide me the link to the next lecture, which is continuation of this one.. !!

[@mitocw]

+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: kzbin.info/aero/PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp

[@PureClarityAbsolute]

Mr. Cameraman focus on the BOARD more than on the teacher.

[@videofountain]

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.

[@raynoldcsya8317]

i think the camera panning is automated right? seems like there is some tracking going on... If so that is pretty amazing

[@SannaFarrukh]

videofountain k

[@李愚-f7j]

@@raynoldcsya8317 yeah imagine them holding the camera and track the board and professor for over 1 hour... a lot of endeavors

[@pratyushvatsa7490]

His bag is actually a 4-dimensional container

[@inesoliveira7418]

my teachers never gave me frisbees

[@hendelsrkearny]

What's CLRS?

[@hendelsrkearny]

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.

[@malharjajoo7393]

I think there is a small mistake at the end in the example. Edge from c-> t should be 0:2

[@videofountain]

At the time point kzbin.info/www/bejne/jIq9eJ-dr9eSd9Um40s 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.

[@dkg4975]

I don't know about others but I don't like these kind of teachers

[@buraknuhemiroglu6033]

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.

[@mr.arikodus7527]

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