Hello everybody, welcome to our course on Advanced Algorithms and Complexity. As the first unit in this course, we're going to talk about network flow algorithms and, in particular, in this very first lecture, we're just going to give an example of a problem to give you a feel for what types of things we're going to be talking about in this unit. So to set things up, suppose that you're a disaster relief manager and you're trying to, among other things, you have this city and you want to know how quickly could it be evacuated in the case of an emergency. Well, to do this you have to look at the roads leading out of the city, and so you see that there's the main highway out that will handle 5000 cars an hour. Of course, this isn't the only road leading out of the city. There are some secondary highways that can each handle 2000 cars an hour. Of course, things are a little bit more complicated than that. These other roads, they each bifurcate into two halves. Each of these halves can handle 1000 cars an hour. So you're maybe okay so far. But it turns out that two of those halves merged together a little wise down into just a single road that can only handle 1000 cars now. And so you can imagine that in real life, there are many, many, many more roads than this in their full road network, but this is a toy example. And we'd like to know, given that this is the network, how quickly can we evacuate? Well, it's not hard to start playing around with this. We can take 5000 cars an hour and send them out along the main road. We can send another thousand cars an hour along this northern path here. Another thousand cars an hour can go along up on the northern road and then split off and join in on the merged road, and finally, another thousand cars and hour can go off on the third highway. Now, putting this all together, we have a total of 8000 cars an hour that we can evacuate, but we'd like to know, is this the best that we can do or can you do better? Well, if you play around with this a little bit, there's no obvious way to make an improvement, and you might suspect that this is the best you can do, and in fact, you'd be correct. One way to show this is that if you draw a river, suppose that there was a river where this blue line is on the diagram, you'll note that there are only four bridges that cross that river. And the total capacity of all the bridges is only 8000 cars an hour. So if only 8000 cars an hour can cross this river and you need to cross the river to get out of the city, only 8000 cars an hour can evacuate the city. And that proves that this plan that we have for evacuation is really the best you can do. It's bottlenecked at the river, you can't do any faster. So network flow problems are problems that will allow us to study things like this problem. And this is what we're going to be talking about in this unit. And next lecture, what we're going to do is we're going to take a little bit of a more careful look at this problem. We're going to come up with a formal framework to discuss this kind of issue, and then we're going to discuss some examples of where these sorts of problems might show up in real life. So that's what you have to look forward to in the next lecture. I hope to see you then.