CS570
Analysis of Algorithms
Spring 2017
Exam II
Name:
Student ID:
Email Address:
Check if DEN Student
Maximum Received
Problem 1 20
Problem 2 10
Problem 3 10
Problem 4 15
Problem 5 15
Problem 6 15
Problem 7 15
Total
1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any
justification.
[TRUE/FALSE ] The value of the max flow is not enough and we need the
complete flow
[TRUE/FALSE ]
The Ford-Fulkerson algorithm can compute the maximum flow in polynomial time.
[TRUE/FALSE ]
A network with unique maximum flow has a unique min-cut.
[TRUE/FALSE]
If all of the edge capacities in a graph are an integer multiple of 3, then the value of
the maximum flow will be a multiple of 3.
[TRUE/FALSE]
The Floyd-Warshall algorithm always fails to find the shortest path between two
nodes in a graph with a negative cycle.
[TRUE/FALSE] 0/1 knapsack does not have a polynomial time dynamic
programming solution—not even a weakly polynomial solution. 0/1 knapsack has a
pseudo polynomial time dynamic programming solution which is basically an
exponential time solution (with respect to its input size)
[TRUE/FALSE]
If a dynamic programming algorithm has n sub problems, then its running
time complexity is O(n).
[TRUE/FALSE]
The Travelling Salesman problem can be solved using dynamic programming in
polynomial time
[TRUE/FALSE]
If flow in a network has a cycle, this flow is not a valid flow.
[TRUE/FALSE]
We can use the Bellman-Ford algorithm for undirected graph with negative edge
weights.
2) 10 pts
Given , a flow network with source , sink , and positive integer
edge capacities c(e) for every e E. Prove or disprove the following statement:
A maximum flow in an integer capacity graph must have integral (integer) flow on each
edge.
3) 10 pts
The subset sum problem is defined as follows: Given a set of n positive integers
S={a1, a2, …, an} and a target value T, does there exist a subset of S such that the sum
of the elements in the subset is equal to T? Let’s define a boolean matrix M where M(i,
j) is true if there exists a subset of {a1, a2, …, ai} whose sum equals j. Which one of the
following recurrences is valid? (circle one)
4) 15 pts
This problem involves partitioning a given input string into disjoint substrings in the
cheapest way. Let x1x2 . . . xn be a string, where particular value of xi does not matter.
Let C(i,j) (for i ≤ j) be the given precomputed cost of each substring xi . . . xj . A
partition is a decomposition of a string into disjoint substrings. The cost of a partition
is the sum of costs of substrings. The goal is to find the min-cost partition.
An example. Let “ab” be a given string. This string can be partitioning in two
different ways, such as, “a”, “b”, and ”ab” with the following costs C(1,1) + C(2,2)
and C(1,2) respectively.
a) Define (in plain English) subproblems to be solved. (5 pts)
b) Write the recurrence relation for subproblems. (7 pts)
c) Compute the runtime of the algorithm. (3 pts)
5)
You have two rooms to rent out. There are n customers interested in renting the
rooms. The ith customer wishes to rent one room (either room you have) for d[i] days
and is willing to pay bid[i] for the entire stay. Customer requests are non-negotiable
in that they would not be willing to rent for a shorter or longer duration. Devise a
dynamic programming algorithm to determine the maximum profit that you can make
from the customers over a period of D days.
a) Write the recurrence relation for subproblems. (7 pts)
b) Compute the runtime of the algorithm. (4 pts)
6) 15 pts
You are given the following graph. Each edge is labeled with the capacity of that edge.
a) Draw the corresponding residual graph after sending as much flow as possible
along the path s→x→y→v→w→t. (5 pts)
b) Find the value of a max-flow. (5 pts)
c) Find a min-cut? (5 pts)
7) 15 pts
Consider a drip irrigation system, which is an irrigation method that saves water and
fertilizer by allowing water to drip slowly to the roots of plants. Suppose that the
location of all drippers are given to us in terms of their coordinates (xd, yd). Also, we
are given locations of plants specified by their coordinates (xp, yp).
A dripper can only provide water to plants within distance l. A single dripper can
provide water to no more than n plants. However, we recently got some funding to
upgrade our system with which we bought k monster drippers, which can provide
water supply to three times the number of plants compared to standard drippers. So,
we now have i standard drippers and k monster drippers.
Given the locations of the plants and drippers, as well as the parameters l and n,
decide whether every plant can be watered simultaneously by a dripper, subject to the
above mentioned constraints. Justify carefully that your algorithm is correct and can
be obtained in polynomial tim