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)