### Question 1

We are given as input a set of
requests (e.g., for the use of an auditorium), with a known start time
and finish time
for each request
. Two requests
, including it in the solution-so-far and deleting from future consideration all requests that conflict with
. Which of the following greedy rules is guaranteed to always compute an optimal solution?

*conflict*if they overlap in time --- if one of them starts strictly between the start and finish times of the other. Our goal is to select a maximum-size subset of the given requests that contains no conflicts. We aim to design a greedy algorithm for this problem with the following form: At each iteration we select a new request### Question 2

We are given as input a set of
jobs, where job
has a processing time
and a deadline
. Recall the definition of
of job
as the amount of time
after its deadline that the job completes, or as 0 if
. Our goal is to minimize the maximum lateness,
. Which of the following greedy rules produces an ordering that minimizes the maximum lateness? You can assume that all processing times and deadlines are distinct.

*completion times*
from the video lectures. Given a schedule (i.e., an ordering of the jobs), we define the*lateness*### Question 3

Consider an undirected graph
where every edge
has a given cost
. Assume that all edge costs are positive and distinct. Let
be a minimum spanning tree of
and
a shortest path from the vertex
to the vertex
. Now suppose that the cost of every edge
of
is increased by
and becomes
. Call this new graph
. Which of the following is true about
?

### Question 4

Suppose
is a minimum spanning tree of the graph
. Let
be an induced subgraph of
. (I.e.,
is obtained from
by taking some subset
of vertices, and taking all edges of
that have both endpoints in
.) Which of the following is true about the edges of
that lie in
? You can assume that edge costs are distinct, if you wish.

### Question 5

Consider an undirected graph
where edge
has cost
. A
is a spanning tree that minimizes the maximum edge cost
. Which of the following statements is true? Assume that the edge costs are distinct.

*minimum bottleneck spanning tree*
## No comments:

## Post a Comment