Problem Set #5
CS 155 -- due December 8, 1999
Problem 1 is worth 20 points; the other problems are worth 10
points each. No late submissions will be accepted.
- The following divide-and-conquer F-sorting algorithm was
designed to have a time complexity near the theoretical minimum
given by the decision tree model. A top-level description is as
follows:
- If n is even, compare the n elements pairwise to get a set of n
pairs. Sort the pairs recursively based on their winning element.
- Let W=(wi) be the sorted set of winners and
L=(li) be the set of losers, where li <= wi.
If n is odd, do as above and add the uncompared element to the
end of L. In either case, add l1 to the beginning of W.
- Merge L into W by inserting the elements of L
(beginning with i=2) one at a time, using binary search to find
the spot for insertion into W. Here the elements of L are merged in
from right to left in blocks from
lm(k) down to lm(k-1)+1, where m(k)
is given by the recurrence mk = 2k - mk-1,
and m2=3. Note that if m(k-1)+1 <= i <= m(k), the sequence
of elements into which li is be merged into contains the
values of L in positions before m(k-1)+1, the values of W in
positions before i, and the elements of L in the same block but
with larger subscripts.
- Find the values of mk for k=2 to k=7.
- For each of the subscripts from i=11 down through i=6, how large is the
sorted sequence into which li is to be inserted?
- For each of the subscripts in the block from i=m(k) down through
i=m(k-1)+1, how large is the sorted sequence into which li is
to be inserted?
- Trace the operation of the F-sorting algorithm on the input
sequence
(8 5 4 9 1 7 6 3 2 0). Compare the number of element comparisons required
with the theoretical minimum obtained from the decision tree model.
- How many element comparisons are required to apply the F-sorting
algorithm to an input sequence of size 21? Compare this value to the
theoretical minimum obtained from the decision tree model.
- An instance of the Shortest Common Superstring Decision
Problem consists of a finite alphabet S, a set R of strings over S,
and a target integer K. The question is whether there is a string
over S of length at most K that is a superstring of every string in R.
Show that this problem is in NP.
- Show that the version of the Boolean Satisfiability Problem in
which every clause contains at most 2 literals is in P. You might
want to test your algorithm on the cases
{{x,y}, {x',y}, {x,y'}, {x',y'}}
and
{{x',y}, {x,y'}, {x',y'}, {y',z}, {y,z'}, {y',z'}}
and
{{x',y}, {x,y'}, {x',y'}, {y',z}, {y,z'}, {y,z}}