Need Assistance With This One Since We're Unable to have Access to Video

 Problem Set #1

The hard deadline for this quiz is Sun 10 Feb 2013 11:59 PM PST.

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 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 , 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?

At each iteration, pick the remaining request with the fewest number of conflicts with other remaining requests (breaking ties arbitrarily).

At each iteration, pick the remaining request which requires the least time (i.e., has the smallest value of ) (breaking ties arbitrarily).

At each iteration, pick the remaining request with the earliest finish time (breaking ties arbitrarily).

At each iteration, pick the remaining request with the earliest start time (breaking ties arbitrarily).

Question 2

We are given as input a set of jobs, where job has a processing time and a deadline . Recall the definition of completion times from the video lectures. Given a schedule (i.e., an ordering of the jobs), we define the lateness 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.

Schedule the requests in increasing order of deadline

Schedule the requests in increasing order of processing time

Schedule the requests in increasing order of the product

None of the above.

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 ?

is always a minimum spanning tree and is always a shortest - path.

may not be a minimum spanning tree but is always a shortest - path.

may not be a minimum spanning tree and may not be a shortest - path.

must be a minimum spanning tree but may not be a shortest - path.

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.

They might be disjoint from every minimum spanning tree of

They form a minimum spanning tree of

They are always contained in some minimum spanning tree of

They might have non-empty intersection with a minimum spanning tree of , but at least one of the edges will be missing from

Question 5

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

A minimum bottleneck spanning tree is not always a minimum spanning tree, but a minimum spanning tree is always a minimum bottleneck spanning tree.

A minimum bottleneck spanning tree is always a minimum spanning tree and a minimum spanning tree is always a minimum bottleneck spanning tree.

A minimum bottleneck spanning tree is not always a minimum spanning tree and a minimum spanning tree is not always a minimum bottleneck spanning tree.

A minimum bottleneck spanning tree is always a minimum spanning tree but a minimum spanning tree is not always a minimum bottleneck spanning tree.