Introduction to Algorithms Homework 4

CS 577: Introduction to Algorithms Homework 4

Ground Rules
• The homework is worth 5 points (out of a total of 100 points you can accumulate in this course).
• The homework is to be done and submitted in pairs. You can partner with someone from either section.
• The homework is due at the beginning of either lecture on the due date.
• No extensions to the due date will be given under any circumstances.
• Turn in your solution to each problem on a separate sheet of paper (or sheets stapled together), with your names
clearly written on top.
Note
• When we ask for an efficient algorithm, it means that the running time for the algorithm should be some polynomial in the size of the problem. For graph problems, the size is |V | + |E| = n + m = O(n2), so we require
an algorithm with running time O(nc) for some constant c.
• When we ask you to analyze an algorithm, provide a proof of correctness as well as an analysis of running time.
Problems
1. (Worth: 2 points. Page limit: 1 sheet; 2 sides) Let G = (V, E) be a connected undirected graph. We will call
a subgraph (V, E0
) special if it is connected and has exactly one cycle.
(a) Show that a subgraph is special iff it can be obtained by taking a spanning tree and adding one edge.
(b) Let G have non-negative weights on its edges. Suppose all edge weights are distinct. Describe and analyze
efficient algorithm that finds a minimum-weight special subgraph of G, assuming there is one.
2. (Worth: 3 points. Page limit: 2 sheets; 3 sides) Suppose that on a busy day of the semester you get homework
for each of the n courses that you are taking. Homework for the i
th course is due within ti days, and you earn pi
points for submitting the homework on time. Unfortunately it takes you one full day to do each homework. So,
for example, if you have 4 homeworks due within 2, 3, 1, and 2 days, respectively, you cannot submit all four
on time, but you can submit the first three on time by doing the third one on day 1, the first one on day 2, and
the second one on day 3. Your objective is to maximize the total number of points you can earn by submitting a
subset of the homeworks on time.
(a) Let S be a subset of all homeworks. Call S “reasonable” if there is an order in which you can do the
homeworks in S so that each one can be submitted on time. Prove that S is reasonable if and only if for all
integers t ≤ n, the number of homeworks in S due within t days or less is no more than t.
(Hint: Consider doing the homework in increasing order of due date.)
(b) Describe and analyze an efficient algorithm to determine which homework to do on which day so as to
maximize the number of points you can earn by submitting a subset of the homework on time.
(Hint: Build up a reasonable set of homeworks by considering homeworks in a particular order and adding
each homework to your schedule if the set of selected homeworks continues to remain reasonable. Use
part (a) to check for feasibility. What order should you consider homeworks in to maximize the number of
points earned? Use an “exchange” argument to prove the correctness of your algorithm.)
1