Tuesday, January 29, 2013

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?

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.

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

No comments:

Post a Comment

Blog Archive