Microsoft Word – Exam2_fall2015.doc
CS570
Analysis of Algorithms
Fall 2015
Exam II
1) 20 pts
Mark the following statements as TRUE, FALSE. No need to provide any
justification.
The Ford-Fulkerson Algorithm finds a maximum flow of a unit-capacity flow
network with n vertices and m edges in time O(mn).
In a flow network, if maximum flow is unique then min cut must also be unique.
In a flow network, if min cut is unique then maximum flow must also be unique.
In dynamic programming you must calculate the optimal value of a sub-problem
twice, once during the bottom up pass and once during the top down pass.
Bellman-Ford algorithm solves the shortest path problem in graphs with negative cost
edges in polynomial time.
The problem of deciding whether a given flow f of a given flow network G is a
maximum flow can be solved in linear time.
An optimal solution to a 0/1 knapsack problem will always contain the object i with
the greatest value-to-cost ratio Vi/Ci
The Ford-Fulkerson algorithm is based on greedy.
A flow network with unique edge capacities may have several min cuts.
Complexity of a dynamic programming algorithm is equal to the number of unique
sub-problems in the solution space.
2) 20 pts
Consider the flow network G below with source s and sink t. The edge capacities are
the numbers given near each edge.
(a) Find a maximum flow in this network using the Ford Fulkerson algorithm. Show
all steps of augmentation. Once you have found a maximum flow, draw a copy of the
original network G and clearly indicate the flow on each edge of G in your maximum
flow. (12 pts)
(b) Find a minimum s-t cut in the network, i.e. name the two (nonempty) sets of
vertices that define a minimum cut. (8 pts)
3) 20 pts
There is a river going from east to west, on the south bank of the river there are a set
of cities 1…N as shown in the figure below. On the northern bank there are also N
cities. Each city on the south bank has a unique sister city on the north bank of the
river. We use X(i) to denote the sister city corresponding to city i. Suppose you are
assigned a task to build bridges to connect the southern cities with their sister cities
such that as many bridges as possible are built without any bridges crossing each
other. Solve this problem using dynamic programming.
a). Recurrence formula (7 pts)
b). Provide the algorithm to find the value of the optimal solution using the above
recurrence formula (6 pts)
c) Provide the algorithm to list the actual bridges corresponding to the value found in
part b (7 pts)
4) 15 pts
There are n reservoirs and m cities. Due to the drought you have to bring water from
the reservoirs to the cities through a network of pipes. Each city i has a request for Ci
gallons of water every day. To make matters worse, engineers have detected a leaking
pipe in the water network. If the leaking pipe is used, they will lose L gallons of water per
day through that pipe regardless of how much water flows through it (i.e., as long as the
pipe is used, it leaks L gallon, we cannot control the leak by trying to push less water
through that pipe). The other option is to shut down the leaking pipe at both ends, but that
might reduce the capacity of their network. The water network is represented by a graph.
Each edge represents the capacity of the pipe in gallons per day. Provide algorithms to
determine if it is possible to:
a) Meet all demands for water at all cities without using the leaking pipe (7 pts)
b) Meet all demands for water at all cities by using the leaking pipe (6 pts)
c) Meet all demands for water at all cities after fixing the leaking pipe (6 pts)
5) 20 pts
Assume you want to ski down the mountain. You want the total length of your run to
be as long as possible, but you can only go down, i.e. you can only ski from a higher
position to a lower position. The height of the mountain is represented by an n X n
matrix A. A[i][j] is the height of the mountain at position (i,j). At position (i,j), you
can potentially ski to four adjacent positions (i-1,j) (i,j-1), (i,j+1), and (i+1,j) (only if
the adjacent position is lower than current position). Movements in any of the four
directions will add 1 unit to the length of your run. Provide a dynamic programming
solution to find the longest possible downhill ski path starting at any location within
the given n by n grid.