Question

You're are working on n different projects, but in m hours you are going on vacation. Imagine that for each project i, you had a function fi that told you how happy the people paying for project i would be if out your m available hours you devoted 0 ≤ x ≤ m to project i. Imagine further that each such function has maximum value at most s, corresponding to the project being fully finished (and thus the clients being perfectly happy).

Give a dynamic programming for determining the most happiness you can generate for your clients by splitting your m hours among the n projects.

• Because of book-keeping rules, you can’t spend fractional hours on a project.
• The functions fi are non-decreasing, i.e., for every project i, if t1 ≤ t2, then fi(t1) ≤ fi(t2).
• The running time of your algorithm must be O(nambsc) for some fixed integers a, b, c ≥ 0.

For this problem:

1.Write an identity for the OPT value.

2.Explain why the idenity holds. Your explanation should appear self-evident.

3.Describe the data structure you will use to store the OPT value for the subproblems and the order in which you will fill out the entries in your data structure.

4.In the problems you are asked to return the solution (not just the value of the solution), state the additional information you record which will allow you to retrace your steps and report an optimal solution.

5.Bound the running time by the size of the data structure and the work per entry in it

Answer 1

The ChainedHashTable data structure uses an array of lists, where the th list stores all elements such that . An alternative, called open addressing is to store the elements directly in an array, , with each array location in storing at most one value. This approach is taken by the LinearHashTable described in this section. In some places, this data structure is described as open addressing with linear probing.

The main idea behind a LinearHashTable is that we would, ideally, like to store the element with hash value in the table location . If we cannot do this (because some element is already stored there) then we try to store it at location ; if that's not possible, then we try , and so on, until we find a place for .

There are three types of entries stored in :

1. data values: actual values in the USet that we are representing;
2. values: at array locations where no data has ever been stored; and
3. values: at array locations where data was once stored but that has since been deleted.

In addition to the counter, , that keeps track of the number of elements in the LinearHashTable, a counter, , keeps track of the number of elements of Types 1 and 3. That is, is equal to plus the number of values in . To make this work efficiently, we need to be considerably larger than , so that there are lots of values in . The operations on a LinearHashTable therefore maintain the invariant that .

To summarize, a LinearHashTable contains an array, , that stores data elements, and integers and that keep track of the number of data elements and non- values of , respectively. Because many hash functions only work for table sizes that are a power of 2, we also keep an integer and maintain the invariant that .

    T[] t;   // the table
    int n;   // the size
    int d;   // t.length = 2^d
    int q;   // number of non-null entries in t

The operation in a LinearHashTable is simple. We start at array entry where and search entries , , , and so on, until we find an index such that, either, , or . In the former case we return . In the latter case, we conclude that is not contained in the hash table and return .

    T find(T x) {
        int i = hash(x);
        while (t[i] != null) {
            if (t[i] != del && x.equals(t[i])) return t[i];
            i = (i == t.length-1) ? 0 : i + 1; // increment i
        }
        return null;
    }

The operation is also fairly easy to implement. After checking that is not already stored in the table (using ), we search , , , and so on, until we find a or and store at that location, increment , and , if appropriate.

    boolean add(T x) {
        if (find(x) != null) return false;
        if (2*(q+1) > t.length) resize(); // max 50% occupancy
        int i = hash(x);
        while (t[i] != null && t[i] != del)
            i = (i == t.length-1) ? 0 : i + 1; // increment i
        if (t[i] == null) q++;
        n++;
        t[i] = x;
        return true;
    }