CODEWITHSUNDEEP
algorithmbacktrackingtext-segmentation
Breaking News
Breaking News

Reputation: 414

Backtracking, Text Segmentation

I could not figure out this brainstorming algorithm question! Could some one help?

--------Description--------

Suppose you are a scientist who are searching for certain kinds of genes. You know that a gene you are looking for should be formed of the following blocks\

AT GG CTAC

We call these blocks as 'valid'. All other blocks are called 'invalid'. Now given a gene consisting of symbols

'A', 'G', 'C', 'T' you should identify if the given gene could be formed with valid blocks. Examples of genes which can be formed using valid blocks:

GGATATCTAC CTACGGGG

Examples of genes which can not be formed using valid blocks:

CCC GGCAC

Question!
1. How many possible choice you have after each reduction?
2. Try to draw a recursion tree for this algorithm
3. What kind of data do you need to store after each reduction?
4. Try to write a recurrence relation for the running time of this algorithm.
5. Try to estimate the running time from the above recurrence relation. Is running time exponential or
polynomial in terms of n, the length of a gene?

Upvotes: 0

Views: 233

Answers (1)

firsni
firsni

Reputation: 906

python code to do the backtrack with complexity nnl with n is the number of blocks here 3 and L is the gene length. For the tree I print the current text then ? then the element I test to add.

def genes(chaine, elements, result):
  print()
  if(chaine == ""):
      return result
  ctn = 1
  for elem in elements:
      print(" ".join([" "]*len(chaine)*ctn), "".join(result) + "? " + elem, end = '')
      if(chaine.startswith(elem)):
          return genes(chaine[len(elem):], elements, result + [elem])
      ctn = ctn + 1

   return 0


result = genes("GGATGGATCTAC", ["GG", "AT", "CTAC"], [])
print(result)

Output:

                  ? GG
                GG? GG                                        GG? AT
            GGAT? GG
        GGATGG? GG                        GGATGG? AT
    GGATGGAT? GG                GGATGGAT? AT                        GGATGGAT? CTAC

['GG', 'AT', 'GG', 'AT', 'CTAC']

Upvotes: 3

Related Questions