Homework Assignment 2

Due: by 6pm on Tue 28 Oct
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.

Important Note: For all dynamic programming algorithms, please follow the outline given in class when you write up your answer:

  • Step 1. Define a table of values (clearly state the meaning of each table entry, in particular, which specific subproblem it corresponds to and what specific value it stores).
  • Step 2. Give a recurrence for the values in the table, and justify that your recurrence is correct (by reasoning about the recursive structure of optimal solutions).
  • Step 3. Give a bottom-up algorithm that computes the values in the table following the recurrence, and analyze the runtime of your algorithm.
  • Step 4. Give an algorithm that reconstructs an optimal solution from the table values (include an explanation of any additional information required and a brief justification that your solution is constructed correctly, as well as a brief analysis of your algorithm's runtime).

  1. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10, then making the first cut at position 3 incurs a total cost of 20 + 17 = 37, while doing position 10 first has a better overall cost of 20 + 10 = 30.

    Give a dynamic programming algorithm that, given the locations of m cuts in a string of length n, finds the minimum cost of breaking the string into m+1 pieces.

  2. A mission-critical production system has n stages that have to be performed sequentially; stage i is performed by machine Mi. Each machine Mi has a probability ri of functioning reliably (so probability 1-ri of failing), and the failures are independent of each other. Therefore, if we implement each stage with a single machine, the probability that the whole system works is r1 × r2 × ... × rn. To improve this probability we add redundancy, by having mi copies of the machine Mi that performs stage i. The probability that all mi copies fall simultaneously is only (1-ri)mi, so the probability that stage i is completed correctly is 1 - (1-ri)mi and the probability that the whole system works is now
    ∏i=1,...,n (1 - (1-ri)mi).
    Each machine Mi also has a cost ci, and there is a total budget B to buy machines (where B and each ci are positive integers.)

    Give an algorithm that takes the probabilities r1,...,rn, the costs c1,...,cn, and the budget B, and that returns the redundancies m1,...,mn that are within the available budget and that maximize the probability that the system works correctly.

  3. A "dominating set" D in a graph G = (V,E) is a set of vertices such that every vertex in V - D is adjacent to at least one vertex in D. (The problem of determining a dominating set of minimum cardinality is NP-hard for graphs in general.) If the vertices of the graph are weighted (i.e., for each vertex v ∈ V there is a weight w(v)), then one wants to find a dominating set of minimum total weight, i.e., one wants a dominating set D such that ∑v∈D w(v) is as small as possible.

    Your task is to construct a dynamic programming algorithm to compute such a minimum weight dominating set in a tree T = (V,E). In order to solve this problem, first consider the "dynamic programming table" that will help you solve the problem of computing the smallest possible total weight of any dominating set (later we'll worry about computing the set itself). When working on trees, one usually comes up with this "table" by examining an arbitrary non-leaf vertex x and considering the information one must know about the subtrees rooted at x's children in order to solve the problem for x. In other words, the table is not stored in a separate array but rather as one (or more) value(s) directly associated with each node in the tree, and the recursive structure of the solution is given directly by the tree structure itself. The dynamic programming then proceeds in a "bottom-up" fashion (i.e., from the leaves to the root). This will give you a recursive paradigm for computing all entries in the "table" and it should be clear that from the entries for the root of the tree, you can easily compute the total weight of a minimum weight dominating set. The next problem, of course, is to take those values and produce the vertices in D, a dominating set that achieves the minimum possible total weight.

    1. State precisely the information contained in your "dynamic programming table". In particular, specify the exact sub-problem whose solution is stored in each entry of your table.
      (Hint: You will find it helpful to store more than one value at each node of the tree.)

    2. Give a simple recurrence that could be used to compute the entries in your table. Justify briefly that your recurrence is correct.

    3. Show how, given the table, you can compute W, the total weight of a minimum weight dominating set.

    4. Give an algorithm that will determine vertices in a dominating set D such that D has total weight W, given the entries in your table.

    5. To help the marker, show how your algorithm works on the following example (where the weight of each vertex is indicated next to its label, between parentheses). In particular, clearly indicate the value(s) computed by your algorithm for each node in the tree. 

                      a (10)
              _/ \_
             /     \
        (4) b       c (4)
          _/ \___
         /       \
    (8) d       _ e _ (5)
       / \     /  |  \
      f   g   h   i   j
     (2) (4) (1) (1) (6)

      Note that the minimum weight dominating set for this tree is {c,e,f,g} with a total weight of 15.

  4. You are given a list L whose elements can be compared to each other for equality but for not for order (i.e., for all valid indices i,j, the comparisons "L[i] = L[j]" and "L[i] ≠ L[j]" can be made, but other comparisons like "<", ,"≤", ">", "≥" raise exceptions) — for example, this could happen if we were testing computer chips against one another, where we can tell whether or not two chips are equivalent but the notion of one chip being "less than" another makes no sense. We wish to find elements that are duplicated many times in L.

    More precisely, we wish to find any elements that appear in L more than n/3 times (where n = len(L) is the length of L) — note that there can be at most 2 such elements. An obvious algorithm is to take each element in turn and count how many times it is repeated in L. However, this requires time Θ(n2) and we would like to do better — of course!

    Give a divide-and-conquer algorithm that solves this problem in time Θ(n log n). Justify that your algorithm is correct (i.e., explain the strategy employed by your algorithm any why it works) and justify that it runs within the desired time bound (you may use the Master Theorem as long as you explain how it applies to your algorithm).