Combinatorial Algorithms
Programming Assignment #1/Median exact complexity
4
. Det
ermine a strategy that will realize this number
. Write out the
complete decision tree
, omitting symmetric cases
.
You can separate disjoint cases onto
different pages.
Carefully check all
non
–
symmetric
inputs to verify that the median is
exactly determined on every branch of the tree. (10 points)
II.
Determine (1, 1, 1, 2, 2). Determine how many non
–
symmetric inputs need to be
checked in order to verify that your str
ategy works in
all
cases. Write and execute a
computer program to check all the necessary inputs. Be sure to supply pseudocode for
your algorithm. (10 points)
III.
Consider
V
1
6
,
8
(
)
, which is known to be less than or equal to 31.
A possible
strategy to achieve 30c will be sketched out in class. Your part will be to elucidate it, so
that it is clear that it applies to all cases of input. (10 points)
Extra Credit
: Write a computer program to test your strategy
for
V
1
6
,
8
(
)
against all
possible inputs. There are a very large number of possible inputs, although symmetrical
cases can reduce the total quite a bit.
(10 points more)