## 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.