There are tons of different optimization problems out there in computer science. One feature that many of them have in common is that they can't be efficiently solved. But there is an important type of problem, called a network flow problem, that can in fact be solved quite efficiently. Network flow asks how to most efficiently move "stuff" through a network, where "stuff" could be anything from packets on the Internet to materials on a road grid to an abstract notion of association. The class will begin by defining network flow and discussing its applications. Then, we will talk about how to solve it! Algorithms covered for the basic maximum-flow problem may include the Ford-Fulkerson algorithm, the Edmonds-Karp algorithm, Dinic's algorithm, push-relabel methods, and further improvements to these approaches. The class may also cover related topics such as the max-flow min-cut theorem and minimum cost flows. This is an awful lot to digest at once, so the class has been split into two parts, with a break between them. I will structure the class so that you can attend only Part 1 and still understand what network flow is and some ways (though not the most efficient) to solve it. Also, note the use of "may" in the above. The exact topics covered are likely to change depending on your interests.

There are tons of different optimization problems out there in computer science. One feature that many of them have in common is that they can't be efficiently solved. But there is an important type of problem, called a network flow problem, that can in fact be solved quite efficiently. Network flow asks how to most efficiently move "stuff" through a network, where "stuff" could be anything from packets on the Internet to materials on a road grid to an abstract notion of association. The class will begin by defining network flow and discussing its applications. Then, we will talk about how to solve it! Algorithms covered for the basic maximum-flow problem may include the Ford-Fulkerson algorithm, the Edmonds-Karp algorithm, Dinic's algorithm, push-relabel methods, and further improvements to these approaches. The class may also cover related topics such as the max-flow min-cut theorem and minimum cost flows. This is an awful lot to digest at once, so the class has been split into two parts, with a break between them. I will structure the class so that you can attend only Part 1 and still understand what network flow is and some ways (though not the most efficient) to solve it. Also, note the use of "may" in the above. The exact topics covered are likely to change depending on your interests.