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 nXn 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)
Note: We are only looking for the largest number of SPYs not the actual location of the
words. No proof is necessary.