Problem Set 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 . Assume that all start and finish times are distinct. Two requests conflict if they overlap in time — if one of them starts between the start and finish times of the other. Our goal is to select a maximum-cardinality subset of the given requests that contains no conflicts. (For example, given three requests consuming the intervals [0,3], [2,5], and [4,7], we want to return the first and third requests.) 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 earliest finish time.
  • 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 start time.
  • At each iteration, pick the remaining request with the fewest number of conflicts with other remaining requests (breaking ties arbitrarily).

ANSWER: Consider the following requests:

i | start | finish | duration
-----------------------------
1 | 0     | 3      | 3
2 | 2     | 4      | 2
3 | 3     | 6      | 3

If we pick the request with the smallest , we can only pick , whereas just eyeballing shows that the maximum subset should contain and . Therefore, option 2 is incorrect.

Consider the following requests:

i | start | finish
------------------
1 | 0     | 6
2 | 2     | 4
3 | 3     | 6

If we pick the request with the earliest time (), we cannot pick any from the table above, but if we somehow don’t pick , we can pick either one of or . Therefore, option 3 is incorrect.

It is shown here that option 4 is incorrect as well, but I honestly don’t understand how they came up with such an example, so I’m going to refrain from copy-pasting it here.

Option 1 is correct. To prove it, let be a set of requests and a request with the earliest finish time. Let be the maximum subset of mutually compatible requests, and a request with the earliest finish time. Clearly, . If they are equal, we are done with the proof. Otherwise, let . Since is the request with the earliest finish time in , and , therefore, none of the other requests in conflict with , and hence . Therefore, the maximum subset contains , the request with the earliest finish time.

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

  • None of the other answers are correct.
  • 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

ANSWER: Let be a sequence in increasing order of processing time . Let the position of the job with the maximum lateness be . If we swap job at with the one at , since , we get an even lower value for lateness. Thus, option 3 is incorrect.

By similar argument, option 4 is incorrect.

Let be a sequence in increasing order of deadline . If we swap job at with the one at , the lateness for the new job at position increases. Thus, the swap makes the sequence worse, and hence, the sequence is optimal to begin with.

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 ?

  • may not be a minimum spanning tree and may not be a shortest path.
  • may not be a minimum spanning tree but is always a shortest path.
  • is always a minimum spanning tree and is always a shortest path.
  • must be a minimum spanning tree but may not be a shortest path.

ANSWER: Since Prim’s MST algorithm picks the edge with the lowest cost at each iteration, increasing the cost of every edge by wouldn’t change anything. However, the shortest path may change. Consider the graph . The shortest path from to is . Adding to every edge gives us the new graph . Now is no longer the shortest path between and . Thus, option 4 is correct, and the other ones are not.

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

  • For every and , these edges form a minimum spanning tree of
  • For every and , these edges are contained in some minimum spanning tree of
  • For every and and spanning tree of , at least one of these edges is missing from
  • For every and , these edges form a spanning tree (but not necessary minimum-cost) of

ANSWER: Consider a triangle graph . If , which rules out options 1 and 4.

Option 2 is correct. To prove it, let’s establish the Light-Edge Property of a MST.

Light-Edge Property: Let G = (V, E) be a connected undirected weighted graph with distinct edge weights. For any cut of G, the minimum weight edge that crosses the cut is in the minimum spanning tree T of G.

Proof: Suppose be the minimum weight edge. If we take a cut , then there must be another edge that connects and (since by definition is a connected subgraph). Let ; since, . Since is a MST, this brings us to a contradiction, and hence cannot be true.

Back to the original question, suppose be a MST of and an edge . Arguing on the same lines as the Light-Edge Property, we can show that this contradicts the assumption is a MST, and must be in . Since is an arbitrary edge, all edges in must be included in .

Since option 2 is correct, option 3 is not.

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 and a minimum spanning tree is not 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 always a minimum spanning tree but a minimum spanning tree is not always a minimum bottleneck spanning tree.
  • A minimum bottleneck spanning tree is not always a minimum spanning tree, but a minimum spanning tree is always a minimum bottleneck spanning tree.

ANSWER: Recall the Light-Edge Property; it implies that every other spanning tree has maximum edge cost at least as large. Therefore, a MST is also a minimum bottleneck spanning tree. But the reverse is not true; to see that, consider the graph . Consider the spanning tree ; it doesn’t increase the bottleneck (), and hence is a minimum bottleneck spanning tree, but isn’t a MST.

In this problem you are given as input a graph that is a tree (that is, is undirected, connected, and acyclic). A perfect matching of is a subset of edges such that every vertex is the endpoint of exactly one edge of . Equivalently, matches each vertex of with exactly one other vertex of . For example, a path graph has a perfect matching if and only if it has an even number of vertices.

Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching. The degree of a vertex in a graph is the number of edges incident to it. (The two algorithms differ only in the choice of in line 5.)

Algorithm A:

1 While T has at least one vertex:
2   If T has no edges:
3     halt and output "T has no perfect matching."
4   Else:
5     Let v be a vertex of T with maximum degree.
6     Choose an arbitrary edge e incident to v.
7     Delete e and its two endpoints from T.
8 [end of while loop]
9 Halt and output "T has a perfect matching."

Algorithm B:

1 While T has at least one vertex:
2   If T has no edges:
3     halt and output "T has no perfect matching."
4   Else:
5     Let v be a vertex of T with minimum non-zero degree.
6     Choose an arbitrary edge e incident to v.
7     Delete e and its two endpoints from T.
8 [end of while loop]
9 Halt and output "T has a perfect matching."

Is either algorithm correct?

  • Algorithm A always correctly determines whether or not a given tree graph has a perfect matching; algorithm B does not.
  • Neither algorithm always correctly determines whether or not a given tree graph has a perfect matching.
  • Both algorithms always correctly determine whether or not a given tree graph has a perfect matching.
  • Algorithm B always correctly determines whether or not a given tree graph has a perfect matching; algorithm A does not.

ANSWER: The algorithms are understated: When a vertex is deleted, all edges incident to that vertex are also deleted, otherwise we’re left with dangling edges.

Consider the path tree . Algo A chooses vertex , and say, edge . After deleting vertices and , and all the edges, we’re left with vertices and with no edges. Algo A halts, and incorrectly declares that doesn’t have perfect matching (it does, ).

Lets prove the correctness of algo B by induction. For , it correctly identifies that doesn’t have perfect matching. For , it correctly identifies that has perfect matching. Clearly, for to have perfect matching, must be even. Assume algo B works for . Let us add a new vertex and a new edge to , where is some existing vertex in . Clearly, for to have perfect matching, it must include edge (since that’s the only way to match vertex ). By construction, algo B picks and removes edge in some iteration, leaving , which by inductive hypothesis, is correctly solved by algo B.

Therefore, algo B is correct.