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
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 :
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; }
Get Answers For Free
Most questions answered within 1 hours.