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