CMI2015-B-07

Question

There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new side products secreted by the virus push the old products along the fibre towards its ends. The possible actions of the virus are as follows

1. Produce an acid molecule to its left and a base molecule to its right.
2. Produce a base molecule to its left and an acid molecule to its right.
3. Divide into two viruses, each of which continues to behave like its ancestor.
4. Die.

You are given a sequence of acid and base molecules from one end of the fibre to the other end. Design an algorithm to check if a single virus could possibly have produced the given sequence. Use dynamic programming, checking smaller subsequences before checking bigger subsequences.

Answer 1

Comments

Why would you need to apply any membership algorithm.

You can just use pushdown automata to see if 2 vars are equal in number.