Homework Assignment 1

Due: by 6pm on Tue 30 Sep
Worth: 8%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

  1. Prof. Pushover has agreed to assign as much of his TAs' time as necessary to ensure that his course bulletin board is monitored around the clock (24 hours a day, 7 days a week) throughout the term. Suppose that his TAs have given him their weekly availabilities, specified as intervals [si,fi] where si < fi are the start and end times of each available time slot, over some suitable range of non-negative integers.

    Prof. Pushover would like to draw up a monitoring schedule with the following properties:

    1. at every point in time, there is at least one TA available to monitor the course bulletin board, i.e., there are no gaps in the schedule, although it's OK if there is overlap, and
    2. the TAs are not overworked, i.e., the schedule uses as few available time slots as possible to achieve property I, so that there are enough TA hours left over to help out with marking.

    Note that this problem is a "dual" to the activity scheduling problem. With the same kind of input — intervals [s1,f1], ..., [sn,fn] — we are asked a complementary question — to find a subset of intervals that totally cover the range from the earliest start time to the latest finish time, with overlap allowed, using as few intervals as possible.

    1. Give an ordering of the intervals for which the natural greedy algorithm does not always find an optimal solution — include a description of some specific input for your algorithm, show the solution found by the greedy algorithm, and justify that it is not optimal.

    2. Design a greedy algorithm that solves this problem, i.e., on input [s1,f1], ..., [sn,fn], your algorithm either produces a valid schedule that uses the smallest number of intervals, or it correctly states that no such schedule is possible.
      Analyze the running time of your algorithm, and prove its correctness.

  2. Consider the coin-changing problem from Exercise 1. As you've seen, the natural greedy algorithm works for certain denominations but not for others. We would like to see if we can find general properties of denominations that would guarantee that the greedy algorithm always works, without having to do a full proof of correctness.

    1. Suppose each denomination is an integer multiple of the previous denomination, i.e., ∃ k1, k2, ..., kn-1 ∈ N such that

        d1 = 1 < d2 = k1 d1 < d3 = k2 d2 < ... < dn = kn-1 dn-1.

      Prove or disprove: the natural greedy algorithm yields an optimal solution for all such denominations.

    2. Suppose each denomination is at least twice as large as the previous one, i.e., di+1 ≥ 2 di for i = 1,2,....,n-1.
      Prove or disprove: the natural greedy algorithm yields an optimal solution for all such denominations.

    3. BONUS! Warning: this is difficult, and it will be marked harshly — credit will be given only for making significant progress toward a correct answer.
      Can you find a more general condition that guarantees that the natural greedy algorithm will yield an optimal solution for all denominations that satisfy your condition? Can you prove that this is the case? Can you prove that the natural greedy algorithm will fail for all denominations that do not satisfy your condition?

  3. For any undirected, connected, weighted graph G with non-negative integer weights, let m(G) represent the total weight of a minimum spanning tree of G.

    1. Suppose that we pick one edge in G whose weight is positive, and reduce the weight of that edge to zero. Show that this does not necessarily reduce m(G), i.e., give a specific weighted graph G and an edge e in G with w(e) > 0, such that setting w(e) = 0 does not change m(G).

    2. Suppose that we pick one edge in G whose weight is maximum, and reduce the weight of that edge to zero. Does this guarantee a reduction in m(G)? If so, give a short proof that m(G) always decreases; if not, give a counter-example (as in part (a)).

    3. Give an efficient algorithm that takes as input an undirected, connected, weighted graph G together with one of its minimum spanning trees T, and that outputs one edge e of G with the property that reducing the weight of e to zero yields the maximum reduction possible to m(G).
      Analyze the running time of your algorithm (for full marks, it should run in linear time), and prove that it is correct.

  4. A "ladder" is a very restricted type of graph with vertex set V = {a1, a2, ..., an, b1, b2, ..., bn} and edge set E = {(ai,bi) : 1 ≤ i ≤ n} ∪ {(ai,ai+1), (bi,bi+1) : 1 ≤ i ≤ n-1}.
    Pictorially, a ladder looks like this: 

        a1 ---- a2 ---- a3 -- ... -- an-1 ---- an
    |       |       |            |        |
    |       |       |            |        |
    b1 ---- b2 ---- b3 -- ... -- bn-1 ---- bn

    Suppose that each vertex v in a ladder has a positive integer weight w(v). We wish to find an independent set in this ladder (a subset of vertices with no edge between any two of them) such that the total weight of the vertices in the independent set is maximal.

    1. Give a natural greedy algorithm for this problem.
      Prove that your greedy algorithm always yields an optimal solution, or give a specific counter-example to show that your greedy algorithm does not always work (include the output produced by your algorithm and justify that it is not optimal).

    2. Give a dynamic programming algorithm that solves this problem.
      Justify that your algorithm is correct (give an argument about the recursive structure of optimal solutions), and analyze the worst-case running time of your algorithm.
      Hint: You will need to store values in more than one array, where the values in one array depend on the values in other arrays.