Consider this flow network.
(a) Following Tim's suggestion, we decide to use the highest-capacity path, Source -> A -> B -> C-> Sink, with a flow of four units. Draw the residual network, showing how much additional flow can be pushed between nodes.
(b) What is the highest-capacity augmenting path in the residual network. (Describe it as a sequence of nodes from Source to Sink, along with the largest flow it will support.)
(c) Find a maximum flow for the original graph. (You needn't show your work ... I'm not going to check it.)
(d) What is the minimum cut corresponding to your max flow?
Warning: The following problems are supposed to be like ones that arise in real-world consulting jobs. (Actually, they are adapted from the problems you created in homework number 2.) They may be easy, hard, stupid, or ambiguous. I'm not necessarily expecting you to come with optimal algoritms (and may not know how to do them myself). Your job is to do something intelligent with the problems.
For each problem, imagine that I hired your group as consultants. I'm not paying you that much - only enough for 2-3 hours per problem per group member. Your goal is to win the contract for the next phase (e.g. more research or writing the program) or to make me want to hire your group for other work in the future. I'm looking for an articulate and insightful response. It might be 500 words, it could be much shorter. For instance, you might write something along the lines of "This problem could be solved by a simple greedy heuristic (Algorithm A descibed below) if it weren't for the constraint that (blah blah). This apparantly makes the problem much more difficult - in Example 1 below we show how a seemingly small change in the input makes a large change in the optimal solution. Currently, we believe that a promising approach to the problem is based on a divide-and-conquer approach (see Algorithm B). Even though this runs in Theta(N^2) time, it doesn't always give the optimal answer (see Example 2 below)." (I don't think the above narrative is particularly appropriate for any of the problems, but it may give you an idea of what I mean by "do something intelligent with the problem".)
You may want to discuss the problems with me, for instance if you feel the problem could be formulated in a way that would better meet my real needs. I will play the role of your customer (who doesn't know how to solve the problem and doesn't exactly know what I want).
Good luck!
Given an undirected graph and two distinguished nodes S and T, and an integer k, find a maximum-sized set of node-disjoint paths from S to T, where each path has length at most k. (If I recall, the motivation was to provide fault-tolerance in a communication network. We want the paths to be disjoint so that if all but one fails, we can still commuicate, and we want them short so that the latency is small.)
You are the manager of a boat rental concession. You have a set of N boats that can't be rented because they need to be repaired. You can only work on fixing up one boat at a time, since you have a small workshop. Boat i will take D(i) days to repair, and will bring in M(i) dollars per day after it is fixed up. Find an algorithm that tells which boats to repair, and when, so as to maximize your income.
You are given an undirected graph G with N nodes and positive weights on each edge. The nodes represent possible building sites, and the weights are the time it would take to walk between buildings at the two sites.
You are also given a set of L distinct labels, and a collection of designated subsets of L. The labels are the names of the buildings to be built, and each subset represents a group of buildings that some collection of people will use. For instance, the CS graduate students will use some group of building, the Warren college students will use another group (which might include some of the buildings that the CS majors use), etc.
Given an assignment of L to G (i.e. a one-to-one mapping from L to the nodes of G) for each designated subset S, define the cost C(S) to be the sum of all the edges between nodes whose labels are in S. (The lower the cost, the more convient the building locations are for the users of that group of building).
Finally, define the total cost of the assignment to be the sum of the costs of all the designated subsets. The problem is to find the assignment of least total cost.