Algorithms

Option  #1:  

Algorithm  Design

A  palindrome  is  a  sequence  of  units  that  has  the  property  of  reading  the  same  in either  direction  

(e.g.,  GCCG).  Palindromes  also  occur  in  nucleotide  acid sequences  (e.g.,  DNA  and  RNA).  To  learn  more  about palindromes  in  DNAs  and  RNAs,  please  refer  to  the   following  web  sites:  

1.   http://en.wikipedia.org/wiki/Palindrome

2.   http://en.wikipedia.org/wiki/Palindromic_sequence

3.   http://users.rcn.com/jkimball.ma.ultranet/BiologyPages/P/Palindromes.html

4. http://users.ccewb.net/lonerock/H5N1/RNAPalindromesInfluenza.pdf

However,  due  to  mutation,  there  could  be  some  insertion  of deletion  which  makes  some  palindromes  not  palindromes any  more.  For example, GCCACCG is a palindrome.  Due to  deletion,  this  sequence  might  be  changed  to  CCACCG  (“G”  was  deleted).  

In  this  project,  you  are  required  to  design  an  algorithm   which  takes  an  input  string  and  return  a  palindrome  by   inserting  the  smallest  number  of  letters.  You are allowed to insert characters at any position of the string.  

For  example,  AAT  can  be  turned into  palindrome  TAAT  by  one  insertion  T,  and  GCT  into   GCTCG  with  two  insertions  CG.  

Besides  designing  an  algorithm  you  also  need  to  provide the  time  complexity  analysis  (e.g.  big-​O  notation).