Description
1. There is a precious diamond that is on display in a museum at m disjoint time intervals. There are n
security guards who can be deployed to protect the precious diamond. Each guard has a list of intervals
for which he or she is available to be deployed. Each guard can be deployed to at most M time slots and
has to be deployed to at least L time slots.
Design an algorithm that decides if there is a deployment of
guards to intervals such that each interval has either one or two guards deployed. (10 pts)
2. Consider LAX, a notoriously busy airport with many arriving passengers who want to get to their destinations as soon as possible. There is an available fleet of n Uber drivers to accommodate all passengers.
However, there is a traffic regulation at the airport that limits the total number of Uber drivers at any
given hour-long interval to 0 <= k < n simultaneous drivers. Assume that there are p time intervals.
Each driver provides a subset of the time intervals he or she can work at the airport, with the minimum
requirement of aj hour(s) per day and the maximum bj hour(s) per day. Lastly, the total number of Uber
drivers available per day must be at least m to maintain a minimum customer satisfaction and loyalty.
Design an algorithm to determine if there is a valid way to schedule the Uber drivers with respect to these
constraints. (20 pts)
3. Counter Espionage Academy instructors have designed the following problem to see how well trainees
can detect SPY’s in an n*n grid of letters S, P, and Y.
Trainees are instructed to detect as many disjoint
copies of the word SPY as possible in the given grid. To form the word SPY in the grid they can start at
any S, move to a neighboring P, then move to a neighboring Y.
(They can move north, east, south or west
to get to a neighbor.) The following figure shows one such problem on the left, along with two possible
optimal solutions with three SPY’s each on the right.
Give an efficient network flow-based algorithm to
find the largest number of SPY’s. (20 pts)
4. In the network below, the demand values are shown on vertices. Lower bounds on flow and edge
capacities are shown as (lower bound, capacity) for each edge.
Determine if a feasible circulation exists
or not. If it does, show the feasible circulation. If it doesnot, show the cut in the network that is the
bottleneck. Show all your steps.
5. The following graph G is an instance of a circulation problem with demands. The edge weights represent
capacities and the node weights (in parantheses) represent demands. A negative demand implies source.
(i) Transform this graph into an instance of max-flow problem.
(ii) Now, assume that each edge of G has a constraint of lower bound of 1 unit, i.e., one unit must flow
along all edges. Find the new instance of max-flow problem that includes the lower bound constraint
6. Determine if it is possible for flow to circulate within the given network depicted as graph G. The
demand values, indicated on vertices, represent either supply (if positive) or demand (if negative). Each
edge also has specified lower bounds on flow and capacity.
Demonstrate all necessary steps to ascertain
if a feasible circulation exists within this graph. (20 pts)
(a) Reduce the Feasible Circulation with Lower Bounds problem to a Feasible Circulation problem without
lower bounds. (b) Reduce the Feasible Circulation problem obtained in part (a) to a Max Flow problem
in a Flow Network. (c) Solve the resulting Max Flow problem and explain whether there is a Feasible
Circulation in the original G.
7. USC Admissions Center needs your help in planning paths for Campus tours given to prospective
students or interested groups. Let USC campus be modeled as a weighted, directed graph G containing
locations V connected by one-way roads E.
On a busy day, let k be the number of campus tours that have
to be done at the same time. It is required that the paths of campus tours do not use the same roads. Let
the tour have k starting locations A = {a1, a2, . . . , ak} ⊂ V .
From the starting locations, the groups are
taken by a guide on a path through G to some ending location in B = {b1, b2, . . . , bk} ⊂ V .
Your goal is to
find a path for each group i from the starting location ai
, to any ending location bj such that no two paths
share any edges, and no two groups end in the same location bj .
(a) Design an algorithm to find k paths ai → bj that start and end at different vertices, such that they do
not share any edges.