Lecture 31 Max Flow and Min Cut

Today, we finished algorithm on strongly connected component. We also defined the problem of max flow and showed that the maximum flow is always upper bounded by the minimum cut.

Lecture 30. Strongly Connected Component

Today, we explained how to use DFS to find all the strongly connected components of a graph.

Homework 5

Homework 5 is out. Any question can be asked here.

Problem 1
Q: is there a maximum grade?
A:You can assume there is no maximum grade for each course.


Q: Can you give us hint on the running time for problem 1?
For full credit. The running time should be O(n), O(T log n+ n), O(nT^2)
Hint for case 3:　dynamic programming


Problem 4
Q:The goal is to: delete as many edges as possible from G , when Vertex u is reachable from v if there is a path from v to u. Also, do we need to remove as many edges as possible from the other vertexes that will be along the path from u--to --v? or just to remove the edges that connect u--to--v and left the minimum path.

A:　This problem requires you to delete the maximum number edges so that the reachability does not change for *ANY* two vertices u, v; i.e., for any two vertices u,v in V,  u is reachable from v in G if and only if u is reachable from v in G'.

Lecture 29 DFS, longest path, topological sort, and strongly connected component

Today, we talked about DFS and its applications on solving topological sort, longest path in a graph, and deciding whether a directed graph is strongly connected.

Lecture 28. Algorithms for finding the shortest path

Today, we talked about three different algorithms for the shortest path problem. The Bellman-Ford algorithm, Floyd-Warshall algorithm and Dijkstra's algorithm.

Lecture 27. Dynamic Proigramming (2)

Today, we talked about the longest increasing subsequence. We gave two algorithms with running time O(n^2) and O(n log n).

Then we talked about 0-1 Knapsack problem and gave a dynamic programming algorithm for it.

Lecture 26 Dynamic programming

Today we talked about dyanmic programming. We showed how to use Dynamic Programming to solve the weight verision of activity selection.