# Combinatorial Algorithms

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)