Examine the time and space complexity of algorithm

Assignment Help Data Structure & Algorithms

Reference no: EM13712962

You have to examine the time and space complexity of algorithm.

Question- Some DNA strings can transform to other strings by breaking into contiguous substrings, reversing some of these substrings, and then reconnecting the substrings in the original order.

For example, x =ACTGCATCAT can transform into y=TCAGCCTATA by breaking x into ACT, GC, ATC, AT, reversing the first, third, and fourth substring, and then reconnecting to form y.

The cost of the transformation is the number of breaks, which is three in the example.

Given two DNA strings of length n each, find the transformation of one string into the other with fewest breaks. Your algorithm should return? if there is no way of transforming one string to the other using this procedure.

Examine the time and space complexity of your algorithm.

Reference no: EM13712962

Questions Cloud

Implement sumpairs and sumof : Using SML writes a version of sumPairs that sums each component of the pairs separately, returning a pair consisting of the sumof the first components and the sum of the second components

Define riboflavin stock in order to create a solution : What volume of water should be added to 7 mL of a 10 mM riboflavin stock in order to create a solution with a working concentration of 350 uM

Draw the process tree and expected output : Draw the process tree and expected output, Repeat the exercise using 3 instead of 2 in the for statement

What was the concentration of hcl in the original solution : A 3 mL volume of a solution containing an unknown concentration of HCl is added to 7 mL of water. It is then determined that the concentration of the HCl in the diluted solution is 630 mM. What was the concentration of HCl in the original solution

Examine the time and space complexity of algorithm : Some DNA strings can transform to other strings by breaking into contiguous substrings, reversing some of these substrings, and then reconnecting the substrings in the original order.

What volumes of 1 m ethanol stock and water should combined : A 10 mL volume of 75 mM ethanol is necessary for an experiment. What volumes of 1 M ethanol stock and water should be combined to produce exactly the required volume at the working concentration

What is the ph of a solution that is 0.041 m in naclo : HClO is a weak acid (Ka = 4.0 x 10^-8) and so the salt NaClO acts as a weak base. What is the pH of a solution that is 0.041 M in NaClO

Explain what volume h2 can be produced at 780 mm hg : What volume H2 can be produced at 780 mm Hg and 15 degrees Celsius from 1 mole Al, 1 mole NaOH and 2 moles H2O. --> Al(s) + NaOH(aq) + H2O (l) ---> NaAl(OH4) (s) + H2(g)

What is the value of distance d : Block 1 of mass m1 slides from rest along a frictionless ramp from height h = 3 m and then collides with stationary block 2, which has mass m2 = 5m1.

User Account

All Pages